- •Программирование и алгоритмические языки. Курс за второй семестр. Абстрактные типы данных.
- •Задача о раскраске.
- •Перечисление последовательностей фиксированной длины.
- •Var I:tСтраны; c:tЦвет;
- •Два взгляда на диаграммы – графы и автоматы.
- •Деревья
- •Как сократить перебор с возвратом. Перечисление последовательностей переменной длины
- •Словарный порядок на последовательностях произвольной длины
- •Статическая реализация стеков.
- •Очереди. Статическая реализация.
- •Статическая реализация деревьев.
- •Автоматы как структуры данных
- •Статическая реализация графов. Проблема фрагментации памяти. Списочные структуры.
- •Общая схема реализации автомата как списка.
- •Обработка кучи.
- •Динамическая реализация абстрактных типов ссылками. Ссылочные типы Паскаля.
- •Ссылочные типы Паскаля. Синтаксис типов.
- •Объявление списочной структуры в Паскале.
- •Реализация стеков.
- •Реализация очередей.
- •Основные операции над списками.
- •Обработка деревьев. Деревья выражений.
- •Поиск атома.
- •Различные объединения типов. Записи типов с вариантами.
- •Создание дерева. Перевод из префиксной записи. Представление записи.
- •Анализ алгоритма вычисления. Дерево как последовательность ветвей.
- •Задача синтаксического анализа.
- •Графы-выражения.
- •Раздельное описание абстрактных типов. Модульное программирование.
- •Проблема с кратным использованием модулей.
- •Деревья как структуры данных.
- •Деревья поиска.
- •Поиск в дереве поиска.
- •Включение в дерево поиска.
- •Другие обходы дерева. Обход в ширину.
- •Рекурсивные процедуры и функции. Примеры применения.
- •Поиск в дереве.
- •Проблемы с семантикой рекурсии.
- •Введение в машинно-ориентированное (ссылочное) программирование. Оператор Goto.
- •Создание новых структурных операторов.
- •Формальная семантика goto и неструктурных программ.
- •Мини-Паскаль.
- •Представление сложных типов. Адресная арифметика.
- •Проблемы реализации ввода-вывода. Идея буферизации.
- •Реализация процедур read и write.
- •Реализация структур управления.
- •Путь наверх. Реализация процедур-подпрограмм.
- •Передача параметров.
- •Сохранение и восстановление значений. Соглашение о связях.
- •Введение в теоретическое программирование. Границы программирования. Принципиальная и практическая неразрешимость.
- •О формальной спецификации. Мир задачи как автомат.
- •Процедуры как функции на множестве состояний. Процедуры как преобразователи предикатов.
- •Универсальные методы решения задач.
Введение в теоретическое программирование. Границы программирования. Принципиальная и практическая неразрешимость.
Каковы пределы автоматизации (замены интеллектуальной деятельности «машинной», точнее программой, написанной другими людьми)? Эти проблемы мы осветили в терминах области машинного моделирования интеллектуальной деятельности, традиционно называемой «искусственный интеллект» (ИИ). Задачи ИИ относят к самым сложным и самым необходимым.
Что такое интеллект? Как минимум – способность решать задачи. Чем умный решатель отличается от глупого? Умному достаточно постановки задачи, спецификации, он сам находит метод решения. Глупый лишь исполняет алгоритм, постановки задачи он может и не знать.
алгоритм
ответ
данные
алгоритм
спецификация ответ
данные
Языки процедурного программирования, очевидно, рассчитаны на глупого исполнителя и описывают метод, но не спецификацию.
Использование рекурсии вместо циклов даёт языки более высокого уровня, хотя и менее эффективные. Чаще действует «золотое правило»: чем более универсален метод, тем менее эффективен он в каждом частном случае.
Можно ли сделать компьютер более умным?
Самый мощный суперкомпьютер функционально эквивалентен самому слабому – они могут решать одни и те же задачи. Всё их отличие от остальных механизмов состоит в том, что они являются универсальными интерпретаторами, но не универсальными решателями.
Основная задача ИИ («проба пера») – построить универсальный решатель задач, написать алгоритм, который в качестве входа принимает текст постановки задачи на некотором формальном языке спецификации, а на выходе выдаёт программу её решения на некотором языке программирования. Трактовка задачи корректна.
Язык спецификации Язык программирования
Существуют универсальные языки программирования, например: Паскаль, язык блок-схем или Ассемблер. Существуют универсальные языки спецификаций.
Самый простой ответ – это математика, точнее один из общих математических языков – теория множеств, математическая логика, теория функций. Наибольшая некорректность заключается в том, что существуют неразрешимые задачи, которые не имеют алгоритмов решения.
Примеры:
1) Проблема остановки: нельзя написать программу, проверяющую по тексту входящей программы, зацикливается ли она:
а) на заданных значениях;
б) на некоторых значениях.
Либо язык не даёт зацикливаться, либо он неуниверсален.
2) Существуют синтаксические анализаторы, проверяющие по входному тексту программы, является ли она на самом деле выражением данного языка программирования.
Задача написать семантический анализатор неразрешима.
а) Написать программу, которая проверяет функциональную эквивалентность двух программ.
б) Написать программу, проверяющую, удовлетворяет ли данная программа заданной спецификации.
Доказательства сложны, но причина тривиальна – все они сводятся к задаче проверки бесконечного числа входов.
Уточним постановку: написать программу, которая по данной спецификации выдаёт решение задачи, либо строку «Нет решений».
Универсального решателя задач не существует. Существует большой круг решаемых задач. Более того, в некотором смысле это все задачи. Это конечные задачи с конечным числом входов, вариантов решения.
Существует универсальный решатель конечных задач – это алгоритм полного перебора. Этот алгоритм считается не только глупым, но и практически неразрешимым в плане расхода ресурсов. Такими считаются задачи, в которых число вариантов растёт экспоненциально (как степень) от входных значений. Практически разрешимыми считаются задачи полиномиальной сложности. Это задачи тории сложности.
Для каждой ли задачи существует полиномиальное решение? В этом суть знаменитой ПНП-проблемы.
Вернёмся к постановке задачи…
Выявить возможно более полные классы задач, для которых проблема универсальных решений не только принципиальна, но и практически разрешима.
Пример моделирования интеллектуальной деятельности – задача «Обезьяна и банан». Содержательная постановка: в комнате находятся обезьяна, ящик и подвешенный к потолку банан. Как обезьяне его достать?
Понятно, что если обезьяна может подойти к ящику, перенести его под банан, встать на ящик и сорвать банан, то она должна сделать именно это. Очевидно, этот случай неявной спецификации алгоритма, в которой по умолчанию подразумевается возможность действовать «как обычно», «как все делают».
А как делают все? Что такое комната-ящик-банан? Как берут ящик?
Очевидно, компьютер ничего не воспринимает по умолчанию. В случае построения алгоритмов, работающих со спецификациями, необходим формальный язык спецификации – формальная теория.