Понятие алгоритма. Свойства алгоритма
В 2003 году отмечалось 1220-летие со дня рождения величайшего средневекового ученого Средней Азии Мухамеда ибн Мусы аль-Хорезми. С именем этого ученого связано понятие алгоритма.
Итак, Алгоритм - это определённая последовательность действий, которые необходимо выполнить, чтобы получить результат. Алгоритм может представлять собой некоторую последовательность вычислений, а может - последовательность действий нематематического характера. Для любого алгоритма справедливы общие закономерности - свойства алгоритма.
Дискретность - это свойство алгоритма, когда алгоритм разбивается на конечное число элементарных действий (шагов).
Понятность - свойство алгоритма, при котором каждое из этих элементарных действий (шагов) являются законченными и понятными.
Детерминированность - свойство, когда каждое действие (операция, указание, шаг, требование) должно пониматься в строго определённом смысле, чтобы не оставалась места произвольному толкованию. чтобы каждый, прочитавший указание, понимал его однозначно.
Массовость - свойство, когда по данному алгоритму должна решаться не одна, а целый класс подобных задач.
Результативность – свойство, при котором любой алгоритм в процессе выполнения должен приводить к определённому результату. Отрицательный результат также является результатом.
7.2. Способы записи алгоритма: псевдокод, блок-схема
Алгоритм должен быть формализован по некоторым правилам посредством конкретных изобразительных средств. К ним относятся следующие способы записи алгоритмов: словесный, формульно-словесный, графический, язык операторных схем, алгоритмический язык.
Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.
Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.
В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя.
Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются.
Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
алг Сумма квадратов (арг цел n, рез цел S)
дано | n > 0
надо | S = 1*1 + 2*2 + 3*3 + ... + n*n
нач цел i
ввод n; S:=0
нц для i от 1 до n
S:=S+i*i
кц
вывод "S = ", S
кон
Наибольшее распространение благодаря своей наглядности получил графический (блок-схемный) способ записи алгоритмов.
Блок-схемой называется графическое изображение логической структуры алгоритма, в котором каждый этап процесса обработки информации представляется в виде геометрических символов (блоков), имеющих определенную конфигурацию в зависимости от характера выполняемых операций. Перечень символов, их наименование, отображаемые ими функции, форма и размеры определяются ГОСТами.
При всем многообразии алгоритмов решения задач в них можно выделить три основных вида вычислительных процессов:
· линейный;
· ветвящийся;
· циклический.
Линейным называется такой вычислительный процесс, при котором все этапы решения задачи выполняются в естественном порядке следования записи этих этапов.
Ветвящимся называется такой вычислительный процесс, в котором выбор направления обработки информации зависит от исходных или промежуточных данных (от результатов проверки выполнения какого-либо логического условия).
Циклом называется многократно повторяемый участок вычислений. По количеству выполнения циклы делятся на циклы с определенным (заранее заданным) числом повторений и циклы с неопределенным числом повторений. Количество повторений последних зависит от соблюдения некоторого условия, задающего необходимость выполнения цикла. При этом условие может проверяться в начале цикла — тогда речь идет о цикле с предусловием, или в конце — тогда это цикл с постусловием.
7.3. Преобразование программы в машинные коды.
Интерпретаторы и компиляторы
Преобразование программы, написанной на языке высокого уровня, в двоичный код, на котором работает компьютер, требует пристального внимания к многочисленным деталям - того, что успешно может делать компьютер под управлением транслирующей программы.
Трансляция программы — преобразование программы, представленной на одном из языков программирования, в программу на другом языке и, в определённом смысле, равносильную первой.
Язык, на котором представлена входная программа, называется исходным языком, а сама программа — исходным кодом.
Транслирующие программы делятся на две категории: интерпретаторы и компиляторы.
Интерпретатор преобразует небольшой фрагмент исходной программы в машинные команды и, лишь дождавшись, когда компьютер их выполнит, переходит к обработке следующего фрагмента.
Компилятор, наоборот, транслирует всю программу, написанную на языке высокого уровня, и помещает команды в память компьютера, не выполняя их; компилированную программу можно сохранить, чтобы в дальнейшем использовать.
Каждый из этих способов преобразования имеет свои достоинства и недостатки.
Компилированные программы выполняются быстрее, чем интерпретируемые; однажды компилированная программа не требует в дальнейшем компилятора, и компьютеру не приходится исхитряться, чтобы одновременно и транслировать, и выполнять программу.
Программы, написанные на языках, ориентированных на интерпретацию, требуют присутствия в памяти компьютера интерпретатора, который осуществляет трансляцию программы в ходе ее выполнения.
Благодаря построчной трансляции интерпретатор полезен как при отладке, так и при трансляции программ, подверженных частым изменениям; исправленную программу можно сразу запустить, чтобы проверить ее работу. При использовании компилятора исправленную программу приходится перекомпилировать.
Как компилятор, так и интерпретатор должны соответствовать правилам конкретного языка высокого уровня, который они транслируют. Подобно тому, как правила грамматики описывают естественный язык, правила формального языка управляют работой программиста, указывая, как можно соединять слова и символы, используемые в языке, при построении сложных выражений и задавая правила форматирования, в том числе употребления пробелов и знаков пунктуации. В транслирующих программах грамматика является основой преобразования понятий исходной программы в машинный код.