Брой М. Информатика. Основополагающее введение. Часть 4. Теоретическая информатика, алгоритмы и структуры данных, логическое программирование, объектная ориентация

Пер. с нем. Н.П. Трифонова под ред. чл.-корр. РАН Л.Н.Королева. — М.: Диалог-МИФИ, 1998. — 224 с. — ISBN 3-540-58602-4; ISBN 5-86404-109-2.Первые три главы данной, заключительной части "Введения в информатику" посвящены основным теоретическим аспектам информатики: теории формальных языков (основные понятия отношений и графов), формальным языкам и их классификации по Хомскому, различным способам задания грамматик и их соотношениям, понятиям вычислимости и сложности вычислений. В гл. 4 рассматривается ряд классических алгоритмов (сортировка данных, нахождение путей в графах и др.) с оценкой их сложности, а также избранные структуры данных, ориентированные на хранение больших множеств данных, и эффективные методы работы с ними (в частности, специальные древовидные структуры и хэш-таблицы). Гл. 5 посвящена формализмам спецификаций, базам данных и информационным системам, а также — дополнительно к рассмотренным в предыдущих частях стилям программирования — кратко рассматривается логическое и объектно-ориентированное программирование. Наконец, в гл. 6 даются заключительные замечания к информатике, касающиеся её современного состояния и перспектив развития, а также обсуждаются некоторые специфичные аспекты информатики (правовые, социальные, экономические, философские и др.).Предисловие.
Формальные языки.
Отношения и графы.
Грамматики.
Грамматики типа 3 и конечные автоматы.
Контекстно-свободные языки и магазинные автоматы.
Контекстно-зависимые грамматики.
Вычислимость.
Гипотетические машины.
Рекурсивные функции.
Эквивалентность понятий вычислимости.
Разрешимость.
Теория сложности.
Мера сложности.
NP-полнота.
Эффективные алгоритмы для NP-полных проблем.
Эффективные алгоритмы и структуры данных.
Избранные алгоритмы.
Деревья.
Эффективное представление множеств.
Методы описаний в программировании.
Формализмы для спецификаций.
Базы данных и информационные системы.
Логическое программирование.
Объектно-ориентированное программирование.
Заключительные замечания к информатике.
Применения информатики.
Информатика и право.
Социальная компетенция информатиков.
Информатика и экономика.
Информатика, научная теория и философия.
К ответственности информатиков.
Литература.
Предметный указатель.