Презентация Основы теории алгоритмов онлайн

Содержание слайда: Тема 6. Основы теории алгоритмов

Содержание слайда: 6.1 Интуитивное понятие об алгоритме Интуитивное понятие алгоритма. Алгоритм – это правило, сформированное на некотором языке и определяющее процесс переработки допустимых исходных данных в искомые результаты. Допустимыми исходными данными для этого правила являются предложения языка исходных данных.

Содержание слайда: Правила описания алгоритмов: Понятность для исполнителя Массовость (т.е. допустимость для него всех предложений языка исходных данных) Определенность (все шаги алгоритма детерминированы и четко определены) Результативность

Содержание слайда: Алгоритм применим к допустимому исходному данному, если с его помощью, отправляясь от этого исходного данного, можно получить искомый результат. При этом алгоритмический процесс оканчивается после конечного числа шагов и на каждом шаге нет препятствий для его выполнения. Алгоритм применим к допустимому исходному данному, если с его помощью, отправляясь от этого исходного данного, можно получить искомый результат. При этом алгоритмический процесс оканчивается после конечного числа шагов и на каждом шаге нет препятствий для его выполнения.

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

Содержание слайда: Об источниках алгоритмов: Практика; научная теория; совокупность накопленных алгоритмов; изобретательность разработчика.

Содержание слайда: 6.2 Три типа алгоритмических моделей Различный выбор исходных средств формализации приводит к моделям алгоритмов разного вида. Можно выделить три основных типа универсальных алгоритмических моделей, различающихся исходными эвристическими соображениями относительно того, что такое алгоритм.

Содержание слайда: Первый тип Связывает понятие алгоритма с вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого типа – рекурсивные функции – первый способ формализации понятия алгоритма.

Содержание слайда: Второй тип Основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент лишь примитивные операции (машина Тьюринга).

Содержание слайда: Третий тип Это преобразование слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замена куска слова (подслова) другим словом (Нормальный алгоритм Маркова, каноническая система Поста).

Содержание слайда: Тезис Чёрга Класс задач, решаемых в любой из этих формальных моделей, и есть класс всех задач, которые могут быть решены интуитивно алгоритмическими методами. Одна из причин, побудивших заняться теорией алгоритмов, – это подозрительность математиков в связи с накоплением упорно не поддающихся решению задач на нахождение алгоритмов.

Содержание слайда: Примеры. Задача о квадратуре круга. Требуется найти алгоритм построения с помощью циркуля и линейки квадрата, равновеликого данному кругу. Задача трисекции угла. Требуется найти алгоритм деления произвольного угла с помощью циркуля и линейки на три равные части

Содержание слайда: Примеры. Задача удвоения куба. Найти алгоритм, позволяющий на стороне любого куба с помощью циркуля и линейки построить сторону куба, объем которого вдвое больше объема заданного куба.

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

Содержание слайда: Пример Актуально бесконечное множество. Расходуя ограниченное количество ресурсов на каждом шаге, имеющим фиксированную длительность, построить такое множество ни реально, ни потенциально нельзя; нельзя проверить обладает ли все элементы такого множества каким либо свойством из-за ограниченной скорости проверки.

Содержание слайда: 6.3 Кризис теории множеств антиномии. Выводы из антиномий. До середины XIX века никто не сомневался в истинности математических результатов, залогом чего считалась истинность аксиом. Исследования Лобачевского сокрушили веру в аксиомы и заставили задуматься над тем, что же является фундаментом математики. Оказалось, что все вопросы можно свести к рассмотрению только натуральных чисел и некоторых отношений между ними. Была доказана возможность полной арифметизации матанализа и теории функций.

Содержание слайда: На втором Международном Математическом Конгрессе было заявлено, что теперь в математике остались только целые числа и конечные или бесконечные множества целых чисел. Математика полностью арифметизирована. И вот тогда, когда математика обрела надежный фундамент сама арифметика пошатнулась из-за того что в теории множеств были обнаружены противоречия, вошедшие в историю математики под названием антиномий. На втором Международном Математическом Конгрессе было заявлено, что теперь в математике остались только целые числа и конечные или бесконечные множества целых чисел. Математика полностью арифметизирована. И вот тогда, когда математика обрела надежный фундамент сама арифметика пошатнулась из-за того что в теории множеств были обнаружены противоречия, вошедшие в историю математики под названием антиномий.

Содержание слайда: Две теории Кантора из теории множеств Кардинальное число множества М называется его мощностью и обозначается m. Теорема 1: Для любого кардинально числа m справедливо неравенство m<2m, где 2m – мощность множества всех подмножеств бесконечного множества. Теорема 2: Мощность m’ подмножества множеств, имеющих мощность m удовлетворяет неравенству m’<= m

Содержание слайда: Парадокс Кантора. Пусть М множество всех множеств обозначим его кардинальное число буквой m. В силу теоремы 1 кардинальное число множества его подмножества 2m удовлетворяет условию 2m> m с другой стороны множество m есть множество всех множеств его подмножества являются множествами и значит являются элементом М, а их множества являются подмножествами множества М. По теореме 2 должно иметь место неравенство 2m<= m полученные два неравенства противоречат друг другу

Содержание слайда: Парадокс Рассела (парадокс брадобрея). Один из солдат оказался по профессии парикмахером, узнав об этом командир приказал ему брить всех тех и только тех кто сам себя не бреет. Все было хорошо пока не пришло время побрить самого себя оказалось, что побрить самого себя нельзя, так парикмахер брил только тех кто себя не бреет. Не брить себя тоже нельзя, потому что приказано брить всех, кто себя не бреет.

Содержание слайда: Открытие антиномий потрясло математику и математиков, как землетрясение. Нужно сказать, что математики поразному отреагировали на это заявление: одни стали во всем сомневаться, другие на антиномии не отреагировали. Открытие антиномий потрясло математику и математиков, как землетрясение. Нужно сказать, что математики поразному отреагировали на это заявление: одни стали во всем сомневаться, другие на антиномии не отреагировали.

Содержание слайда: 6.4 Машины Тьюринга как модели алгоритмов В 1937г. английский математик Тьюринг опубликовал работу в которой он уточняя понятие алгоритма, прибегал к воображаемой вычислительной машине. Машина должна перерабатывать какие-то объекты в исходные результаты. Этими объектами являются слова, построенные из символов-букв.

Содержание слайда: Машина состоит из бесконечной в обе стороны ленты, разбитой на ячейки, и рабочей головки. Машина работает в дискретные моменты времени t=0,1,2… В каждый момент времени во всякой ячейке ленты записана одна буква из некоторого конечного алфавита А={а0, а1, а2…аn}, называемым внешним алгоритмом машины, а головка находится в одном состояний из конечного множества внутренних состояний Q={q0, q1…qz}. Будем считать,что а0-пустой символ, т.е. в ячейке ничего не написано. Машина состоит из бесконечной в обе стороны ленты, разбитой на ячейки, и рабочей головки. Машина работает в дискретные моменты времени t=0,1,2… В каждый момент времени во всякой ячейке ленты записана одна буква из некоторого конечного алфавита А={а0, а1, а2…аn}, называемым внешним алгоритмом машины, а головка находится в одном состояний из конечного множества внутренних состояний Q={q0, q1…qz}. Будем считать,что а0-пустой символ, т.е. в ячейке ничего не написано.

Содержание слайда: Основной частью машины является логический блок, который работает следующим образом. В каждый момент времени рабочая головка обозревает одну ячейку ленты и в зависимости от того, что там написано и от своего внутреннего состояния она заменяет символ в обозреваемой ячейке, переходит в новой состояние и сдвигает на одну ячейку или остается на месте. Введем для обозначения этого движения символы d-1, d0, d+1 соответственно. Основной частью машины является логический блок, который работает следующим образом. В каждый момент времени рабочая головка обозревает одну ячейку ленты и в зависимости от того, что там написано и от своего внутреннего состояния она заменяет символ в обозреваемой ячейке, переходит в новой состояние и сдвигает на одну ячейку или остается на месте. Введем для обозначения этого движения символы d-1, d0, d+1 соответственно.

Содержание слайда: Т.о. работа МТ задается системой команд вида: qj*ai-qk*ax*dy Все случаи сочетания qj и ai для разных j и j и все реакции машины на них можно представить в виде функциональной таблицы с двумя входами.

Содержание слайда: Если головка в состоянии qj читаем символ ai, то в следующий момент она записывает в эту ячейку символ ax. Переход в состояние qk и в зависимости от того каково dy гловка сдвигает на одну ячейку влево, вправо или остается на месте. Если головка в состоянии qj читаем символ ai, то в следующий момент она записывает в эту ячейку символ ax. Переход в состояние qk и в зависимости от того каково dy гловка сдвигает на одну ячейку влево, вправо или остается на месте.

Содержание слайда:

Содержание слайда: Примеры построения машин Тьюринга Постороить машину Тьюринга, реализущую. «сложение» чисел. В машине Тюринга все числа представляются в единичном коде, состоящем из Х единиц. Поэтому сложить а и в значит переработать слова 1а * 1в в слово 1а+в. Это преобразование выполняет машина c 4-мя состояниями и системой команд вида

Содержание слайда:

Содержание слайда: Построить машину Тьюринга, которая вычисляет функцию а(Х)=Х+1 число Х запишем в виде строки, состоящей из букв 1 (палочек)

Содержание слайда: В первом случае говорят, что машина применила к исходному данному, во втором – не применима. Соответствия устанавливаются между теми исходными данными, к которым они применимы, и результат ее работы представляет собой некоторую функцию (в математическом смысле). В первом случае говорят, что машина применила к исходному данному, во втором – не применима. Соответствия устанавливаются между теми исходными данными, к которым они применимы, и результат ее работы представляет собой некоторую функцию (в математическом смысле). Если для функции f(x) можно построить МТ, которая к ней применима, то говорят, что f(x) вычислена по Тьюрингу. Функцию, для вычисления которой существует МТ, называют вычислимой.

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

Содержание слайда: Проблема остановки: Можно ли построить машину То такую что для любой машины Тк любых исходных данных а для машины Т. Ответ на этот вопрос отрица-тельный, т.к. сформулирована и доказана следующая теорема.

Содержание слайда: Теорема Тьюринга: Не существует машины То , решающей проблему остановки для произвольной машины Т. Неразрешимость проблемы оста-новки можно интерпретировать как несуществование общего алгоритма для отладки программы.