Информатика. Введение в компьютерные науки

В учебнике подробно рассмотрены математическое понятие алгоритма, рекурсивные алгоритмы и рекурсивные структуры данных, алгоритмы сортировки и поиска. Изложены основы теории сложности алгоритмов, задач, элементы теории формальных языков. Приведены многочисленные алгоритмы на языке Паскаль. Отдельный раздел посвящен архитектуре компьютеров. Системы команд, организация вычислений, иерархия памяти рассмотрены в историческом развитии от первоначальных решений до перспективных разработок. Архитектурные решения поясняются на математических моделях. Для студентов вузов, обучающихся по направлению «Прикладная математика и информатика». Может использоваться в школах с углубленным изучением информатики и математики, а также всеми, кто хочет постичь основы информатики как точной науки.

Г л а в а 1. Введение в теорию алгоритмов

• 1.1. Интуитивное понятие алгоритма. Свойства алгоритмов. Понятие об исполнителе алгоритма
• 1.2. Точное понятие алгоритма. Классические формализации
• 1.3. Понятие об алгоритмической неразрешимости
• 1.4. Развитие понятия алгоритма
• 1.5. Методы разработки алгоритмов

Г л а в а 2. Рекурсивные алгоритмы

• 2.1. Вычислимые функции
• 2.2. Рекурсия и математическая индукция
• 2.3. Реализация механизма рекурсии
• 2.4. Рекурсия и итерация

Г л а в а 3. Рекурсивные данные

• 3.1. Рекурсивно определенные типы данных
• 3.2. Линейные списки
• 3.3. Деревья
• 3.4. Графы

Г л а в а 4. Анализ сложности алгоритмов

• 4.1. Понятие сложности алгоритма
• 4.2. Основные методы и приемы анализа сложности
• 4.3. Сложность операций с бинарными деревьями
• 4.4. Оптимизация алгоритмов

Г л а в а 5. Классы сложности задач

• 5.1. Разрешимые и неразрешимые задачи
• 5.2. Сложность задачи. Основные понятия.
• 5 .3. Пограничная полоса. Класс NP
• 5.4. If NP <> P then NP := P «объединение» NPC «объединение» NPI

Г л а в а 6. Сортировка и поиск

• 6.1. Сортировка массивов
• 6.2. Сортировка последовательных файлов
• 6.3. Поиск. Хеширование

Г л а в а 7. Формальные языки

• 7.1. Принципы построения формальных языков
• 7.2. Классификация формальных языков
• 7.3. Описание синтаксиса языка с помощью металингвистических формул и синтаксических диаграмм

Г л а в а 8. Общие сведения об ЭВМ

• 8.1. Понятие архитектуры ЭВМ
• 8.2. Упрощенная типовая схема однопроцессорной ЭВМ
• 8.3. Понятие системы команд
• 8.4. Типы данных, поддерживаемые аппаратурой

Г л а в а 9. Особенности архитектур машин разных поколений

• 9.1. Поколения ЭВМ
• 9.2. Вычислительные машины нетрадиционной архитектуры

Г л а в а 10 Организация памяти и конвейерная обработка

• 10.1. Иерархия запоминающих устройств
• 10.2. Механизмы преобразования виртуального адреса в физический адрес
• 10.3. Методы ускорения обработки потока данных и команд

Г л а в а 11. Лабораторный практикум