- •Программирование и алгоритмические языки. Курс за второй семестр. Абстрактные типы данных.
- •Задача о раскраске.
- •Перечисление последовательностей фиксированной длины.
- •Var I:tСтраны; c:tЦвет;
- •Два взгляда на диаграммы – графы и автоматы.
- •Деревья
- •Как сократить перебор с возвратом. Перечисление последовательностей переменной длины
- •Словарный порядок на последовательностях произвольной длины
- •Статическая реализация стеков.
- •Очереди. Статическая реализация.
- •Статическая реализация деревьев.
- •Автоматы как структуры данных
- •Статическая реализация графов. Проблема фрагментации памяти. Списочные структуры.
- •Общая схема реализации автомата как списка.
- •Обработка кучи.
- •Динамическая реализация абстрактных типов ссылками. Ссылочные типы Паскаля.
- •Ссылочные типы Паскаля. Синтаксис типов.
- •Объявление списочной структуры в Паскале.
- •Реализация стеков.
- •Реализация очередей.
- •Основные операции над списками.
- •Обработка деревьев. Деревья выражений.
- •Поиск атома.
- •Различные объединения типов. Записи типов с вариантами.
- •Создание дерева. Перевод из префиксной записи. Представление записи.
- •Анализ алгоритма вычисления. Дерево как последовательность ветвей.
- •Задача синтаксического анализа.
- •Графы-выражения.
- •Раздельное описание абстрактных типов. Модульное программирование.
- •Проблема с кратным использованием модулей.
- •Деревья как структуры данных.
- •Деревья поиска.
- •Поиск в дереве поиска.
- •Включение в дерево поиска.
- •Другие обходы дерева. Обход в ширину.
- •Рекурсивные процедуры и функции. Примеры применения.
- •Поиск в дереве.
- •Проблемы с семантикой рекурсии.
- •Введение в машинно-ориентированное (ссылочное) программирование. Оператор Goto.
- •Создание новых структурных операторов.
- •Формальная семантика goto и неструктурных программ.
- •Мини-Паскаль.
- •Представление сложных типов. Адресная арифметика.
- •Проблемы реализации ввода-вывода. Идея буферизации.
- •Реализация процедур read и write.
- •Реализация структур управления.
- •Путь наверх. Реализация процедур-подпрограмм.
- •Передача параметров.
- •Сохранение и восстановление значений. Соглашение о связях.
- •Введение в теоретическое программирование. Границы программирования. Принципиальная и практическая неразрешимость.
- •О формальной спецификации. Мир задачи как автомат.
- •Процедуры как функции на множестве состояний. Процедуры как преобразователи предикатов.
- •Универсальные методы решения задач.
Мини-Паскаль.
(Паскаль, из которого выброшено «всё лишнее»).
Данные и сами программы хранятся в памяти. Реально существует много типов памяти: внешняя память (файлы) и оперативная, которая, в свою очередь, имеет много подтипов.
Память со случайным доступом,
Регистровая память и т.д.
В любом случае память можно представлять как набор двоичных разрядов (битов). Однако самой мелкой порцией памяти, доступной для обработки (адресуемая), является слово. Обычно это группа из восьми битов, или байт.
Bit=0..1;
Byte=array[0..7] of bit;
Word=byte;
Математические языки не содержат явных описаний, но лишь действия по выделению памяти, которые мы можем трактовать логически как применение оператора new, а реализовать пропуском участка памяти.
Goto begin
память
под
переменные
begin
Данные и программы хранятся в одной памяти, информация о структуре (типе данных) хранится в нашей собственной памяти. Все слова основной (оперативной) памяти занумерованы, номер слова называется его абсолютным адресом.
Замечание: На практике программист на машинном языке очень редко использует абсолютные адреса (отсчёт от начала памяти), но относительные адреса (смещение, отсчёт от некоторого фиксированного адреса, который называется базовым).
базовый
смещение
Это даёт возможность операционной системе разместить программу в любом свободном на этот момент участке памяти.
С точки зрения ЭВМ, вне зависимости от носителя любая информация есть последовательность слов (byte). Единственным типом нашего языка будет то, что раньше мы называли ячейками памяти – последовательности или одномерные массивы машинных слов. Этот тип мы будем называть двоичным полем. Поля задаются адресом начала поля и его длиной.
начало длина
///////////////////////////
Память в целом, конечно, - тоже двоичное поле.
{var Mem:field}
Можно считать, что это единственная переменная нашего языка. Собственно машинные языки допускают, конечно, запись данных и команд (операторы машинных языков) лишь в двоичной записи.
Близкие к машинным языкам языки ассемблера разрешают использование символьных имён полей и символьных кодировок команд (то есть язык ассемблера – ориентированная на человека форма машинного языка). В отличие от Паскаля и других языков высокого уровня имеется однозначное соответствие между командами машинного и языка ассемблера.
Конечно, все переменные – это подполе основного поля.
Пример синтаксиса: А[10] – десять машинных слов, лежащих по адресу А.
Может ли наш единственный тип заменить все типы данных? В принципиальном плане (в теории), если игнорировать конечность памяти, то, конечно, да!
Двоичный тип универсален. Любой другой тип можно смоделировать (реализовать) в нём, по крайней мере, хотя бы одним способом. На деле таких способов много. Они называются форматами (представление данных и команд).
Достаточно понять, что символьный тип можно смоделировать двоичными полями, поставив в соответствие каждому символу некоторое двоичное поле (обычно байт или два). Символьный тип универсален: любое значение любого типа имеет какую-то запись в какой-то системе обозначений.
На практике важна не только возможность, но и эффективность такого представления: для разных задач могут быть эффективными разные представления. Для числовых типов альтернативными символьному являются представления в двоичной системе счисления.
Записью числа в k-ичной системе счисления называется последовательность кодов от 0 до k-1.
m n
n=∑ aiki (n=∑ ai2i – для двоичной)
i=0 i=0
Упражнение. Написать алгоритм перевода числа из k-ичной в «нормальную» (десятеричную) и обратно.
0 1 0 1=5
1*20+0*21+1*22+0*23=5
В зависимости от того, занимает ли число фиксированное или переменное количество слов, существуют фиксированные и переменные форматы. Для указания формата фиксированной длины достаточно лишь указания адреса.
Для простоты будем считать, что мы будем использовать форматьы только фиксированной длины и знать значения констант: cSizeOfInteger, cSizeOfChar, cSizeOfReal и так далее, которые измеряются в байтах.
Понятие формата определено не только для данных, но и для команд, причём для каждого формата, например, числового, имеются свои операции.