Понятие алгоритма – одно из базовых в информатике и главное в программировании. Алгоритм – это совокупность инструкций исполнителю, выполнять конечную последовательность действий для достижения решения им задачи за конечное число шагов. Под исполнителем, чаще всего, понимается некоторый механизм (компьютер, станок), способный понимать и выполнять те или иные команды. Но в качестве исполнителя может выступать, например, человек или животное, т. к. алгоритм это не обязательно сложные, понятные лишь компьютеру инструкции. Действие схожее с приготовлением пищи или походом в магазин также является алгоритмом.
Слово «алгоритм» происходит от имени средневекового персидского ученого Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми (алгоритм – аль-Хорезми). Оно впервые упоминается в его сочинении, датированным примерно 825-ым годом.
Алгоритм должен быть описан согласно некоторым правилам. Различают следующие способы описания алгоритма:
· словесное описание (с помощью естественного языка);
|
|
· графическое описание (с помощью блок-схем);
· программное описание (с помощью языка программирования);
· псевдокод (словесное описание + программное описание).
Выделяют следующие виды алгоритмов:
· линейный алгоритм – набор инструкций, выполняемых последовательно во времени друг за другом;
· разветвляющийся алгоритм – алгоритм, в котором направление обработки информации зависит от результата выполнения логического условия;
· циклический алгоритм – алгоритм, предусматривающий многократное повторение одного и того же действия над исходными данными.
Алгоритм обладает следующими свойствами:
· дискретность – процесс решения задачи алгоритм должен представляться как последовательное выполнение некоторых простых шагов;
· детерминированность – выдача алгоритмом одного и того же результата для одних и тех же исходных данных;
· понятность – использование только понятных исполнителю команд;
· конечность – завершенность работы алгоритма и выдача им результата за конечное число шагов;
· универсальность (массовость) – возможность применения алгоритма к разным наборам исходных данных;
· результативность – завершение алгоритма определёнными результатами.
Глава 5.Анализ сложности алгоритмов