Дудаков С.М., Карлов Б.Н. Математическое введение в информатику

Учебник. — Тверь: Тверской государственный университет (ТвГУ), 2017. — 320 с.В пособии освещаются теоретические вопросы программирования: связь и эквивалентность различных языков программирования, доказательство корректности программ, вычислительная сложность алгоритмов.
Учебник адресован, прежде всего, студентам младших курсов, обучающихся по направлениям укрупненных групп 01.03.00 «Математика и механика», 02.03.00 «Компьютерные и информационные науки», 09.03.00 «Информатика и вычислительная техника».Предисловие.
Ко второму изданию.
К первому изданию.
Введение.
Основные понятия.
Исторические сведения.
Свойства алгоритмов и языков программирования.
Примеры алгоритмов.
Некоторые математические сведения.
Алгебра и теория множеств.
Графы.
Математическая логика.
Структурированные программы.
Синтаксис.
Семантика.
Свойства структурированных программ.
Простые программы.
Подстановка.
Программы с метками.
Синтаксис.
Семантика.
Построение программ с метками.
Построение структурированных программ.
Блок-схемы.
Корректность структурированных программ.
Исчисления.
Исчисление Хоара.
Корректность циклов.
Примеры формальных выводов.
Исчисление предусловий.
Существование слабейших предусловий.
Невозможность автоматической верификации.
Подпрограммы, функциональное программирование.
Подпрограммы.
Графы зависимости, списки и деревья вызовов.
Функциональное программирование.
Удаление подпрограмм.
Корректность подпрограмм.
Вычислительная сложность.
Хранение чисел.
Вычисления.
Время и память вычисления.
Предметный указатель.
Список литературы.