Лекция 1 Понятие алгоритма Классификация алгоритмических моделей

• В третьем и четвертом модуле будут рассмотрены фундаментальные понятия математики, важные для всех, кто занимается математикой.  

• Эти понятия включают вычисление и доказательство.  

• В третьем модуле будет изучаться теория алгоритмов, которая рассматривает вычисление.  

• В четвертом модуле будет рассмотрен аксиоматический подход к математической логике, изучающий доказательство.  

• История математики показывает, что строгость рассуждений и точность вычислений не были предметом самой математики до XIX века.  

• В XIX веке возникли парадоксы, связанные с новыми объектами, такими как множества и функции.  

• Теория множеств стала рассматривать объекты произвольной природы, что привело к парадоксам, таким как парадокс Кантора.  

• Понятие функции изменилось с политического представления на точное определение.  

• Возникают проблемы с представлением данных и вычислением функций.  

• Понятие алгоритма возникло давно, но до середины XIX века математики не задумывались о его природе.  

• Алгоритмы стали объектом исследования в математике и информатике.  

• Теория алгоритмов изучает методы исследования в самой математике.  

• Основные понятия и теоремы были уточнены в 30-х годах XX века.  

• Алгоритм в интуитивном понимании — это последовательность шагов, строго определенных для любых данных.  

• Алгоритм должен быть применим к бесконечному множеству данных и давать однозначный результат.  

• Алгоритм должен давать результат, что не всегда очевидно.  

• Проблема результативности требует уточнения и исследования.  

• Требования к алгоритмам: однозначность результата, детерминированность, элементарный шаг.  

• Уточнение этих требований приводит к различным алгоритмическим моделям.  

• Алгоритм работает с данными и выдает результат.  

• Данные формируются из конечного множества символов, называемого алфавитом.  

• Примеры алфавитов: символы клавиатуры, цифры, буквы, переменные, скобки, знаки операций.  

• Память должна быть выделена для хранения данных.  

• Элементарный шаг должен работать с фиксированным числом единиц памяти.  

• Пример: машинная команда, работающая с ограниченным объемом памяти.  

• Детерминированность: правила инициации, определения следующего шага и окончания.  

• Результативность: алгоритм должен давать ответ на все возможные данные задачи.  

• Не все алгоритмы являются решением задачи, что связано с их корректностью.  

• Три основных типа моделей: абстрактные машины, машина Тьюринга, машина Поста.  

• Машина Тьюринга: механическая модель, работающая с символами и состояниями.  

• Машина Поста: математическая модель, вычисляющая функции.  

• Построение теории вычислимых функций из простых арифметических функций.  

• Операции над функциями, сохраняющие вычислимость.  

• Задача: выяснить набор операций, сохраняющих вычислимость и позволяющих построить все вычислимые функции.  

• Три типа моделей: абстрактные машины, комбинаторные модели, модели Тьюринга.  

• Идея: данные могут быть любыми словами в любых алфавитах, операции над ними должны быть комбинаторными.  

• Примеры операций: замена фрагментов слова, добавление символов, удаление фрагментов со сдвигом.  

• Основное внимание: абстрактные машины Тьюринга.  

• Имена математиков, связанных с моделями: Тьюринг, Пост, Клини, Черч, Гёдель, Марков.  

• Идея: алгоритм должен выполняться машиной, а не человеком.  

• Важность математической точности и простоты конструкции.  

• Машина Тьюринга как основа современной вычислительной техники.  

• Лента с ячейками, управляющее устройство с головкой, способной читать и писать.  

• Команды управления, конечное множество состояний, начальное и заключительное состояния.  

• Алфавит символов, включая пустой символ.  

• Команды: устройство переходит в новое состояние, пишет символ, перемещается по ленте.  

• Требования к командам: детерминизм, отсутствие одинаковых команд.  

• Проблема результативности: машина может зациклиться и никогда не выйти из начального состояния.  

• Пример таблицы команд: описание переходов между состояниями и символами.  

• Таблица обеспечивает детерминизм, так как каждой левой части соответствует одна ячейка.  

• Конфигурация машины определяется состоянием ленты, головкой и управляющим устройством.  

• Описание конфигурации включает символы алфавита и слова.  

• Терминизм машины заключается в том, что каждая конфигурация однозначно определяет следующую.  

• Если конфигурация повторяется, машина "зацикливается".  

• Остановка машины означает, что ни одна из конфигураций не повторяется.  

• Начальные и конечные конфигурации должны быть стандартными.  

• Начальные конфигурации начинаются с пустого левого символа.  

• Конечные конфигурации завершаются на правом символе результата.  

• Стандартные конфигурации удобны для программистской культуры, так как промежуточные результаты стираются.  

• Возможность передачи управления от одной машины к другой.  

• Каждая машина тьюринга соответствует функции, определенной на всех словах алфавита.  

• Функция вычисляется, если машина останавливается с результатом на ленте.  

• Современные машины тьюринга больше похожи на программы, чем на физические машины.  

• Универсальные машины могут вычислять все функции, что является теоретической основой современной вычислительной техники.