| Предисловие | 3 |
| 1. Я3ЫК ТЕОРИЙ ПEPBOГО ПОРЯДКА | 4 |
| 1.1. Язык, логики высказываний | 4 |
| l.1.1. Логические операции | 5 |
| 1.1.2. Основные равносильности. Тавтологии | 7 |
| 1.1.3. Логическое следствие | 10 |
| 1.2. Язык логики предикатов первого порядка | 15 |
| l.2.1. Формулы логики предикатов первого порядка. Интерпретации | 16 |
| 1.2.2. Равносильные формулы. Приведенная и нормальная формы | 20 |
| 2. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ И КОМБИНАТОРИКИ | 22 |
| 2.1. Множества, способы их задания. Подмножества | 22 |
| 2.2. Операции над множествами. Основные равенства | 25 |
| 2.3. Упорядоченная пара. Декартово произведение множеств. Отношения | 28 |
| 2.4. Свойства бинарных отношений. Отношение эквивалентности | 29 |
| 2.5. Функции. Счетные множества | 32 |
| 2.6. Размещения и размещения с повторениями | 36 |
| 2.7. Сочетания и сочетания с повторениями | 37 |
| 2.8. Формула бинома Ньютона | 41 |
| 2.9. Рекуррентные соотношения и их решения | 44 |
| 2.10. Формула включений и исключений | 49 |
| 2.11. Производящие функции | 54 |
| 2.12. Неориентированные графы | 60 |
| 3. ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ | 69 |
| 3.1. Основные понятия | 69 |
| 3.2. Важнейшие примеры грамматик | 72 |
| 3.3. А-грамматики и автоматы | 74 |
| 3.4. Некоторые свойства грамматик | 75 |
| 3.5. Иерархия языков | 77 |
| 3.6. Грамматический разбор | 79 |
| 3.7. КС-языки и синтез языков программирования | 82 |
| 3.8. Аксиоматические грамматики | 85 |
| 4. АЛГОРИТМЫ | 87 |
| 4.1. Индуктивное понятие алгоритма и необходимость его уточнения | 87 |
| 4.2. Машины Тьюринга | 89 |
| 4.3. Функции, вычислимые по Тьюрингу. Тезис Тьюринга | 93 |
| 4.4. Операции над машинами Тьюринга | 96 |
| 4.5. Частично-рекурсивные функции (класс Ч) | 99 |
| 4.6. Классы Ч и Т | 104 |
| 4.7. Одна просто определяемая невычислимая функция | 106 |
| 4.8. Алгоритмические неразрешимые проблемы | 108 |
| 4.9. Универсальные машины Тьюринга и функции1 | 111 |
| 4.10. Некоторые общие теоремы теории алгоритмов | 114 |
| 4.11. k –Ленточные машины Тьюринга, (детермированные и недетермированные) | 120 |
| 4.12. Классы P и N Р . Проблема P =?NP . NР-полные и NР-трудные проблемы | 125 |
| 4.13. О машинно-независимой теории сложности вычислений | 130 |
| 4.14. Перечисление рекурсивно-перечислимых множеств | 134 |
| 4.15. Конечные автоматы | 135 |
| 4.15.1. Автоматы Мура и Мили | 136 |
| 4.15.2. Эквивалентность автоматов Мили и Мypa | 137 |
| 4.15.3. Множества слов, вычислимые в реальное время | 139 |
| 4.16. Приближенные (эвристические) алгоритмы | 140 |
| 4.16.1.Оценки качества приближенных алгоритмов | 142 |
| 4.16.2. Примеры приближенных алгоритмов | 144 |
| ЛИТЕРАТУРА | 147 |