Алгоритмы и способы их описания

Алгоритмы и способы их описания

• Слово «алгоритм» происходит от имени выдающегося математика средневеко­вого Востока Мухаммеда аль-Хорезми.

Понятие алгоритма так же фундаментально для информатики, как и понятие инфор­мации.

Слово «алгоритм» происходит от имени выдающегося математика средневеко­вого Востока Мухаммеда аль-Хорезми.

Им были предложены приемы выполнения ариф­метических вычислений с многозначными числами (они всем хорошо знакомы из школь­ной математики). Позже в Европе эти приемы назвали алгоритмами от «Algorithmi» — латинского написания имени аль-Хорезми. В наше время понятие алгоритма понимается шире, не ограничиваясь только арифметическими вычислениями.

это точное предписание, которое определяет процесс, ведущий от исходных данных к требуемому конечному результату

Примеры: правила сложения, умножения, решения алгебраических уравнений и т.п.

АЛГОРИТМ-

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

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

• ВЫЧИСЛИТЕЛЬНЫЕ алгоритмы , работающие с простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;
• ИНФОРМАЦИОННЫЕ алгоритмы , представляющие собой набор простых процедур, работающих с большими объемами информации (алгоритмы баз данных);
• УПРАВЛЯЮЩИЕ алгоритмы , генерируют различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми алгоритмы управляют.

Классы алгоритмов

По типу передачи управления алгоритмы бывают:

основные (главные выполняемые программы)

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

Для задания алгоритма необходимо описать следующие его элементы:

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

https://yandex.ru/video/preview/4164280568798066000

• СИМВОЛЬНЫЙ , когда алгоритм описывается с помощью специального набора символов ( специального языка ).
• СЛОВЕСНАЯ форма записи алгоритмов обычно используется для алгоритмов, ориентированных на исполнителя-человека . Команды такого алгоритма выполняются в естественной последовательности, если не оговорено противного.
• ГРАФИЧЕСКАЯ запись с помощью блок-схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками.

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

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

Виды блоков

Виды блоков

Виды блоков

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

Правила создания блок-схем:

Процесс построения АЛГОРИТМА (алгоритмизация) – разложение задачи на элементарные действия или операции

Исходные (входные) данные

АЛГОРИТМ

Выходные данные (результат)

В линейном алгоритме операции выполняются последовательно, в порядке их записи.

Каждая операция является самостоятельной, независимой от каких-либо условий.

На схеме блоки, отображающие эти операции, располагаются в линейной последовательности.

Пример. Составить алгоритм запуска программы Paint в ОС Windows.

Линейный алгоритм

Начало

Решение :

• Вспомним порядок действий для запуска программы Paint.

• Войти в меню «Пуск».
• Войти в пункт «Все программы».
• Войти в пункт «Стандартные».
• Выбрать программу «Paint».

Меню ПУСК

Все программы

Стандартные

Paint

Конец

Пример 2. Составьте алгоритм для перехода дороги на светофоре.

Пример. Составьте алгоритм для перехода дороги на светофоре.

Начало

• Подойти к светофору.
• Посмотреть на его свет.
• Если горит зелёный, то перейти дорогу.
• Если горит красный, то подождать, пока загорится зелёный, и уже тогда перейти дорогу.

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

НЕТ

ДА

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

Решение :

Возможны следующие ситуации: в тот момент, когда мы подошли к дороге горел красный или зелёный свет. Если горел зелёный свет, то можно переходить дорогу. Если же горел красный свет, то необходимо дождаться зелёного – и уже тогда переходить дорогу.

Таким образом, алгоритм имеет следующий вид:

Перейти

Дождаться зеленого света

Конец

16

Решение :

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

Составить алгоритм перевода чисел из десятичной системы в двоичную.

То есть, алгоритм будет выглядеть так:

16

«Чтение» алгоритмов

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

Составьте алгоритмы по известным русским сказкам

Как убить Кощея?

• «Смерть моя – на конце иглы, которая в яйце, яйцо – в утке, утка – в зайце, заяц в сундуке сидит, сундук на крепкий замок закрыт и закопан под самым большим дубом на острове Буяне, посреди моря-океяна …»

На распутье…

• На камне написано:
• «Направо пойдёшь – коня потеряешь, себя спасёшь; налево пойдёшь – себя потеряешь, коня спасёшь; прямо пойдёшь – и себя и коня потеряешь».

16

Репка

• Вспомним сюжет сказки: дед тянет-потянет – вытянуть не может. Затем на помощь к деду по очереди подходят новые персонажи – и так до тех пор, пока не приходит мышка.

У студента имеются накопления в сумме S рублей. Ежемесячная стипендия составляет А рублей, расходы на проживание превышают стипендию и составляют В рублей/мес. накануне начала учебы. Рост цен ежемесячно увеличивает расходы на 2% по сравнению с расходами предыдущего месяца.

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

Постройте алгоритм

16

Задавая a и b, вычислить значения функции z=sin x + cos y, где x=a+cos|a 2 -2ab|

Постройте алгоритм

Составить родословное дерево потомков Владимира Мономаха в виде графа.

Потомки Владимира Мономаха:

Владимир Мономах умер в 1125 г. Он оставил 4 сыновей: Мстислава (год смерти - 1132), Ярополка (1139), Вячеслава Туровского (1154) и Юрия Долгорукого (1157). После Мстислава осталось 3 сына: Изяслав Волынский (1154), Всеволод Новгородский (1138) и Ростислав Смоленский (1168). У Изяслава Волынского был сын Мстислав(1170), у Мстислава сын Роман (1205), у Романа - Даниил Галицкий (1264). Ростислав Смоленский имел 4 сыновей: Романа (1180), Рюрика (1215), Давида (1197) и Мстислава Храброго (1180). После Романа Ростиславича остался сын Мстислав Киевский (1224), после Мстислава Храброго - сын Мстислав Удалой (1228). Юрий Долгорукий имел 3 сыновей: Андрея Боголюбского (1175), Михаила (1177) и Всеволода (1212).