2: Індукція та рекурсія
- Page ID
- 64069
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Якщо ви не знайомі з принципом математичної індукції, вам слід прочитати Додаток B. Принцип математичної індукції говорить, що для того, щоб довести твердження про ціле число\(n\), якщо ми можемо\(1\). Доведіть заяву\(n = b\), коли, для деяких фіксованих цілих чисел\(b\), і\(2\). Покажіть, що істинність твердження for\(n = k − 1\) передбачає істинність твердження для\(n = k\) кожного разу\(k > b\), тоді ми можемо зробити висновок, що твердження вірно для всіх цілих чисел\(n ≥ b.\)
- 2.1: Деякі приклади математичного введення
- Принцип математичної індукції говорить, що для того, щоб довести твердження про ціле число n, якщо ми можемо 1) Довести твердження, коли n = b, для якогось фіксованого цілого числа b, і 2) Показати, що істинність твердження для n = k−1 передбачає істинність твердження для n = k всякий раз, коли k > b, то ми можемо зробити висновок, що твердження вірно для всіх цілих чисел n ≥ b.
- 2.3: Графік і дерева
- У розділі 1.3.4 ми ввели ідею орієнтованого графа. Графіки складаються з вершин і ребер. Ми описуємо вершини та ребра приблизно так само, як описуємо точки та лінії в геометрії: ми насправді не говоримо, що таке вершини та ребра, але ми говоримо, що вони роблять. У нас просто немає складної системи аксіом, як ми робимо в геометрії. Графік складається з множини V, яка називається множиною вершин, і множини E, яка називається набором ребер. Кожен член V називається вершиною, а кожен член Е називається ребром.
- 2.4: Застосування індукції та рекурсії в комбінаториці та теорії графів (вправи)
- Цей розділ містить додаткові проблеми, пов'язані з матеріалами, розглянутими в розділі 2.
Мініатюра: креслення графіка. (Громадське надбання; АзаТот).