29 Информатика. Вводный курс: В 2-х ч. Ч. 2: Пер. с нем.— М.: Мир, 1990. —423 с., ил.
ISBN 5-03-002100-0
Учебный курс, представляющий собой перевод с 3-го, полностью переработанного и расширенного издания, написанного известными специалистами (ФРГ). (Второе немецкое издание было переведено на русский (М.: Мир, 1976).) Изложение отличается глубокой методической проработанностью материала и применением концептуального подхода к преподаванию основ информатики. Фундаментальные понятия программирования вводятся в книге как исходные, получают затем формализацию и раскрываются в виде конструкций языков программирования разного уровня. Много содержательных и изящных примеров решения конкретных задач с использованием алгола-68 и паскаля.
В ч. 2 входят гл. 5—8, приложения, литература и указатели.
Для студентов, изучающих программирование, научных работников различных специальностей, использующих ЭВМ в своей работе.
Оглавление
Вступление .............................. 326
Глава 5. Блочная структура и динамическое распределение
памяти....................328
5.1. Блоки и распределение памяти..........328
5.1.1. Блочная структура............. 331
5.1.2. Магазинное распределение памяти.......333
5.1.3. Память с делением на слова......... 335
5.1.4. Относительная адресация........... 336
5.1.5. Массивы с динамически устанавливаемыми границами индексов............... 337
5.1.6. Заключительные замечания.......... 341
5.2. Процедуры и блочная структура.......... 341
5.2.1. Включение процедур в блочную структуру .... 341
5.2.2. Дерево блочной структуры, дополненное стрелками вызова..................345
5.2.3. Дерево динамической блочной структуры .... 349
5.2.4. Статические и динамические цепочки ссылок . . . 351
5.2.5. Динамическое распределение памяти при наличии процедур.................352
Глава 6. Внешняя память с внешним миром, структуры данных, организация памяти ....... 354
! 6.1. Технические характеристики устройств внешней памяти
и ввода/вывода ................. 355
6.1.1. Память с прямым доступом..........355
6.1.2. Память с непрямым доступом.........355
6.1.3. Единицы передачи и обмена.........359
6.2. Функциональное описание внешней памяти и устройств
ввода/вывода ................. 362
6.2.1. Перфокарты и колоды перфокарт, перфоленты: носители однократного использования ...... 364
6.2.1.1................... 365
6.2.1.2................... 366
6.2.2. Память на магнитной лепте с зонами переменной длины: носитель многократного использования с последовательным доступом к зонам переменно:"! длины 367
6.2.2.1................... 367
6.2.2.2................... 368
6.2.2.3................... 370
6.2.2.4................... 370
6.2.2.5................... 372
6.2.3. Память на магнитной ленте и на магнитных дисках "* ;., . с фиксированным разбиением на блоки: носители
многократного использования с последовательным доступом к фиксированным блокам, структурированная память................372
6.2.4. Память на магнитных дисках: носитель многократного использования с вращательным доступом . . 374 6.3. Введение новых вычислительных структур......374
6.3.1. Подструктуры.............. . 375
6.3.2. Операционное обогащение..........378
6.3.3. Образование пар и произвольных наборов .... 381
6.3.3.1..................381
6.3.3.2..................382
6.3.3.3...................385
6.3.3.4...................386
6.3.4. Вариантные образования...........387
6.3.5. Рекурсивное определение вычислительных структур: рекурсивные структуры данных........ 389
6.3.5.1. Стеки...............390
6.3.5.2. Бинарные деревья с размеченными листьями 391
6.3.5.3. Размеченные бинарные деревья ..... 392
6.3.5.4. Произвольные деревья с размеченными листьями..............393
6.3.5.5. Алгоритмы на рекурсивных структурах данных................394
6.3.6. Термы и диаграммы . . ..........395
6.3.6.1. Построение и обработка термов.....396
6.3.6.2. Деревья Канторовича и вилочные картинки 396
6.3.6.3. Термы и коробочные диаграммы ..... 400
6.3.6.4. Использование закона ассоциативности . .401
6.4. Организация данных: списки и указатели......403
6.4.1. Списки..................403
6.4.1.1. Ссылки............. . 403
6.4.1.2. Бесконечные списки..........407
6.4.2. Структурированная память..........411
6.4.2.1. Вычисляемые обозначения переменных . .411
6.4.2.2. Переход от составных объектов к структурированной памяти......... 415
6.4.2.3. Запрет отождествлений, побочные эффекты 417
6.4.3. Указатели................ 417
6.4.3.1. Сцепление указателей.........418
6.4.3.2. Объявление сорта указателя.......419
6.4.3.3. Создание переменных и указателен .... 420
6.4.3.4. Равенство указателей......... 423
6.4.4. Элементы сцеплений............423
6.4.4.1.................. . 424
6.4.4.2...................425
6.4.4.3.................. . 426
6.5. Реализация различных типов структурированной памяти
с помощью указателей..............426
6.5.1. Реализация стеков.............426
6.5.1.1. Стек как односвязанный список.....427
6.5.1.2. Сцепление двух односвязанных списков . . 428
6.5.1.3. Процедуры модуля СТЕК........430
6.5.2. Реализация последовательностей.......431
6.5.2.1. Последовательности как линейные двусвя-занные списки............432
6.5.2.2. Копирование линейных двусвязанных списков 434
6.5.2.3. Процедуры с последовательностями переменных...............437
6.5.3. Реализация деревьев с размеченными листьями . . 437
6.5.3.1. Бинарные деревья с размеченными листьями как списки с вариантными указателями . . 437
6.5.3.2. Произвольные деревья с размеченными листьями как списки с вариантными указателями...............439
6.6. Реализация структурированной памяти с помощью линейной памяти..................443
6.6.1. Разбросанное распределение памяти......443
6.6.2. Последовательное распределение памяти .... 444
Глава 7. Формальные языки..............446
7.1. Отношения и формальные системы.........446
7.1.1. Бинарные отношения и ориентированные графы . . 447
7.1.1.1. Теоретико-множественные свойства отношений ................448
7.1.1.2. Произведение двух отношений...... 449
7.1.1.3. Обращение отношений.........450
7.1.1.4. Максимальные и наибольшие, минимальные
и наименьшие элементы.........451
7.1.1.5. Рефлексивность............451
7.1.1.6. Транзитивность............452
7.1.1.7. Замыкания.............454
7.1.1.8. Классы эквивалентности....... . 456
7.1.2. Нётеровы и конфлюэнтные отношения.....458
7.1.2.1. Пути................ 458
7.1.2.2. Нётеровы отношения и графы......458
7.1.2.3. Замыкания нётеровых отношений.....459
7.1.2.4. Нередуцируемые элементы, тупиковые пути 460
7.1.2.5. Недетерминистический алгоритм редукции . 461
7.1.2.6. Конфлюэнтные отношения, единственность нормальных форм........... 462
7.1.2.7. Свойство Чёрча — Россера.....• . 464
7.1.3. Формальные языки: общие понятия.......465
7.2. Формальные языки над последовательностями символов 467
7.2.1. Согласованные системы редукций......467
7.2.2. Полутуэвские системы............469
7.2.3. Полутуэвские алгоритмы...........472
7.2.4. Языки Хомского и грамматики Хомского.....474
7.2.4.1. Грамматики составляющих....... 476
7.2.4.2. Контекстно-свободные грамматики Хомского 479
7.2.4.3. Регулярные грамматики........ 484
7.2.4.4. Конечные грамматики......... 488
7.2.5. Бэкусова нотация и обобщённая бэкусова нотация 489
7.2.5.1. Варианты..............489
7.2.5.2. Синтаксические диаграммы.......490
7.2.5.3. Знак итерации............492
7.2.5.4. Обобщённые синтаксические диаграммы . . 493
7.2.5.5. Добавление и удаление нетерминальных символов................495
7.2.6. Регулярные выражения........... 497
7.2.6.1. . . Г............... 498
7.2.6.2....................498
7.2.7. Подстановка грамматик . , •........499
7.3. Графы редукции и деревья редукции........501
7.3.1. Двудольные графы.............501
7.3.2. Графы и деревья редукции..........502
7.3.3. Построение графов редукции.........504
7.3.4. Однозначность...............506
7.3.5. Критерий однозначности...........508
7.3.6. Структурные грамматики...........510
7.4. Проблема анализа........•......512
7.4.1. Тупики.................513
7.4.1.1. Отсечение тупиков.......... 513
7.4.1.2. КС-грамматика с конфлюэнтным отношением подстановки.............515
7.4.1.3. Тупики в регулярных грамматиках .... 516
7.4.2. Методы последовательного анализа для регулярных грамматик...............517
7.4.2.1. Переходы состояний.......... 517
7.4.2.2. Теорема Клини об эквивалентности .... 521
7.4.2.3. Конечные автоматы..........522
7.4.3. Методы последовательного анализа для КС-грамматик ..................524
7.4.3.1. Переходы состояний магазинной памяти . . 524
7.4.3.2. Автоматы с магазинной памятью.....526
7.4.3.3. LR (б)-грамматики...........528
7.4.4. Методы последовательного анализа сверху-вниз . . 529
7.4.4.1. Обратные переходы состояний......530
7.4.4.2. LL(k) -грамматики...........531
7.4.5. Метод рекурсивного спуска..........532
7.5. Вычислимость и разрешимость..........536
Глава 8. Определение синтаксиса и семантики алгоритмических языков •................ 540
8.1. Синтаксис алгоритмических языков.........540
8.1.1. Синтаксическое описание составных объектов . . . 546
8.1.2. Синтаксическое описание деревьев Канторовича . 549
8.2. Операционная семантика.............550
8.2.1. Строение формул и вычисление их значений . . . 551
8.2.2. Частичная определимость...........554
8.2.3. Нестрогие операции.............556
8.2.4. Недетерминизм...............557
8.2.5. Семантика передачи параметров в подпрограммах 558
8.2.6. Операционная семантика рекурсии.......560
8.2.7. Редукционные машины............563
8.3. Семантика состояний.......•......563
8.3.1. Исчисление состояний по Маккарти.......563
8.3.1.1...................564
8.3.1.2...................565
8.3.1.3...................566
8.3.2. Исчисление утверждений по Флойду, Хоару и Дейкстре.................567
8.3.2.1. Аксиома присваивания.........оо/
8.3.2.2. Аксиома композиции.........570
8.3.2.3. Аксиомы для условных операторов . . . .571
8.3.2.4. Аксиома операторов цикла .......573
8.3.2.5. Некоторые общие правила.......576
8.3.2.6. Верификация программ . .......577
8.3.2.7. Переходы и инварианты циклов.....580
8.4. Математическая семантика............580
8.4.1. Теория неподвижных точек..........582
8.4.1.1. Теория неподвижных точек для рекурсии . 582
8.4.1.2. Теория неподвижных точек в исчислении слабейших предусловий..........585
8.4.1.3. Рекурсивное определение семантики алгоритмических языков...........585
8.4.2. Абстрактные типы (данных).........586
8.4.2.1. Сигнатурные графы..........587
8.4.2.2. Термальная алгебра абстрактного типа . . 588
8.4.2.3. Вычислительные структуры как конечно-порождённые модели абстрактного типа . . .591
8.4.2.4. Примеры полиморфных типов......593
8.4.3. Абстрактные типы и характеризация базовых вычислительных структур............ 596
8.4.3.1...................597
8.4.3.2...................597
8.4.3.3...................598
8.4.3.4...................599
8.4.4. Абстрактные типы и описания синтаксиса и семантики языков программирования........599
8.4.4.1...................600
8.4.4.2...................602
8.4.4.3...................605
8.4.4.4...................606
Приложение А. Системы счисления .......... 608
А.1. Позиционные системы счисления и перевод целых чисел из одной системы счисления в другую 608
А.2. Представление отрицательных чисел.....610
А.З. Четыре основные арифметические операции . .611 А.4. Числа с плавающей запятой........612
Приложение В. Теория информации Шеннона .... 614
8.1. Дискретизация..............614
8.1.1. Развёртка.............614
8.1.2. Квантование............618
8.2. Вероятностная теория информации......619
8.2.1. Шенноновские сообщения.......620
8.2.2. Количество информации........621
8.2.3. Пропускная способность канала .... 631
8.2.4. Надёжность кода..........633
Приложение С. Соответствия и функции......... 635
С.1. Некоторые специальные свойства соответствий . 635
С.1.1. Функции..............635
С.1.2. Отображения............637
С. 1.3. Многозначные функции........637
С.1.4. Представление соответствий и функций . . 638 С.2. Диаграммы для соответствий и функций . . . 639 С.З. Возведение в степень для множеств.....641
Приложение D. Устройства ввода/вывода данных • . . . 642
D.I. Требования и возможности ......... 642
D.2. Вывод.................643
D.2.I. Устройства посимвольной печати .... 643
D.2.2. Устройства построчной печати.....644
D.2.3. Графические устройства........646
D.2.4. Экранные устройства.........647
D.2.5. Речевой вывод...........649
D.3. Ввод.................649
D.3.I. Клавиатуры...........650
D.3.2. Точечный ввод с дисплея.......650
D.3.3. Устройства считывания маркировок . . . 651 D.3.4. Устройства считывания со стандартных
формуляров............652
Приложение Е. К истории информатики . • . .....656
ЕЛ. Введение................636
Е.1.1. Лейбниц.............657
ЕЛ.2. Корни информатики.........659
Е.2. История цифровых и символьных вычислений . . 659
Е.2.1. Цифровые вычисления........659
Е.2.1.1. Механизация вычислений .... 660 Е.2.1.2. Вычисления в двоичной системе
счисления..........661
Е.2.1.3. Вычисления над числами с плавающей запятой........663
Е.2.2. Символьные вычисления.......663
Е.2.2.1. Криптография........664
Е.2.2.2. „Искусственный интелект" .... 666
Е.2.2.3. Логическое исчисление.....669
Е.З. История связи..............670
Е.3.1. Передача сообщений.........670
Е.3.2. Принцип двоичного кодирования .... 671 Е.3.3. Теория кодирования и теория информации,
теория экстраполяции.........672
Е.3.4. Регулирование...........673
Е.4. Автоматы и алгоритмы..........674
Е.4.1. Принцип автомата..........674
Е.4.2. Программное управление.......675
Е.4.3. Алгоритмы.............676
Е.4.4. Алгоритмические языки........678
Е.4.5. Рекурсивность...........679
Литература........................681
Синтаксические диаграммы для использованных в книге версий алгола-68
и паскаля....................685
Предметно-именной указатель........•........704
Содержание части 1....................734
Цена: 250руб.
