- •Программирование и алгоритмические языки. Курс за второй семестр. Абстрактные типы данных.
- •Задача о раскраске.
- •Перечисление последовательностей фиксированной длины.
- •Var I:tСтраны; c:tЦвет;
- •Два взгляда на диаграммы – графы и автоматы.
- •Деревья
- •Как сократить перебор с возвратом. Перечисление последовательностей переменной длины
- •Словарный порядок на последовательностях произвольной длины
- •Статическая реализация стеков.
- •Очереди. Статическая реализация.
- •Статическая реализация деревьев.
- •Автоматы как структуры данных
- •Статическая реализация графов. Проблема фрагментации памяти. Списочные структуры.
- •Общая схема реализации автомата как списка.
- •Обработка кучи.
- •Динамическая реализация абстрактных типов ссылками. Ссылочные типы Паскаля.
- •Ссылочные типы Паскаля. Синтаксис типов.
- •Объявление списочной структуры в Паскале.
- •Реализация стеков.
- •Реализация очередей.
- •Основные операции над списками.
- •Обработка деревьев. Деревья выражений.
- •Поиск атома.
- •Различные объединения типов. Записи типов с вариантами.
- •Создание дерева. Перевод из префиксной записи. Представление записи.
- •Анализ алгоритма вычисления. Дерево как последовательность ветвей.
- •Задача синтаксического анализа.
- •Графы-выражения.
- •Раздельное описание абстрактных типов. Модульное программирование.
- •Проблема с кратным использованием модулей.
- •Деревья как структуры данных.
- •Деревья поиска.
- •Поиск в дереве поиска.
- •Включение в дерево поиска.
- •Другие обходы дерева. Обход в ширину.
- •Рекурсивные процедуры и функции. Примеры применения.
- •Поиск в дереве.
- •Проблемы с семантикой рекурсии.
- •Введение в машинно-ориентированное (ссылочное) программирование. Оператор Goto.
- •Создание новых структурных операторов.
- •Формальная семантика goto и неструктурных программ.
- •Мини-Паскаль.
- •Представление сложных типов. Адресная арифметика.
- •Проблемы реализации ввода-вывода. Идея буферизации.
- •Реализация процедур read и write.
- •Реализация структур управления.
- •Путь наверх. Реализация процедур-подпрограмм.
- •Передача параметров.
- •Сохранение и восстановление значений. Соглашение о связях.
- •Введение в теоретическое программирование. Границы программирования. Принципиальная и практическая неразрешимость.
- •О формальной спецификации. Мир задачи как автомат.
- •Процедуры как функции на множестве состояний. Процедуры как преобразователи предикатов.
- •Универсальные методы решения задач.
Программирование и алгоритмические языки. Курс за второй семестр. Абстрактные типы данных.
Полезные при описании реальности, но отсутствующие в конкретном языке программирования типы данных, называют абстрактными ( по отношению к данному языку).
«Программы = алгоритмы (процедуры) + структуры данных»
Н. Вирт
Идею нисходящего проектирования – многошаговый процесс создания (или выбора существующих) специализированных математических языков описания задач (подзадач) – мы ранее применяли к структурам управления. Применение к структурам данных – этот процесс был, как правило, одношаговый. При решении действительно сложных задач процесс нисходящего проектирования продолжается и на выбор промежуточных структур данных, то есть в целом на создание промежуточных абстрактных типов.
Тип
Задача о раскраске.
Выяснить, можно ли данную карту правильно раскрасить данным количеством цветов. Если да, то предъявить все возможные раскраски. Раскраска правильная, если никакие две соседние страны не окрашены в один цвет.
Делаем первые выводы относительно определения типа данных.
type
tСтраны = 1..n; {Можно взять произвольный порядковый тип}
tКарта = array [tСтраны,tСтраны] of Boolean; {На этом типе обязана быть определена единственная функция}
var
карта: tКарта;
m:cardinal;
можно: boolean;
раскраска:tРаскраска; {Определение типа откладываем до определения операций, которые нужны в алгоритме}
Function Правильная (раскраска: tРаскраска):boolean;
{правильная:=i,jtСтраны (соседи(Карта, i,j) and (i<j) раскраска(i) раскраска j)}
{Стрелка – логическая связь – «если, то»}
{правильная:= }
Begin
result:=true;
i:=первая страна;
while (i<=последняя страна) and (Result) do
begin
j:=succ(i);
while (j<=последняя страна) and Result do
begin
if соседи (i,j) then
if раскраска(i) = раскраска (j) then Result:=false;
else j:=succ(j);
end;
i:=succ(i);
end;
end;
Begin
{Можно:= раскраска tРаскраска (раскраска - правильная}
можно:=false;
раскраска:=первая раскраска;
while not (конечная раскраска) do
begin
if правильная(карта, раскраска) then
begin
можно:=true;
write (Правильная раскраска);
end;
раскраска:=следующая раскраска;
end;
End.
Мы отождествляем тип tКарта с функцией “Соседи”, задавая её в виде булевского массива. Не забудь переименовать в алгоритме Соседи на Карта!
tРаскраска: tСтранаtЦвет
array[tСтрана] of tЦвет
Однако основной алгоритм требует, чтобы тип tРаскраска был порядковым. Нам необходима возможность перечислять раскраску.
Перечисление последовательностей фиксированной длины.
n циклов дали бы нужный порядок, но мы не можем выразить такой оператор синтаксически, однако это даёт идею того, в каком порядке можно перебирать последовательности (конечные функции) – в словарном (лексикографическом).
a=a1,…,an
b=b1,…,bn
a<b ai0<bi0, где i0 – наименьший символ i такой, что aibi и i<i0 ai=bi
Procedure Следующая ({var Раскраска: tРаскраска;var Кончились:boolean});
{Выдаёт раскраску, следующую за данной, кладёт «Кончились» в true, если таковой нет}