2: Індукція та рекурсія

Last updated

Oct 27, 2022
Save as PDF
- 1.4: Що таке комбінаторика? (Вправи)
- 2.1: Деякі приклади математичного введення

$\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.2: Відносини повторення
2.3: Графік і дерева
У розділі 1.3.4 ми ввели ідею орієнтованого графа. Графіки складаються з вершин і ребер. Ми описуємо вершини та ребра приблизно так само, як описуємо точки та лінії в геометрії: ми насправді не говоримо, що таке вершини та ребра, але ми говоримо, що вони роблять. У нас просто немає складної системи аксіом, як ми робимо в геометрії. Графік складається з множини V, яка називається множиною вершин, і множини E, яка називається набором ребер. Кожен член V називається вершиною, а кожен член Е називається ребром.
2.4: Застосування індукції та рекурсії в комбінаториці та теорії графів (вправи)
Цей розділ містить додаткові проблеми, пов'язані з матеріалами, розглянутими в розділі 2.

Мініатюра: креслення графіка. (Громадське надбання; АзаТот).

Дописувачі та атрибуція

Template:ContribBogart