Программирование - Математические основы, средства, теория - Лавров С.С.

Название: Программирование - Математические основы, средства, теория.
Автор: Лавров С.С.
    Современное программирование излагается как искусство заставить компьютер решить задачу, возникшую перед человеком. Даны единые основания математики и программирования, краткие сведения из области графов, теории вероятностей и информации (в ее математическом толковании). Приведены основные понятия и конструкции современных языков программирования. Рассмотрен ряд вопросов теории программирования с упором на математическую семантику языковых конструкций.

Содержание
Введение
1. Математические основы
1.1. Формальные языки
1.1.1. Неформальный взгляд на формализацию
1.1.2. Алфавиты, слова, языки
1.1.3. Структура формальных теорий
1.2. Логические формальные теории
1.2.1. Язык
1.2.2. Интерпретации
1.2.3. Две точки зрения на математику
1.2.4. Значения формул
1.2.5. Примеры
1.2.6. Выполнимость и общезначимость
1.2.7. Некоторые общезначимые формулы
1.2.8. Теоремы об истинности и общезначимости
1.3. Исчисление высказываний
1.3.1. Аксиоматика
1.3.2. Теорема о дедукции
1.3.3. Некоторые леммы о выводимости
1.3.4. Теорема о полноте
1.3.5. Другие аксиоматики исчисления высказываний
1.4. Формальные теории первого порядка
1.4.1 Аксиоматика
1.4.2. Теорема о дедукции
1.4.3. Некоторые теоремы об истинности и общезначимости
1.4.4. Непротиворечивость
1.4.5. Теоремы о выводимости
1.4.6. Теории первого порядка с равенством
1.5. Теория множеств
1.5.1. Основные понятия
1.5.2. Пары и кортежи (n-ки)
1.5.3. Отношения
1.5.4. Графы и деревья
1.5.5. Соответствия и отображения
1.5.6. Отношения порядка
1.5.7. О парадоксах теории множеств
1.5.8. Еще раз о двух математиках
1.6. Вероятности и информация
1.6.1. Случайные события
1.6.2. Случайные величины
1.6.3. Об измерении информации
1.6.4. Случайные процессы
1.7. Теория вычислимости
1.7.1. Введение
1.7.2. Язык Лисп
1.7.3. Модель арифметики
1.7.4. Моделирование машины Тьюринга
1.7.5. Семантика рекурсивных функций
1.7.6. Теория неподвижной точки
1.7.7. На общем фоне
Библиографическая справка
2.Основные понятия и конструкции языков программирования
2.1. Программы
2.1.1. Данные и информация
2.1.2. Языки программирования
2.1.3. Описание синтаксиса языков
2.1.4. Описание семантики
2.2. Структуры данных
2.2.1. Простые значения и их представление
2.2.2. Составные значения и их типы
2.3. Структуры действий
2.3.1 Переменные и их объявления
2.3.2. Операции и выражения
2.3.3. Операторы и структура программы
2.3.4. Работа со ссылками
2.4. Более сложные средства
2.4.1 Процедуры
2.4.2. Алгоритмы над графами
2.4.3. Файлы и операторы для работы с ними
2.4.4. Примечания в программах
2.5. Старые новые веяния
2.5.1. О функциональном стиле программирования
2.5.2. Объектно-ориентированное программирование
3. Анализ свойств программ
3.1. Операторные схемы
3.1.1. Оценка трудоемкости алгоритмов
3.1.2. Доказательство свойств программ
3.1.3. Завершаемость алгоритмов
3.1.4. Структурированные схемы
3.1.5. Экономия памяти
3.2. Формализация семантики языков программирования
3.2.1 Модельный язык и его операционная семантика
3.2.2. Исчисление программ
3.2.3 Состояния и преобразователи состояний
3.2.4. Целые и логические выражения
3.2.5. Преобразователи состояний для операторов
3.2.6 Преобразователи предикатов
3.2.7. Преобразователи предикатов для операторов
3.2.8. Обоснование правил деривационной семантики
3.2.9. Операторные схемы, рекурсия и циклы
3.3. Денотационная семантика составных значений и указателей
3.3.1. Векторы, записи и ссылки
3.3.2 Состояния, имена, выражения
3.3.3. Объявления, генераторы и присваивания
3.3.4. Блоки
3.3.5. Простые переменные как указатели
3.3.6. Динамические типы
3.3.7. Преобразователи предикатов для присваивания
3.4. Денотационная семантика процедур и функций
3.4.1. Нерекурсивные процедуры и функции
3.4.2. Рекурсивные процедуры
3.4.3. Преобразователи предикатов для процедур
3.5. Послесловие. За что боролись?
Решения упражнений
Список литературы.
Интерпретации.
Уже не раз выше было сказано, что формальные теории интересны не столько сами по себе, сколько из-за возможности сопоставить символам и выражениям некоторые содержательные понятия. В общих чертах говорилось и о том, как это делается. Теперь в нашем изложении металогики настало время дать более точные определения.
Будем говорить, что задана интерпретация I некоторой формальной теории Т, если:
1)  указано некоторое множество D (конечное или бесконечное, но не пустое), называемое предметной областью интерпретации I;
2)  каждой предметной константе ai теории Т (если они есть) сопоставлен некоторый элемент аi предметной области D;