Алгоритм – конечная совокупность точно сформулированных правил решения какой-либо задачи.

Понятие алгоритма. Алгоритмизация задач.

Термин алгоритм своим происхождением обязан имени узбекского математика Аль-Хорезми, который в 9 веке сформулировал правила выполнения 4 арифметических действий в 10 системе счисления. Процесс выполнения арифм. Действий он назвал алгоризмом. С 1747г. стали употреблять алгорисмус, с 1950 г. алгорифм, который чаще всего связывался с алгорифмами Евклида – процесс нахождения наибольшего общего делителя двух многочленов. В 20 годах 20 века определение понятия алгоритма стало центральной математической проблемой. Решение её было получено математиками Гильбертом, Гёделем, Черчем, Постом, Тьюрингом в двух формах. Первое решение было основано на понятии рекурсивных функций, второе на описании точно очерченного класса процессов. Второй тип основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент времени лишь весьма примитивные операции. Эвристика этой модели близка к ЭВМ. Основной теоретической моделью этого типа (созданной в 30 –х годах -раньше ЭВМ) является машина Тьюринга. Основная мысль Поста и Тьюринга заключалась в том, что алгоритмические процессы – это процессы, которые может совершать подходяще устроенная «машина». Ими с помощью точных математических терминов были описаны довольно узкие классы машин, на которых оказалось возможным осуществить или имитировать все алгоритмические процессы, которые фактически когда-либо писывались математиками. Под машинами Поста и Тьюринга понимается некоторая гипотетическая (условная) машина, состоящая из следующих частей:

1. Информационной ленты, представляющей собой бесконечную память машины, разделённой на отдельные ячейки. В каждой ячейке можно поместить лишь один символ, в том числе и нуль.

2. «Считывающей головки» - специального чувствительного элемента, способного обозревать содержимое ячеек. Вдоль головки информационная лента перемещается в обе стороны так, чтобы в каждый рассматриваемый момент времени головка находилась в одной определенной ячейке ленты.

3. Управляющего устройства, которое в каждый рассматриваемый момент времени находится в некотором «состоянии». Состояние устройства управления наз. Внутренним состоянием машины. Одно из этих состояний наз. Заключительным и в работе машины играет особую роль, так как управляет окончанием работы машины.

Пусть алфавит машины Тьюринга задан в виде множества А={s₀,s₁,…s_n}, где s₀ соответствует пустой ячейке, а число состояний устройства управления задано в виде множества Q={q₀,q₁,…q_m}, где q₀соответствует заключительному состоянию.

Конечная совокупность символов алфавита, с которой работает машина, наз. внешним алфавитом.

q_i

Если стандартная машина Тьюринга, находясь в состоянии q_i и воспринимая записанный на ленте символ Sk , переходит в новое состояние q_j , осуществляя при этом замену символа в рассматриваемой ячейке на символ s_m и сдвиг ленты на одну ячейку, то говорят, что машина выполняет команду

q_i Sk ® q_j s_m Л При манипуляциях Л –движение ленты влево, П –вправо, С –нет движения.

Рассмотрим пример машины Тьюринга с алфавитами А={0,1}, Q={q₀,q₁} и командами q₁1q₁1Л , q₁ 0 q₀1С. Пусть на ленте имеется слово 11100. Головка стоит над первой слева 1. В результате работы машины Тьюринга это слово превращается в в 11110. По окончании работы головка стоит над крайней справа 1.

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

Появление ЭВМ способствовало развитию теории алгоритмов, вызвало к жизни разделы этой теории, имеющие ярко выраженную прикладную направленность.

Алгоритм – конечная совокупность точно сформулированных правил решения какой-либо задачи.

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

Алгоритмы делятся на:

Детерминированный алгоритм –алгоритм, имеющий место при чёткой и ясной системе правил и указаний и однозначных действиях.

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

Численный алгоритм – алгоритм, соответствующий решению поставленной задачи с помощью арифметических действий (+,-,*).

Логический алгоритм – алгоритм, при котором используются логические действия. Примером может служить поиск минимального числа.

Дата добавления: 2018-05-12; просмотров: 399; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 Следующая ⇒

Мы поможем в написании ваших работ!