Первые три главы данной, заключительной части Введения в информатику посвящены основным теоретическим аспектам информатики: теории формальных языков (основные понятия отношений и графов), формальным языкам и их классификации по Хомскому, различным способам задания грамматик и их соотношениям, понятиям вычислимости и сложности вычислений. В гл. 4 рассматривается ряд классических алгоритмов (сортировка данных, нахождение путей в графах и др.) с оценкой их сложности, а также избранные структуры данных, ориентированные на хранение больших множеств данных, и эффективные методы работы с ними (в частности, специальные древовидные структуры и хэш-таблицы). Гл. 5 посвящена формализмам спецификаций, базам данных и информационным системам, а также - дополнительно к рассмотренным в предыдущих частях стилям программирования - кратко рассматривается логическое и объектно-ориентированное программирование. Наконец, в гл. 6 даются заключительные замечания к информатике, касающиеся ее современного состояния и перспектив развития, а также обсуждаются некоторые специфичные аспекты информатики (правовые, социальные, экономические, философские и др.).
Author(s): Брой М.
Publisher: Диалог-МИФИ
Year: 1998
Language: Russian
Pages: 242
City: М.
Титул ......Page 4
Аннотация ......Page 5
ПРЕДИСЛОВИЕ ......Page 6
1. ФОРМАЛЬНЫЕ ЯЗЫКИ ......Page 8
1.1.1. Двухместные отношения ......Page 9
1.1.2. Пути в графах и образование замыканий ......Page 13
1.2. Грамматики ......Page 21
1.2.1. Редукционные и генерационные грамматики ......Page 28
1.2.2. Иерархия языков по Хомскому ......Page 32
1.2.3. Структурные графы и структурные деревья ......Page 34
1.2.4. Тупики и бесконечные трассы вывода ......Page 40
1.3. Грамматики типа 3 и конечные автоматы ......Page 45
1.3.1. Регулярные выражения ......Page 46
1.3.2. Конечные автоматы ......Page 47
1.3.3. Эквивалентность форм представления ......Page 51
1.3.4. Регулярные выражения, конечные автоматы и языки типа 3 ......Page 55
1.3.5. Минимальные автоматы ......Page 63
1.4. Контекстно-свободные языки и магазинные автоматы ......Page 65
1.4.1. БНФ-нотация ......Page 66
1.4.2. Магазинные автоматы ......Page 67
1.4.3. Магазинные автоматы и контекстно-свободные языки ......Page 70
1.4.4. Нормальная форма Грейбах ......Page 73
1.4.5. 1Л1(к)-языки ......Page 76
1.4.6. LL(k)-грамматики ......Page 82
1.4.7. Метод рекурсивного спуска ......Page 85
1.5. Контекстно-зависимые грамматики ......Page 86
2. ВЫЧИСЛИМОСТЬ ......Page 88
2.1.1. Машины Тьюринга ......Page 90
2.1.2. Регистровые машины ......Page 98
2.2.1. Примитивно-рекурсивные функции ......Page 100
2.2.2. ц-рекурсивные функции ......Page 108
2.2.3. Общие объявления рекурсивных функций ......Page 113
2.3.1. Эквивалентность ц-вычислимости и тьюринг-вычислимости ......Page 117
2.3.2. Эквивалентность RM- и тьюринг-вычислимости ......Page 119
2.3.3. Тезис Чёрча ......Page 121
2.4.1. Невычислимые функции ......Page 123
2.4.2. Разрешимые предикаты ......Page 124
2.4.3. Рекурсивные и рекурсивно-перечислимые множества ......Page 125
3.1.1. Временна’я сложность ......Page 128
3.1.2. Ленточная сложность ......Page 130
3.1.3. Временная и ленточная сложность задач ......Page 132
3.1.4. Полиномиальная и недетерминированная полиномиальная временная сложность ......Page 137
3.1.5. Бэктрекинг-недетерминированность в языках программирования ......Page 138
3.2.1. Проблема выполнимости для булевских выражений ......Page 143
3.2.2. Другие NP-полные проблемы ......Page 147
3.3. Эффективные алгоритмы для NP-полных проблем ......Page 148
3.3.1. Искусный просмотр больших древовидных структур ......Page 149
3.3.2. Альфа-бета-поиск ......Page 152
3.3.3. Динамическое программирование ......Page 157
3.3.4. Гриди-алгоритмы ......Page 160
4.1.1. Сложность алгоритмов сортировки ......Page 162
4.1.2. Пути в графах ......Page 165
4.2.1. Упорядоченные, ориентированные и отсортированные деревья ......Page 168
4.2.2. Представление деревьев массивами ......Page 169
4.2.3. AVL-деревья ......Page 170
4.2.4. В-деревья ......Page 171
4.3. Эффективное представление множеств ......Page 172
4.3.1. Вычислительная структура множеств с доступом по ключу ......Page 173
4.3.2. Представление множеств AVL-деревьями ......Page 174
4.3.3. Метод хэширования ......Page 183
5.1.1. Абстракция в спецификации ......Page 187
5.1.2. Спецификация абстрактных вычислительных структур ......Page 189
5.1.3. Спецификация функций ......Page 193
5.1.4. Спецификация операторов ......Page 194
5.2. Базы данных и информационные системы ......Page 197
5.2.1. Моделирование отношений сущность/связь ......Page 198
5.2.2. Диаграммы сущность/связь ......Page 200
5.2.3. Харакгеризация связей ......Page 201
5.2.4. К применению систем баз данных ......Page 202
5.2.6. Запросы к базам данных и их изменение ......Page 203
5.3. Логическое программирование ......Page 204
5.3.1. Решение задач в логическом программировании ......Page 205
5.3.2. Выполнение логических программ ......Page 207
5.3.3. Унификация ......Page 210
5.4. Объектно-ориентированное программирование ......Page 214
6. ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ К ИНФОРМАТИКЕ ......Page 224
6.1. Применения информатики ......Page 226
6.3. Социальная компетенция информатиков ......Page 229
6.4. Информатика и экономика ......Page 230
6.5. Информатика, научная теория и философия ......Page 231
6.6. К ответственности информатиков ......Page 232
ЛИТЕРАТУРА ......Page 233
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ......Page 236
Содержание ......Page 238
