Лабораторные работы по теории алгоритмов с решением

---

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

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

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

Алгоритм можно описать разными способами: словами, на языке программирования, а также с помощью блок-схем.

На языке блок-схем каждый шаг алгоритма описывается с помощью соответствующей фигуры, а последовательность выполнения шагов определяется линиями-связями. Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел. Перебор делителей – это алгоритм, предназначенный для определения, какое число перед нами: простое или составное. Алгоритм заключается в последовательном делении заданного натурального числа на все целые числа, начиная с двойки и заканчивая значением меньшим или равным квадратному корню тестируемого числа. Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.

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

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

Работа алгоритма должна завершаться за определенное число шагов, при этом задача должна быть решена. Отсюда следует, что разработчик алгоритма в конечном итоге должен описать алгоритм в допустимых командах определенного исполнителя (той машины, которой будет поручено выполнение алгоритма). С его помощью можно выполнять разнообразные по видам алгоритмы: делать математические вычисления, обрабатывать текстовые данные, изменять графику и др. Это связано с тем, что создание алгоритма предполагает подробное описание каждого шага решения задачи, и в конечном итоге шаг алгоритма может быть достаточно прост для выполнения его компьютером. Однако это не всегда так: стоит попытаться нарисовать блок-схему для более-менее сложного алгоритма, как она разрастается до невероятных размеров и теряет все свое наглядное преимущество. Если условие выполняется, то алгоритм идет по линии «да», если не выполняется – то по линии «нет». Если результат вычисления выражения-условия возвращает true (правда), то выполнение алгоритма идет по ветке «Да», в которую включены дополнительные выражения-действия.

В процессе выполнения данного алгоритма постепенно отсеиваются составные числа, кратные простым, начиная с 2.

Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией).

Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Однако с течением времени понятие алгоритма видоизменялось и в XX веке под ним стали понимать какую-либо последовательность действий, приводящую к решению поставленной задачи. А значит, задачи, для которых можно выработать алгоритм их решения, могут быть автоматизированы, т.е.

Если условие возвращает false (ложь), то выполнение алгоритма идет по ветке «нет», т.е продолжает выполняться основная ветка программы.

Занимательные факты:

1) Для того чтобы выполнение алгоритма не зациклилось, в теле цикла (помимо прочих действий) должно быть выражение, в результате выполнения которого будет изменяться переменная, используемая в условии.

2) Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

3) С другой стороны, если одному и тому же алгоритму передать несколько раз одни и те же данные, он должен столько же раз выдать один и тот же результат.

4) Данную алгоритмическую конструкцию (if – elif – else) не следует путать с алгоритмической конструкцией «Выбор».