Основы теории алгоритмов (теория) / Основаная часть / Содержание
.docО.Н. Паулин. Основы теории алгоритмов
СОДЕРЖАНИЕ
|
ПРЕДИСЛОВИЕ …………….….………………………………………………………
|
3 |
|
ВВЕДЕНИЕ …………………………………………………….………………………. В.1. Интуитивное определение понятия алгоритма ……….…………..……… B.2. Виды вычислений и алгоритмов …………………………………….………. В.3. Базовые фрагменты схем алгоритмов …………………………….……….. Контрольные вопросы …..………………………………….……….……………….
|
4 4 8 11 14 |
|
Глава 1.Простейшие алгоритмы и вычислительные процесСы ... 1.1. Разветвления в алгоритмах ……………………………………..……………. 1.1.1. Примеры алгоритмов, линейного и с разветвлением ……………….. 1.1.2. Общие вопросы организации разветвлений в СА ……………….…… 1.2. Циклы в алгоритмах ……………..….…………………….……………………. 1.2.1. Примеры циклических алгоритмов………………………………………. 1.2.2. Общие вопросы организации циклов ………………………..…………. 1.3. Логические алгоритмы …………………………………………………………. 1.3.1. Задача Поиск пути в лабиринте ……………………………………….. 1.3.2. Задача Ханойские башни ……………………………………………….. Заключение ……………………………………………………………………………. Контрольные вопросы. Упражнения ……………………………………………….
|
15 15 15 20 27 27 36 43 43 47 49 50
|
|
Глава 2. Модели вычислений …………………………………….…………... 2.1. Ассоциативные исчисления …………………………………………..……….. 2.1.1. Определения, операции, свойства ………………………………………. 2.1.2. Примеры ассоциативных исчислений …………………………………... 2.1.3. Нормальный алгоритм Маркова …………………………………………. 2.2. Вычислимые и рекурсивные функции ………….…………………..……….. 2.2.1. Построение класса примитивно-рекурсивных функций …….………. 2.2.2. Построение класса общерекурсивных функций ……………………… 2.3. Модели дискретной обработки информации …….…………………..…….. 2.3.1. Конечные автоматы ………………………………………….…………….. 2.3.2. Машина Тьюринга, её свойства и особенности ……………….….…… 2.4. Уточнение понятия алгоритма. Тезис Чёрча ………..……..…...………….. Заключение …………………………………………..……….…..………….……….. Контрольные вопросы. Упражнения ……………….……………….……………..
|
52 54 54 57 59 61 62 67 73 73 80 91 94 95
|
|
Глава 3. Представление данных в памяти ЭВМ …………………….. 3.1. Понятие структуры данных ………………………………...………………….. 3.2. Списки и их разновидности ………………….……………..…………………. 3.3. Представление множеств в машине …………...……………….…………… 3.4. Графы и их представление в машине ...……………….……………………. Заключение ……………………………….………….………………….……………. Контрольные вопросы. Упражнения ……….………….……..……………………
|
96 96 104 111 114 127 128
|
|
Глава 4. АНАЛИЗ И ПОСТРОЕНИЕ АЛГОРИТМОВ ………………………. 4.1. Комбинаторные вычисления на конечных множествах ………….……….. 4.1.1. Введение в комбинаторику ……….……………………………………… 4.1.2. Асимптотики …………………………………………………………………. 4.1.3. Рекуррентные соотношения ……………………….……………………… 4.1.4. Производящие функции …………………………………………….……... 4.2. Оценки сложности алгоритмов ..……………………….....………………….. 4.3. Методы повышения эффективности алгоритмов …………………………. 4.3.1. Рекурсия ……………………………………………………………………… 4.3.2. Приём разделяй и властвуй …………………………………..……….. 4.3.3. Принцип балансировки ……………………………………………………. 4.3.4. Динамическое программирование ……………………………….……… 4.3.5. Алгоритмы с возвратом …………………………………………………… 4.4. Построение алгоритмов ……………………………..…………………………. 4.4.1. Как разрабатывать алгоритм …………………………………..…………. 4.4.2. Пример построения алгоритма …………………………………………… Заключение ………………………..…………………………………..……………… Контрольные вопросы. Упражнения ……………………………………….………
|
129129 129 130 132 134 136 139 139 149 151 155 156 158 158 169 175 175
|
|
ЛИТЕРАТУРА ……………………………………………………….………….………..
|
176
|
|
Приложение а. Правила начертания схем алгоритмов ..………….………… Приложение Б. Основные виды наборов и их свойства ……………………... Приложение В. Краткое руководство для решения задач ...…...…….………
|
177 179 184
|