Свойства алгоритма Способы описания Виды алгоритма Что такое алгоритм?

Из истории Само слово «алгоритм» происходит от имени великого узбекского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 г. он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, арабский оригинал книги не сохранился, так что её оригинальное название нам неизвестно. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритми о счёте индийском»). Про аль-Хорезми позднейшие авторы ничего не знали, но поскольку первый перевод книги начинается словами: «Dixit algorizmi: …» («Аль-Хорезми говорил: …»), всё ещё связывали это слово с именем конкретного человека. Очень распространённой была версия о греческом происхождении книги. В англо- норманской рукописи XIII века, написанной в стихах, читаем: "Алгоризм был придуман в Греции. Это часть арифметики. Придуман он был мастером по имени Алгоризм, который дал ему своё имя. И поскольку его звали Алгоризм, Он назвал свою книгу «Алгоризм». ( материал из Хаба-вики)

Алгоритм – это последовательность действий, которые должен выполнить исполнитель для достижения конкретной цели. Алгоритм содержит несколько шагов. Шаг – отдельное законченное действие.

Исполнитель - это объект, умеющий выполнять определенный набор действий. (человек, животное, робот, компьютер). Система команд исполнителя (СКИ) – это все команды, которые исполнитель умеет выполнять. Среда исполнителя – обстановка, в которой функционирует исполнитель.

Свойства алгоритма Дискретность (прерывность, раздельность) – разбиение алгоритма на шаги; Понятность – каждый шаг алгоритма должен быть понятен исполнителю; Точность - указание последовательности шагов; Результативность - получение результата за конечное число шагов; Массовость – использование алгоритма для решения однотипных задач.

Свойства Пример выполнения свойства Пример невыполнения свойства ДискретностьКазнить нельзя, помиловать.Казнить, нельзя помиловать. Детерминированность (точность) На дубе ларец, а в ларце утка, а в утке яйцо, в яйце игла, в игле смерть Кощея. Поди туда, не знаю куда, принеси то, не знаю что. МассовостьКаждой дочери отец привёз по дорогому подарку. Принц мог жениться только на настоящей принцессе. ПонятностьИнструкция по-русски.Инструкция на японском языке. КонечностьМама сварила кашу в горшочке. Каша уже заполнила все улицы, а горшочек всё варил кашу. РезультативностьМышка хвостиком махнула, яйцо и разбилось. Баба била-била, не разбила.

Способы описания алгоритма: Словесный (письменно или устно); Графический (стрелками, рисунками, блок – схемами); Программный.

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

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

Основные блоки - блок начала или конца алгоритма -блок присваивания -блок ввода или вывода -блок проверки условий -блок счетчика

Виды алгоритмов: Линейный – содержит несколько шагов и все шаги выполняются последовательно друг за другом; Разветвляющийся – порядок выполнения шагов изменяется в зависимости от некоторых условий; Циклический – определенная последовательность шагов повторяется несколько раз в зависимости от заданной величины (параметра цикла).

ЛИНЕЙНЫЙ Начало Оператор 1 Оператор 2 Оператор 3 ВВЕСТИ КОНЕЦ Программа имеет линейную структуру, если все операторы (команды) выполняются последовательно друг за другом.

ВЕТВЯЩИЙСЯ НАЧАЛО УСЛОВИЕ ОПЕРАТОР 1ОПЕРАТОР 2 ВВЕСТИ КОНЕЦ Разветвляющий алгоритм – это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательн ость действий.

Циклический НАЧАЛО ВВЕСТИ УСЛОВИЕ тело цикла КОНЕЦ ОПЕРАТОР 2 счетчик Циклический алгоритм - описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие. Перечень повторяющихся действий называют телом цикла.

Алгоритмические задачи Задание. Волк, коза и капуста. Старик должен переправить на лодке через реку волка, козу и капусту. Лодка может выдержать только старика и одного «пассажира». В каком порядке старик перевезёт «пассажиров»? Не забудь, что волк может съесть козу, а коза – капусту. Найди два варианта решения.

Задача. Переправа. К берегу реки, где была лодка, вмещающая только двух человек, подошли два разбойника и два путешественника. Разбойники не решались напасть на путешественников. В случае если на берегу останется один путешественник и два разбойника, они нападут на него. Как надо переправиться через реку разбойникам и путешественникам, чтобы последние смогли избежать нападения? Обозначения: П1 – первый путешественник П2 – второй путешественник; Р1 – первый разбойник; Р2 – второй разбойник.

Первый берегВторой берег Нач.П1 П2 Р1 Р2 1П2 Р2П1 Р1 П2 Р2П1 Р1 2П2 Р2 П1Р1 П1 П2 Р2Р1 3Р2П1 П2 Р1 Р2П1 П2 Р1 4Р2 Р1П1 П2 Р1 Р2П1 П2 5Р1 Р2 П1 П2 Кон.П1 П2 Р1 Р2