Алгоритмы и алгоритмизация

АЛГОРИТМЫ И АЛГОРИТМИЗАЦИЯ

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

В. А. Успенский

Что такое алгоритм?

Название "алгоритм" произошло от латинской формы имени величайшего среднеазиатского (узбекского) математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783—850 гг. В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними "столбиком", знакомые теперь каждому школьнику. В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.

РЕЦЕПТ

МЕТОД

АЛГОРИТМ

СПОСОБ

ИНСТРУКЦИЯ

Что такое алгоритм?

Алгоритм — заранее заданное понятное и точное предписание возможному исполнителю совеpшить определенную последовательность действий для получения решения задачи за конечное число шагов.

Это — не определение в математическом смысле слова, а, скорее, описание интуитивного понятия алгоритма, раскрывающее его сущность.

Свойства алгоритмов

В отличие от рецепта, способа и т.д., любой алгоритм обязательно обладает следующими свойствами:

1. Понятность для исполнителя — исполнитель алгоритма должен понимать, как его выполнять. Иными словами, каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола.

2. Дискpетность (прерывность, раздельность) — алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов).

3. Детерменированность — строгая последовательность выполнения команд. Однозначный способ решения задачи.

Свойства алгоритмов

В отличие от рецепта, способа и т.д., любой алгоритм обязательно обладает следующими свойствами:

4. Pезультативность (или конечность) состоит в том, что за конечное число шагов алгоpитм либо должен пpиводить к pешению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов.

5. Массовость означает, что алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными. Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма.

Исполнитель алгоритма

Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

Исполнителя хаpактеpизуют:

• сpеда исполнителя;
• cистема команд;
• элементаpные действия;
• отказы.

Исполнитель алгоритма

Обычно исполнитель ничего не знает о цели алгоритма. Он выполняет все полученные команды, не задавая вопросов "почему" и "зачем" .

В информатике универсальным исполнителем алгоритмов является компьютер .

Способы записи алгоритмов

• словесный (запись на естественном языке);
• графический (изображения из графических символов);
• псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
• программный (тексты на языках программирования).

Словесная запись

• Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

• Пример: инструкции, кулинарные рецепты и др.

Словесный способ не имеет широкого распространения, так как такие описания:

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

Словесная запись

Пример: копирование фрагмента текста.

1. Выделить фрагмент текста.

2. Скопировать фрагмент в буфер обмена.

3. Установить курсор в нужном месте документа.

4. Вставить фрагмент из буфера обмена.

Графический способ (блок-схемы)

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

НАЧАЛО / КОНЕЦ

УСЛОВИЕ

ВВОД / ВЫВОД

ПРОЦЕСС / ДЕЙСТВИЕ

Графический способ (блок-схемы)

Пример: копирование фрагмента текста.

НАЧАЛО

Выделить фрагмент текста

Скопировать фрагмент в буфер обмена

Установить курсор в нужном месте документа

Вставить фрагмент из буфера обмена

КОНЕЦ

Псевдокоды

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

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

Примером может служить школьный алгоритмический язык.

Школьный АЯ

Основные служебные слова

алг (алгоритм)

сим (символьный)

арг (аргумент)

лит (литерный)

рез (результат)

дано

лог (логический)

для

надо

нач (начало)

да

от

кон (конец)

если

таб(таблица)

до

нц (начало цикла)

цел (целый)

то

нет

при

иначе

кц (конец цикла)

вещ (вещественный)

знач          

и

длин (длина)

выбор

все

ввод

или

пока          

не

вывод

утв

Школьный АЯ

Общий вид алгоритма:

алг название алгоритма (аргументы и результаты)

дано условия применимости алгоритма

надо цель выполнения алгоритма

нач описание промежуточных величин |

последовательность команд (тело алгоритма)

кон

Школьный АЯ

Определить объём и площадь боковой поверхности цилиндра с заданными радиусом основания R и высотой H.

алг Цилиндр (арг вещ R, H, рез вещ V, S)

нач вещ Pi

Pi := 3.14 

V := Pi * R^2 * H 

S := V * H 

кон

Домашнее задание

§ 4.1.1. , вопросы устно

§ 4.1.2. , вопросы устно

Составить алгоритм в тетради: (словесная форма, не менее 10 пунктов)

1 ряд: «Сварить картошку»

2 ряд: «Заварить чай»

3 ряд: «Купить продукты»