Курс за второй семестр. Абстрактные типы данных СодержаниеЗадача раскраски.Делаем первые выводы относительно определения типа данных.Перечисление последовательностей фиксированной длины.Два взгляда на диаграммы – графы и автоматы.Х – выделенная переменная, произвольный массив. Остальные переменные не определены. Выход: любое состояние, в котором ХКак сократить перебор с возвратом. Перечисление последовательностей переменной длиныСловарный порядок на последовательностях произвольной длиныПереход к следующей раскраске при новом определении словарного порядкаСтатическая реализация стеков.Очереди. Статическая реализация.Get(q:tQueue;var x:T)Статическая реализация деревьев.Автоматы как структуры данныхСтатическая реализация графов. Проблема фрагментации памяти.Общая схема реализации автомата как списка.Обработка кучи.Динамическая реализация абстрактных типов ссылками.Синтаксис типов.Реализация очередей.Обработка деревьев. Деревья выражений.Задача по вычислениюЗаписи типов с вариантами.Создание дерева. Перевод из префиксной записи.Анализ алгоритма вычисления.Задача синтаксического анализа.Шаблоном атомаФормальным вычислениемРаздельное описание абстрактных типов.Проблема с кратным использованием модулей.Деревья как структуры данных.Деревья поиска.Другие обходы дерева. Обход в ширину.Рекурсивные процедуры и функции.Граф называется деревомРекурсивная версия задачи о вычисленииПоиск в дереве.Поиск в дереве поискаПример с факториаломПроблемы с семантикой рекурсии.Функциональным программированиемВведение в машинно-ориентированное (ссылочное) программирование.Создание новых структурных операторов.Формальная семантикаПредставление сложных типов.Проблемы реализации ввода-вывода.Реализация процедурРеализация структур управления.Путь наверх.Передача параметров.Сохранение и восстановление значений.Границы программирования. Принципиальная и практическая неразрешимость.О формальной спецификации.Процедуры как функции на множестве состояний.Задача поискаУниверсальные методы решения задач.
