Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 636199)
Контекстум
Руконтекст антиплагиат система

Лекции по дискретной математике (1980,00 руб.)

0   0
АвторыВялый Михаил Николаевич, Подольский Владимир Владимирович, Рубцов Александр Александрович, Шварц Дмитрий Александрович, Шень Александр
ИздательствоИздательский дом ВШЭ
Страниц496
ID799826
Аннотация"Учебник написан по материалам курса ""Дискретная математика"", который читается студентам младших курсов факультета компьютерных наук НИУ ВШЭ. Темы этого курса являются частью базовой математической культуры и необходимы будущим математикам, программистам и специалистам в области анализа данных, но не входят в традиционно сложившиеся курсы начального математического цикла (математический анализ, алгебра, линейная алгебра). В книге излагаются начальные сведения из перечислительной комбинаторики, теории графов, теории чисел, теории множеств, теории вероятностей, теории игр, теории вычислимости. Не претендуя на полноценный охват какой-либо из упомянутых теорий, учебник дает введение в эти области, с одной стороны, достаточное для студентов соответствующих специальностей, а с другой –– позволяющее читать специализированную литературу.
Кому рекомендовано Книга будет полезной студентам младших курсов, изучающим курс дискретной математики преподавателям этой дисциплины а также более широкому кругу любителей математики."
ISBN978-5-7598-2212-7
УДК519.1
ББК22.176
Лекции по дискретной математике / М. Н. Вялый, В. В. Подольский, А. А. Рубцов, Д. А. Шварц, А. . Шень .— Эл. изд. — : Издательский дом ВШЭ, 2021 .— 496 с. — («Учебники Высшей школы экономики») .— 1 файл pdf : 496 с. — Москва : Изд. дом Высшей школы экономики, 2021. — (Учебники Высшей школы экономики). — Систем. требования: Adobe Reader XI либо Adobe Digital Editions 4.5 ; экран 10". — Текст : электронный. — ISBN 978-5-7598-2212-7 .— URL: https://rucont.ru/efd/799826 (дата обращения: 20.05.2024)

Предпросмотр (выдержки из произведения)

Лекции_по_дискретной_математике.pdf
Стр.5
Стр.6
Стр.7
Стр.8
Стр.9
Стр.10
Стр.11
Лекции_по_дискретной_математике.pdf
УДК 519.1 ББК 22.176 Л43 Рукопись подготовлена в рамках грантового проекта НИУ ВШЭ по изданию авторских учебников Национального исследовательского университета «Высшая школа экономики» В. А. Тиморин Авторы: доктор физико-математических наук, профессор факультета математики Рецензент: М. Вялый, В. Подольский, А. Рубцов, Д. Шварц, А. Шень Л43 Лекции по дискретной математике / М. Н. Вялый, В. В. Подольский, А. А. Рубцов, Д. А. Шварц и др. ; Нац. исслед. ун-т «Высшая школа экономики». — Эл. изд. — 1 файл pdf : 496 с. — Москва : Изд. дом Высшей школы экономики, 2021. — (Учебники Высшей школы экономики). — Систем. требования: Adobe Reader XI либо Adobe Digital Editions 4.5 ; экран 10". — Текст : электронный. ISBN 978-5-7598-2212-7 Учебник написан по материалам курса «Дискретная математика», который читается студентам младших курсов факультета компьютерных наук НИУ ВШЭ. Темы этого курса являются частью базовой математической культуры и необходимы будущим математикам, программистам и специалистам в области анализа данных, но не входят в традиционно сложившиеся курсы начального математического цикла (математический анализ, алгебра, линейная алгебра). В книге излагаются начальные сведения из перечислительной комбинаторики, теории графов, теории чисел, теории множеств, теории вероятностей, теории игр, теории вычислимости. Не претендуя на полноценный охват какой-либо из упомянутых теорий, учебник дает введение в эти области, с одной стороны, достаточное для студентов соответствующих специальностей, а с другой — позволяющее читать специализированную литературу. Книга будет полезной студентам младших курсов, изучающим курс дискретной математики; преподавателям этой дисциплины; а также более широкому кругу любителей математики. УДК 519.1 ББК 22.176 Электронное издание на основе печатного издания: Лекции по дискретной математике / М. Н. Вялый, В. В. Подольский, А. А. Рубцов, Д. А. Шварц и др. ; Нац. исслед. ун-т «Высшая школа экономики». — Москва : Изд. дом Высшей школы экономики, 2021. — 496 с. — (Учебники Высшей школы экономики). — ISBN 978-5-7598-1782-6. — Текст : непосредственный. В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации. ISBN 978-5-7598-2212-7 © Национальный исследовательский университет «Высшая школа экономики», 2021
Стр.5
СОДЕРЖАНИЕ Предисловие . . . . . . . . . . . ... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 11 Часть I. Начальные примеры .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 13 Лекция 1. Математическая индукция .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 15 1.1. Задача о раскраске плоскости . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... . 15 1.2. Общая схема доказательств по индукции . .. .. .. .. .. .. .. ... .. .. .. .. .. .. 18 1.3. Варианты рассуждений по индукции . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. . 21 1.3.1. С чего начинать? .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. 21 1.3.2. Сведение к меньшим . . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. 22 1.3.3. Переформулировка: принцип наименьшего числа .. .. .. .. .. .. .. . . 24 1.4. Как не надо . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... 24 1.5. Как догадаться, что доказывать? . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. 27 1.6. Доказательства по индукции и без индукции . . . . . . . . . . . . ... .. .. .. .. .. .. 30 1.7. Индукция и рекурсия ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. 33 1.8. Доказательства неравенств по индукции . . . . . . . . . . . . . . ... .. .. .. .. .. .. .. 36 1.8.1. Неравенство Бернулли .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. . 36 1.8.2. Среднее арифметическое и среднее геометрическое . .. .. .. .. .. .. 37 1.9. Пример из алгебры: системы однородных уравнений . . . . . . . ... .. .. .. .. . 40 1.10. Коды Грея . .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. . 43 1.11. Теорема Холла о представителях .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. 46 1.12. Задачи для самостоятельного решения . .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. 48 Лекция 2. Подсчёты . . . . . ... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 50 2.1. Правило суммы . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. .. . 50 2.2. Рекуррентное соотношение: пример . .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. . 54 2.3. Рекуррентное соотношение: число путей . . . . . . . . . . . . . ... .. .. .. .. .. .. .. . 57 2.4. Слова и правило произведения . . . . . . . . . . . . . . ... .. .. .. .. .. .. ... .. .. .. .. . 59 2.5. Выбор с ограничениями . .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... 63 2.6. Подсчёты с кратностью . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 65 2.7. Подмножества и числа сочетаний . .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. . 68 2.8. Ещё о числах сочетаний . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. . 70 2.8.1. Симметрия .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 71 2.8.2. Сумма чисел в строке . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. . 72 2.8.3. Знакочередующаяся сумма . . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. . 72 2.8.4. Снова о включениях и исключениях . . . ... .. .. .. .. .. .. ... .. .. .. .. 74 2.8.5. Пути, подмножества, слова . . . . . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. 75 2.8.6. Соседние числа в строке . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. . 77 2.8.7. Монеты и перегородки .. .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. . 78 2.9. Бином Ньютона и производящие функции ... .. .. .. .. .. .. .. ... .. .. .. .. .. 80 2.10. Числа Каталана .. .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. 89 2.10.1. Правильные последовательности скобок . . . . . . . . ... .. .. .. .. .. .. . 89 2.10.2. Рекуррентная формула . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 91 2.10.3. Вычисление с помощью отражений . .. .. .. .. .. .. .. ... .. .. .. .. .. . 93
Стр.6
Содержание 2.10.4. Вычисление с производящей функцией . .. .. .. .. ... .. .. .. .. .. .. . 95 2.10.5. Вычисление с теорией вероятностей и поворотами ... .. .. .. .. .. . 97 2.10.6. Доказательство по индукции с дробными параметрами . . . . . . . . . 98 2.10.7. Неассоциативные произведения, триангуляции и стековый калькулятор .. .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. 99 2.11. Что дальше? ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. 103 Лекция 3. Графы . . . . . . . ... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 105 3.1. Примеры . . . . . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. 105 3.1.1. Граф авиарейсов . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... . 105 3.1.2. Перестановка коней . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. . 106 3.1.3. Эйлер и мосты в Кёнигсберге . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. 108 3.1.4. Рукопожатия .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. 109 3.1.5. Задачи и решения . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. . 110 3.1.6. Разбор контрольной . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. 111 3.1.7. Знакомые и незнакомые . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. . 113 3.2. Неориентированные графы . . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. 116 3.2.1. Определение . .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. . 116 3.2.2. Соседи. Степени вершин ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. 117 3.2.3. Связные компоненты ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. 120 3.2.4. Расстояния. Простые пути . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. . 128 3.2.5. Деревья . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. .. 131 3.2.6. Полное бинарное дерево . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. . 134 3.3. Ориентированные графы . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 135 3.3.1. Определение . .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. . 135 3.3.2. Степени вершин . . . . . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. . 136 3.3.3. Пути и достижимость . .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. . 137 3.3.4. Достижимость и разрезы .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. 138 3.3.5. Компоненты сильной связности и ациклические графы .. .. .. . . . . 139 3.3.6. Графы преобразований . .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. . 142 3.4. Эйлеровы циклы . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 144 3.4.1. Определение . .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. . 144 3.4.2. Критерий существования ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. . 145 3.4.3. Последовательности де Брёйна .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. 146 3.4.4. Гамильтоновы циклы . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. 147 3.5. Двудольные графы . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. 148 3.5.1. Определение . .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. .. . 148 3.5.2. Двудольные графы и раскраска в два цвета . . . ... .. .. .. .. .. .. .. . 149 3.5.3. Степени вершин . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. 150 3.5.4. Паросочетания . . . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... 151 3.6. Клики и независимые множества . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... . 153 Лекция 4. Арифметика остатков .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 156 4.1. Чётные и нечётные числа .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. . 156 4.2. Деление на 3 и остатки . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. 157 4.3. Деление с остатком .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... . 158 4.4. Сравнения по модулю . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... . 161 4.5. Таблицы сложения и умножения по модулю N . . . . . ... .. .. .. .. .. .. ... .. 163 4.6. Обратимые остатки по модулю N .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 165 6
Стр.7
Содержание 4.7. Обратимые элементы и диофантовы уравнения . ... .. .. .. .. .. .. .. ... .. . 168 4.8. Алгоритм Евклида . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. . 169 4.9. Алгоритм Евклида и диофантовы уравнения . .. .. .. .. .. .. .. ... .. .. .. .. . 171 4.10. Однозначность разложения на множители . .. .. .. ... .. .. .. .. .. .. .. ... . 174 4.11. Китайская теорема об остатках . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. 176 4.12. Малая теорема Ферма . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. 178 4.13. Функция Эйлера и теорема Эйлера . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. 180 4.14. Что дальше? . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. . 182 Часть II. Основные конструкции .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 185 Лекция 5. Множества и логика .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 187 5.1. Основные свойства множеств и операции с множествами .. .. .. .. . . . . . . 187 5.2. Теоретико-множественные тождества . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. . 193 5.3. Логические переменные, логические связки . . . . . . . . . . . . . ... .. .. .. .. .. .. 195 5.4. Наблюдения .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. 199 5.5. Какие связки необходимы? ... .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. 202 5.5.1. Полнота дизъюнкции, конъюнкции и отрицания ... .. .. .. .. .. .. .. . 204 5.5.2. Полнота конъюнкции и отрицания . . . . . . . . . . . . . . . ... .. .. .. .. .. .. .. 205 5.5.3. Алгебраическое доказательство полноты .. .. .. .. .. .. .. . . . . . . . . . . 206 5.6. Формула включений-исключений .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. . 207 5.6.1. Первое доказательство . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. . 208 5.6.2. Второе доказательство . . . . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. . 209 5.6.3. Формула для симметрической разности . . . . . . . . . . ... .. .. .. .. .. .. 209 Лекция 6. Функции .. .. .. ... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 211 6.1. Пример . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. 211 6.2. Функции и связанные с ними понятия .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. 212 6.2.1. Терминология и обозначения .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. . 212 6.2.2. Образ множества, полный прообраз . .. ... .. .. .. .. .. .. .. ... .. .. .. 214 6.3. Декартово произведение множеств и графики функций .. .. .. .. .. .. .. . . 218 6.4. Инъекции, сюръекции и биекции . .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. 222 6.4.1. Определения . .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. . 222 6.4.2. Биекции и сравнение множеств . . . . . . . . . . . . . . . . ... .. .. .. .. .. .. .. . 224 6.5. Композиции функций ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. 227 6.5.1. Определение . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. . 227 6.5.2. Ассоциативность . .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. . 229 6.5.3. Обратная функция . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. 229 6.5.4. Степени композиций .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. 232 6.6. Подсчёты .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. . 233 6.7. Задачи для самостоятельного решения .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. . 235 Лекция 7. Отношения и их графы .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 238 7.1. Отношения в естественном языке .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. 238 7.2. Отношения с точки зрения математики . .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. 239 7.3. Свойства бинарных отношений . .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. 241 7.4. Графы, матрицы и бинарные отношения . .. .. .. .. ... .. .. .. .. .. .. .. ... .. . 243 7.5. Отношения эквивалентности . . . . . . . . . ... .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... 244 7.6. Композиция отношений . . . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. . 247 7.7. Отношения: что дальше? . . . . . . . . . . . . . . . ... .. .. .. .. .. .. ... .. .. .. .. .. .. .. 250 7
Стр.8
Содержание 7.8. Задачи для самостоятельного решения .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 251 Лекция 8. Мощность множеств .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 253 8.1. Равномощные множества ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. 253 8.1.1. Определение равномощности .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. 253 8.1.2. Свойства равномощности . .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. . 254 8.1.3. Примеры равномощных множеств . . . . . ... .. .. .. .. .. .. .. ... .. .. .. . 255 8.2. Счётные множества .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. . 257 8.2.1. Определение и простейшие примеры .. .. .. ... .. .. .. .. .. .. .. ... .. 257 8.2.2. Свойства счётных множеств . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. . 259 8.3. Несчётные множества . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. 263 8.3.1. Интервал и отрезок равномощны . . . . . ... .. .. .. .. .. .. .. ... .. .. .. . 263 8.3.2. Добавление счётного множества . .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. 264 8.3.3. Числа и последовательности . . . . . . . . . . . . . . ... .. .. .. .. .. .. ... .. .. . 265 8.3.4. Отрезок и квадрат . .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. . 266 8.4. Диагональный аргумент Кантора и сравнение мощностей . . . . . . . . . . . . . . 267 8.4.1. Несчётность отрезка .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. . 267 8.4.2. Сравнение мощностей . . . . . . . . . ... .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 270 8.5. Что дальше? . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. 274 Лекция 9. Упорядоченные множества .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 276 9.1. Отношения порядка . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. 276 9.1.1. Отношения строгого частичного порядка .. .. .. .. .. ... .. .. .. .. .. .. 276 9.1.2. Строгие и нестрогие порядки .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. 277 9.2. Примеры . .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... 278 9.3. Операции над частично упорядоченными множествами . .. .. .. ... .. .. .. . 280 9.4. Какие порядки считать «одинаковыми»? . . . . . . . . . . . . ... .. .. .. .. .. .. ... . 282 9.5. Конечные линейные порядки . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. . 284 9.6. Порядки и индукция .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. . 284 9.7. Антицепи . .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... 286 Лекция 10. Вероятность: первые шаги .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 289 10.1. Элементарная теория вероятностей: определения . .. .. .. .. ... .. .. .. .. . 290 10.2. Вероятность объединения событий .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. 299 10.3. Вероятностный метод . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. 302 10.4. Условные вероятности ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. . 304 10.5. Случайная величина, математическое ожидание . . . . ... .. .. .. .. .. .. .. .. 312 10.6. Частота орлов при подбрасывании монеты и биномиальные коэффициенты . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. . 321 10.7. Большие уклонения: неравенство Чернова . . . . . . . . . ... .. .. .. .. .. .. .. .. 325 10.8. Подробности для любознательных . . . . . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... 327 10.8.1. Ещё одна элементарная оценка отношения биномиальных коэффициентов . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. 327 10.8.2. Другое доказательство неравенства Чернова . .. .. .. .. .. .. ... .. . 328 Лекция 11. Комбинаторные игры .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 331 11.1. Позиции . .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. . 331 11.2. Стратегии . .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. .. . 335 11.3. Разбор с конца . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. 338 11.4. Симметричные стратегии . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. 343 8
Стр.9
Содержание 11.5. Ним . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. . 346 11.6. Сумма игр и функция Шпрага –– Гранди . .. .. ... .. .. .. .. .. .. .. ... .. .. .. 350 Часть III. Вычислимость .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 357 Лекция 12. Разрешающие деревья .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 359 12.1. Задача об угадывании числа. Деление пополам. Мощностная нижняя оценка .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. 359 12.2. Формализация модели ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. . 361 12.3. Угадывание числа, неадаптивный вариант задачи ... .. .. .. .. .. .. .. ... . 362 12.4. Ограниченные модели разрешающих деревьев. Сортировка, взвешивания, булевы функции . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. 363 12.5. Рассуждение с противником .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. . 367 Лекция 13. Булевы схемы и формулы .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 371 13.1. Булевы схемы .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. 372 13.2. Формулы .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. . 383 Лекция 14. Алгоритмическая неразрешимость .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 389 14.1. Игра FRACTRAN . .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. 389 14.2. Что утверждается? . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. .. .. . 390 14.3. Отступление о процессорах . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. . 391 14.4. Кодирование . . . . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. 392 14.5. Класс вычислимых функций . . . . . . . . . . . . . . . . ... .. .. .. .. .. .. ... .. .. .. .. . 393 14.6. Определение вычислимости? .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 394 14.7. Компромисс .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... . 395 14.8. Композиция вычислимых функций . .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. 396 14.9. Не все функции вычислимы .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. . 397 14.10. Неразрешимость проблемы остановки . . . . . . . . . . . ... .. .. .. .. .. .. ... .. . 398 14.11. Самоприменимость . . . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. 400 14.12. Перечисление останавливающихся программ . . . . ... .. .. .. .. .. .. .. ... . 401 14.13. Как доказать неразрешимость? .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. 402 14.14. Язык программирования для доказательства теоремы Конвея . ... .. .. 403 14.15. Сведение проблемы остановки: от программ к пасьянсам ... .. .. .. .. . 407 Лекция 15. Вычислимые функции, разрешимые и перечислимые множества .. 410 15.1. Примеры вычислимых функций . .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. . 413 15.2. Не все функции вычислимы (повторение) . . . ... .. .. .. .. .. .. .. ... .. .. .. 417 15.3. Разрешимые множества . . . . . . . . . . . . . ... .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 419 15.4. Перечислимые множества . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 420 15.5. Вычислимость и конечные объекты . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. 427 15.6. Универсальная вычислимая функция . . . . . . . . . . . . . . . . ... .. .. .. .. .. .. .. . 429 15.7. Главная универсальная функция .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. 434 15.8. Теорема Райса –– Успенского . .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. . 439 15.9. Теорема о неподвижной точке . .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... . 443 15.10. Решения задач . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. . 446 Лекция 16. Машины Тьюринга .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 451 16.1. Определения . .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. ... .. .. .. .. .. .. .. 451 16.2. Тезис Чёрча –– Тьюринга . . . . . . . . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... 455 16.3. Машины Тьюринга и свойства вычислимых функций . .. .. .. .. .. .. ... .. . 456 9
Стр.10
Содержание 16.4. Использование машин Тьюринга в доказательствах . .. .. .. .. .. ... .. .. . 458 16.5. Композиция функций, вычислимых по Тьюрингу, и «уборка мусора» . . 459 16.6. Многоленточные машины Тьюринга . .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... 462 16.7. Моделирование многоленточной МТ на одноленточной ... .. .. .. .. .. .. . 465 16.8. Универсальная машина Тьюринга . . . ... .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 468 16.9. Универсальная трёхленточная машина для одноленточных машин . . . . . 470 16.10. Соответствие между абстрактной теорией алгоритмов и МТ .. .. .. .. .. 473 16.11. Машины Тьюринга в доказательствах неразрешимости .. .. .. .. . . . . . . . 477 16.11.1. Задача достижимости на графе подстановок слов .. .. .. .. .. ... 477 16.11.2. Неразрешимость задачи достижимости для графа подстановок слов . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... 479 16.12. Решения задач . . . ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. . 482 Литература .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 493 Об авторах .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. 494 10
Стр.11

Облако ключевых слов *


* - вычисляется автоматически
Антиплагиат система на базе ИИ