Математические основы информатики

Description

Титульный лист ОТ АВТОРОВ 1. ЯЗЫК ТЕОРИЙ ПЕРВОГО ПОРЯДКА 1.1. Язык логики высказываний 1.2. Язык логики предикатов первого порядка 2. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ И КОМБИНАТОРИКИ 2.1. Множества, способы их задания. Подмножества 2.2. Операции над множествами. Основные равенства 2.3. Упорядоченная пара. Декартово произведение множеств. Отношения 2.4. Свойства бинарных отношений. Отношение эквивалентности. 2.5. Функции. Счетные множества 2.6. Размещения и размещения с повторениями 2.7. Сочетания и сочетания с повторениями 2.8. Формула бинома Ньютона 2.9. Рекуррентные соотношения и их решения 2.10. Формула включений и исключений 2.11. Производящие функции 2.12. Неориентированные графы 3. ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ 3.1. Основные понятия 3.2. Важные примеры грамматик 3.3. ?-грамматики и автоматы 3.4. Некоторые свойства грамматик 3.5. Иерархия языков 3.6. Грамматический разбор 3.7. КС-языки и синтез языков программирования 3.8. Аксиоматические грамматики 4. АЛГОРИТМЫ 4.1. Интуитивное понятие алгоритма и необходимость его уточнения 4.2. Машины Тьюринга 4.3. Функции, вычислимые по Тьюрингу. Тезис Тьюринга 4.4. Операции над машинами Тьюринга 4.5. Частично-рекурсивные функции (класс Ч) 4.6. Классы? и Τ 4.7. Одна просто определяемая невычислимая функция 4.8. Алгоритмически неразрешимые проблемы 4.9. Универсальные машины Тьюринга и функции 4.10. Некоторые общие теоремы теории алгоритмов 4.11. к-Ленточные машины Тьюринга, k > 1 (детерминированные и недетерминированные) 4.12. Классы Ρ и ΝΡ. Проблема Ρ =?ΝΡ. TVP-полные и NP-трудные проблемы 4.13. 0 машинно-независимой теории сложности вычислений 4.14. Перечисление рекурсивно-перечислимых множеств 4.15. Конечные автоматы 4.16. Приближенные (эвристические) алгоритмы ЛИТЕРАТУРА СОДЕРЖАНИЕ Обложка