Алгоритмы. Свойства и виды алгоритмов

Алгоритмы. Свойства и виды алгоритмов.

Ученый Мухаммед аль-Хорезми создал книгу по математике, в которой описал правила выполнения арифметических действий над многозначными числами.

Эти правила были изложены Мухаммедом в книге по математике, изданной в 825 году .

Позже в Европе эти приемы назвали « алгоритмами », от Algorithmi -латинского написания имени аль-Хорезми.

Мухаммед аль-Хорезми (787-850)

Понятие алгоритма

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

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

• Понятность  - алгоритм, составленный для конкретного исполнителя, должен включать только те команды, которые входят в его систему команд.
• Совокупность команд, которые могут быть выполнены исполнителем, называется  системой команд исполнителя (СКИ) .

Например, команда на турецком языке не будет понята исполнителем, не знающего турецкого языка.

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

• Точность  - каждая команда алгоритма должна однозначно определять действие исполнителя.
• Пример неточного алгоритма является изречение « Казнить нельзя помиловать ».

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

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

Например, простейший алгоритм для открытия двери разбивается на следующие команды :

• Вставить ключ в замочную скважину
• Повернуть его два раза
• Вынуть ключ из замочной скважины
• Открыть дверь

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

• Результативность (конечность)  - исполнение алгоритма должно приводить к решению задачи за конечное число шагов.

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

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

• Массовость - алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными.

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

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

• Словесный

Например

Рецепт приготовления глазуньи:

• Разогреть сковороду
• Смазать сливочным маслом
• Разбиваем яйца, не размешивая
• Проверяем на готовность
• Выкладываем на тарелку

• Псевдокод (алгоритмический язык) - система правил и обозначений для единообразной и точной записи алгоритмов.

Псевдокод ориентирован на человека и облегчает перевод на язык программирования /

алг

арг

рез

нач

кон

алг переход дороги

нач

подойти к дороге

если горит зеленый то перейти дорогу

иначе стоять на месте

всё

кон

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

Блок начала и конца алгоритма

Блок ввода данных

или вывода результатов

Блок проверки условия

Блок действия или арифметических операций

да

нет

• На языке программирования 

Язык программирования - это совокупность средств и правил представления алгоритмов в виде, приемлемом для компьютера.

Программа – это алгоритм, записанный на языке исполнителя.

Виды алгоритмов

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

начало

Открыть кран

Помыть руки

Закрыть кран

конец

• Алгоритм с ветвлением  - в зависимости от выполнения или невыполнения условия, исполняется либо одна, либо другая ветвь алгоритма.
• Пример

Начало

Подойти к дороге

Горит зеленый?

да

нет

Перейти дорогу

Стоять на месте

Конец

Циклический  - это алгоритм, в котором некоторая последовательность команд выполняется многократно, но не бесконечно.

Циклические алгоритмы существуют двух видов:

• когда количество повторений заранее известно (цикл с параметром)

Пример: Делаем зарядку. Сделать приседания 10 раз

• количество повторений заранее неизвестно и определяется некоторым условием. Здесь выделяются циклы с предусловием (циклы «пока») и циклы с постусловием (циклы «до»).

• Цикл с предусловием

• Цикл с постусловием

Начало

Начало

Открыть кран

Хотите конфету

нет

да

взять конфету

Вымыть одну

тарелку

Все тарелки

вымыты?

нет

развернуть

Конец

да

съесть

Закрыть кран

Конец

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

• Знать что такое алгоритм, его свойства, виды алгоритмов и способы их записи.
• Составить словесный алгоритм нахождения среднего арифметического 4х чисел.
• Составить алгоритм с ветвлением ( на алг. языке ) сравнения двух чисел а и b . Проверить работу алгоритма при а=5, b =8.
• Придумать и записать циклический алгоритм ( блок-схема ).