Барский А.Б., Шилов В.В. Теория цифрового компьютера

М.: Форум, 2019. — 305 с. — ISBN 978-5-8199-0774-0.Исследованы проблемы типизации и структуризации данных. Введено определение алгоритма, отражающее важное свойство альтернативности. В классической теории алгоритмов выделены положения, обеспечивающие два принципа современного цифрового компьютера: программное управление выполнением программы и размещение выполняемой программы в памяти наряду с другими данными. Рассмотрены возможные структуры алгоритмов, алгоритмически неразрешимые проблемы, сложность алгоритмов, абстрактные модели компьютеров. Изучены логические основы компьютера, способы представления и преобразования данных в различных системах счисления и выполнение базовых арифметических и логических операций.
Исследованы возможности параллельного выполнения операций. Приведены функции операционной системы по обеспечению режимов использования компьютера, системы прерывания, многоканального доступа, виртуальной памяти. Дано понятие "теговой" архитектуры, способствующей повышению информационной безопасности. Рассмотрены "фон-Неймановские" и "не-фон-Неймановские" архитектуры.
Соответствует требованиям Федерального государственного образовательного стандарта высшего образования последнего поколения.
Для студентов бакалавриата и магистратуры, аспирантов, преподавателей информационно-технологических и экономических вузов, для исследователей и разработчиков цифровых вычислительных средств.Предисловие.
Введение.
Типы и структуры данных.
Типы данных.
Понятие типа.
Иерархический подход в типизации данных.
Простые типы данных.
Литерный тип.
Целый тип.
Вещественный тип.
Логический тип.
Перечислимый тип.
Интервальный тип.
Абстрактные типы данных.
2. Структурированные типы и основные структуры данных.
Массив.
Строка.
Запись.
Множество.
Объединение (запись с вариантами).
Таблица.
Последовательности.
Разновидности последовательностей.
Файл.
Текстовые файлы.
Бестиповые файлы.
Буферизация.
Конечный буфер.
Кольцевой (бесконечный) буфер.
Стек.
Очередь.
Концепция динамической памяти.
Ссылочный тип данных.
Рекурсивный тип.
Списки.
Дерево.
Граф.
Экзотические типы данных.
Календарный тип (Date).
Тип данных «Денежный».
Пустые типы данных.
Поддержка типов — теговая архитектура.
Краткие итоги.
Ключевые термины.
Вопросы и задания для самоконтроля.
Элементы теории алгоритмов.
Понятие алгоритма.
Базовые структуры алгоритмов.
Итерационные алгоритмы.
Рекурсивные алгоритмы.
Задача о лабиринте.
Основы абстрактной теории алгоритмов.
Нормальные алгоритмы Маркова.
Проблема разрешимости.
Алгоритмически неразрешимые проблемы.
10.Сложность алгоритмов.
Понятие сложности алгоритма.
Полиномиальные и экспоненциальные алгоритмы.
Сложность итеративных и рекурсивных алгоритмов.
Классы сложности.
Полиномиальная сводимость и А/Р-полные задачи.
Приближенное решение А/Р-сложных задач.
Стратегии решения задач.
Метод «разделяй и властвуй».
Метод последовательных приближений.
Метод наискорейшего спуска.
Метод обратного прохода.
Метод динамического программирования.
Метод поиска с возвратом.
Метод выделения подцелей.
Метод моделирования.
Нейросетевой метод ассоциативных вычислений.
Модели элементарных машин.
Машина Поста.
Универсальная машина Тьюринга.
РАМ-машина (машина с произвольным доступом к памяти).
Краткие итоги.
Ключевые термины.
Вопросы и задания для самоконтроля.
Информационные, логические и операционные основы цифрового компьютера.
Немного истории.
Два принципа ЭВМ.
Кодирование информации и системы счисления.
Текстовая (символьная) информация.
Числовая информация.
Перевод чисел из одной системы счисления в другую.
Представление числовой информации.
Диапазон представления чисел.
Представление логических значени.
Логические основы компьютера.
Комбинационные схемы и цифровые автоматы.
Булевы функции и логические элементы.
Система логических элементов.
Кодирование чисел для выполнения операций.
Прямой код.
Обратный код.
Дополнительный код.
Выполнение операций.
Сложение и вычитание чисел с плавающей запятой.
Умножение и деление чисел.
Неарифметические операции над кодами.
Логические операции.
Система и форматы команд.
Стек. Безадресная система команд.
Конвейеры операций.
Скалярные конвейеры выполнения операций.
Умножение с помощью пирамиды сумматоров.
Векторные конвейеры. «Зацепление» векторов.
Структура цифрового компьютера.
Арифметико-логическое устройство.
Устройство управления.
Организация оперативной памяти.
ВЗУ и периферия.
Режимы использования вычислительных систем.
Мультипрограммирование.
Пакетный режим.
Режим разделения времени.
Виртуальная память. Динамическое распределение памяти.
Способы адресации.
Страничная организация памяти.
Алгоритмы замещения страниц.
Сегментация физической памяти.
Защита памяти.
Поддержка языков высокого уровня. Теговая архитектура.
Проблема повышения уровня языка пользователя.
Поддержка типов — теговая архитектура.
Стековый механизм выполнения процедур.
Обработка массивов.
Выполнение циклов.
Ускорение условных переходов.
Параллельное выполнение операций.
Динамическое распараллеливание в многофункциональном АЛУ.
Параллельная обработка стека в решающем поле.
«Длинное командное слово» и EPIC-архитектура.
Параллельное выполнение условных операторов.
«Фон-Неймановские» и «не-фон-Неймановские» архитектуры.
Компромиссная модель «data flow».
Структура и программирование.
Виртуализация ресурса.
Дисциплина обращения к памяти данных.
Микропроцессор — основа элементно-конструкторской базы компьютерной системы.
Микропроцессор в основе центрального процессора системы.
Микропроцессоры в основе функциональных устройств цифрового компьютера.
Способы комплексирования модулей в компьютерной системе.
Краткие итоги.
Ключевые термины.
Вопросы и задания для самоконтроля.
Заключение.
Глоссарий основных терминов.
Библиографический список.