Пер. с нем. — М.: Диалог-МИФИ, 1996. — 299 с. — ISBN 5-86404-071-1.
В данной первой части книги, состоящей из четырёх частей, основное
внимание уделено понятию информации и различным формам её
представления, ориентированным на машинную обработку. Подробно
рассматривается понятие алгоритма, свойства и классификация
алгоритмов, способы их формального описания и исполнения. Даются
общие сведения о языках программирования, их реализации и методах
программирования. Подробно рассматриваются аппликативные и
императивные языки программирования, а также
машинно-ориентированные языковые элементы. Большое внимание уделено
типичным для многих языков структурам данных, объявлениям функций,
процедур и типов данных, при этом особое внимание уделяется
рекурсивным объявлениям. При изложении материала систематически
делается акцент на его теоретические аспекты. Книга ориентирована
прежде всего на студентов университетов и ведущих технических
вузов, уделяющих большое внимание фундаментальности образования в
области информатики. Она будет весьма полезной и для преподавателей
предметов данного цикла.
Предисловие редактора перевода
Предисловие к русскому изданию
Предисловие Информация и её представление
Понятие "информация"
Пример информации и ее представления: высказывательные формы
Булевские термы
Булевская алгебра истинностных значений
Интерпретация булевских термов
Законы булевской алгебры и булевских термов
Применение законов для булевских термов: редукция
Информация и ее представление в нормальной форме
Переход от представления к информации
Преобразование представлений
Нормальные формы и однозначные нормальные формы
Последовательности литер
Формальные языки Вычислительные структуры и алгоритмы
К понятию "алгоритм"
Неформальные описания алгоритмов
Формальное описание алгоритма через за мену текстов
Детерминистические алгоритмы текстовых замен
Отображения, индуцируемые алгоритмами текстовых замен
Вычислительные структуры
Семейства функций и множеств как вычислительные структуры
Сигнатуры
Основные термы
Вычисления основных термов: схемы
Термы с (свободными) идентификаторами
Интерпретация термов с (свободными) идентификаторами
Термы с (свободными) идентификаторами как схемы
Алгоритмы как системы подстановки термов
Правила подстановки термов
Система подстановки термов
Алгоритмы подстановки термов
Корректность систем подстановки термов
Логика высказываний и логика предикатов
Логика высказываний
Логика предикатов Языки программирования и программирование
Синтаксис: описание формального языка с помощью БНФ
БНФнотация
Синтаксические диаграммы
Контекстные условия
Семантика
К реализации языков программирования
Методика программирования
Принципы программирования
Вычислительные структуры Аппликативные языки программирования
Элементы чисто аппликативных ЯП
Синтаксис выражений и примитивных вычислительных структур
Описание значений выражений
Константы и идентификаторы
Условные выражения
Применение функций
Связывание (свободных) идентификаторов: абстракция функций
Расширение аппликативных языков: объявления
Объявление элемента
Объявления функций
Рекурсивные объявления функций
Индуктивное толкование рекурсивных объявлений функций
Толкование через наименьшую неподвижную точку
Рекурсивные объявления функций в системах подстановки термов
Схема для рекурсивного объявления функции
Формы рекурсий
Линейная рекурсия
Повторная рекурсия
Каскадная рекурсия
Удаленная рекурсия
Взаимная рекурсия
Техника аппликативного программирования
Описание постановки задачи: спецификации
Обобщение постановки задачи через вложение
К структурированию от постановки задачи
Вывод рекурсий из спецификаций
Подавление параметров, подчиненные вычислительные предписания
Эффективность аппликативной программы
Документирование
Тестирование и интеграция программ
Техника доказательства для рекурсивных программ
Индукция и рекурсия
Частичная корректность
Доказательство терминированности Управляющие структуры, ориентированные на присваивание
Ориентированные на присваивание языковые элементы: операторы
Синтаксис
Программные переменные и присваивание
Состояния
Функциональное значение операторов
Операционная семантика операторов
Простые операторы
"Пустой" оператор nop
Незавершающийся оператор abort
Оператор присваивания
Производные операторы
Последовательная композиция
Условные операторы
Операторы цикла
Объявления переменных и блоки
Процедуры
Объявления процедур
Вызов процедуры
Глобальные переменные в процедурах
Рекурсивные процедуры
Разделы, связывания, видимость, продолжительность жизни
Техника программирования для императивных программ
Метод утверждений
Доказательство терминированности Объявления типов
Объявления типов
Скалярные элементы: перечисление
Прямое произведение: кортеж
Прямая сумма: вариантные типы
Частичные области
Массивы
Одномерные массивы
Массивы в императивных языках: селективные изменения
Многомерные массивы и общие типы индексов
Динамические и гибкие массивы
Конечные множества как вычислительные структуры Машинноориентированные языковые элементы: переходы и ссылки
Управление потоком
Метки и переходы
Диаграммы управления потоком
Ссылки и указатели Рекурсивные объявления типов
Вычислительные структуры вида последовательностей
Вычислительные структуры последовательностей
Ввод/вывод и внешние вычислительные структуры
Древовидные вычислительные структуры
Рекурсивные объявления типов
Индуктивное толкование рекурсивных объявлений типов
Толкование рекурсивных объявлений типов через неподвижную точку
Применение рекурсивных объявлений типов
Списки
Простые списки
Рекурсивно объявленные списковые типы
Реализация последовательностей в виде списков
Двунаправленные списки
Кольцевые списки
Обобщенные частичные структуры Литература
Предметный указатель
Предисловие к русскому изданию
Предисловие Информация и её представление
Понятие "информация"
Пример информации и ее представления: высказывательные формы
Булевские термы
Булевская алгебра истинностных значений
Интерпретация булевских термов
Законы булевской алгебры и булевских термов
Применение законов для булевских термов: редукция
Информация и ее представление в нормальной форме
Переход от представления к информации
Преобразование представлений
Нормальные формы и однозначные нормальные формы
Последовательности литер
Формальные языки Вычислительные структуры и алгоритмы
К понятию "алгоритм"
Неформальные описания алгоритмов
Формальное описание алгоритма через за мену текстов
Детерминистические алгоритмы текстовых замен
Отображения, индуцируемые алгоритмами текстовых замен
Вычислительные структуры
Семейства функций и множеств как вычислительные структуры
Сигнатуры
Основные термы
Вычисления основных термов: схемы
Термы с (свободными) идентификаторами
Интерпретация термов с (свободными) идентификаторами
Термы с (свободными) идентификаторами как схемы
Алгоритмы как системы подстановки термов
Правила подстановки термов
Система подстановки термов
Алгоритмы подстановки термов
Корректность систем подстановки термов
Логика высказываний и логика предикатов
Логика высказываний
Логика предикатов Языки программирования и программирование
Синтаксис: описание формального языка с помощью БНФ
БНФнотация
Синтаксические диаграммы
Контекстные условия
Семантика
К реализации языков программирования
Методика программирования
Принципы программирования
Вычислительные структуры Аппликативные языки программирования
Элементы чисто аппликативных ЯП
Синтаксис выражений и примитивных вычислительных структур
Описание значений выражений
Константы и идентификаторы
Условные выражения
Применение функций
Связывание (свободных) идентификаторов: абстракция функций
Расширение аппликативных языков: объявления
Объявление элемента
Объявления функций
Рекурсивные объявления функций
Индуктивное толкование рекурсивных объявлений функций
Толкование через наименьшую неподвижную точку
Рекурсивные объявления функций в системах подстановки термов
Схема для рекурсивного объявления функции
Формы рекурсий
Линейная рекурсия
Повторная рекурсия
Каскадная рекурсия
Удаленная рекурсия
Взаимная рекурсия
Техника аппликативного программирования
Описание постановки задачи: спецификации
Обобщение постановки задачи через вложение
К структурированию от постановки задачи
Вывод рекурсий из спецификаций
Подавление параметров, подчиненные вычислительные предписания
Эффективность аппликативной программы
Документирование
Тестирование и интеграция программ
Техника доказательства для рекурсивных программ
Индукция и рекурсия
Частичная корректность
Доказательство терминированности Управляющие структуры, ориентированные на присваивание
Ориентированные на присваивание языковые элементы: операторы
Синтаксис
Программные переменные и присваивание
Состояния
Функциональное значение операторов
Операционная семантика операторов
Простые операторы
"Пустой" оператор nop
Незавершающийся оператор abort
Оператор присваивания
Производные операторы
Последовательная композиция
Условные операторы
Операторы цикла
Объявления переменных и блоки
Процедуры
Объявления процедур
Вызов процедуры
Глобальные переменные в процедурах
Рекурсивные процедуры
Разделы, связывания, видимость, продолжительность жизни
Техника программирования для императивных программ
Метод утверждений
Доказательство терминированности Объявления типов
Объявления типов
Скалярные элементы: перечисление
Прямое произведение: кортеж
Прямая сумма: вариантные типы
Частичные области
Массивы
Одномерные массивы
Массивы в императивных языках: селективные изменения
Многомерные массивы и общие типы индексов
Динамические и гибкие массивы
Конечные множества как вычислительные структуры Машинноориентированные языковые элементы: переходы и ссылки
Управление потоком
Метки и переходы
Диаграммы управления потоком
Ссылки и указатели Рекурсивные объявления типов
Вычислительные структуры вида последовательностей
Вычислительные структуры последовательностей
Ввод/вывод и внешние вычислительные структуры
Древовидные вычислительные структуры
Рекурсивные объявления типов
Индуктивное толкование рекурсивных объявлений типов
Толкование рекурсивных объявлений типов через неподвижную точку
Применение рекурсивных объявлений типов
Списки
Простые списки
Рекурсивно объявленные списковые типы
Реализация последовательностей в виде списков
Двунаправленные списки
Кольцевые списки
Обобщенные частичные структуры Литература
Предметный указатель