Алгоритм и его свойства

Алгоритм – это точное и понятное предписание выполнить конечную последовательность действий, направленную на решение поставленной задачи. Синонимы слова «алгоритм»: план; инструкция; рецепт; предписание.

Составитель алгоритма – человек Исполнитель алгоритма - объект, который будет выполнять алгоритм

Алгоритм представляет из себя последовательно выполняемые команды Простые: Шагни Прыгни Улыбнись Составные: Если темно, то включи свет

Примеры алгоритмов Рецепт приготовления салата Расписание уроков Режим дня Решение задачи

Режим дня школьника 1.Подъём 2. Зарядка 3. Завтрак 4. Дорога в школу 5. Занятия в школе 6. Дорога домой 7. Время игр или прогулки 8. Выполнение домашних заданий 9. Прогулка на свежем воздухе 10. Ужин 11.Сон

Свойства алгоритма Дискретность (прерывность, раздельность) - алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.

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

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

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

Правила построения алгоритма Первое правило – при построении алгоритма прежде всего необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными.

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

Правила построения алгоритма Третье правило – дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.

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

Правила построения алгоритма Пятое правило – сходимость (результативность). Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считать результатом работы алгоритма.

Виды алгоритмов: Линейный Разветвляющийся Циклический Чаще всего алгоритм представляет собой комбинацию линейных, разветвляющихся и циклических структур.

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

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

Линейный алгоритм В данном алгоритме все шаги (команды) выполняются по порядку друг за другом и только один раз. Начало команда 1 команда 2 … Конец

Разветвляющийся алгоритм В данном алгоритме, в зависимости от некоторого условия, может выполняться одна или другая последовательность шагов (команд). Полная форма условие команда 1 команда 2 … да-нет Неполная форма условие команда 1 … да-нет

Циклический алгоритм В данном алгоритме, в зависимости от некоторого условия, одна и та же последовательность шагов (команд) может выполняться несколько раз. Последовательность команд, которая многократно повторяется называется телом цикла.

Цикл-ПОКА (цикл с предусловием) Пока выполняется условие будет выполняться тело цикла. Как только условие перестает выполняться, управление передается следующей команде. условие тело цикла да-нет …

Цикл-ДО (цикл с постусловием) Тело цикла будет выполняться до выполнения условия. У такого цикла тело цикла всегда выполнится хотя бы один раз. условие тело цикла да-нет …

Бесконечный цикл Это цикл, условие которого всегда выполняется. У него отсутствует «веточка нет». условие тело цикла да

Пустой цикл Это цикл, у которого отсутствует тело цикла. условие да-нет …

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

Алгоритм Линейная структура (периметр прямоугольника) Начало ввод ( A, B) Р=2*(А+В) вывод Р Конец

Алгоритм Структура с ветвлением (вычисление функции) Начало ввод (H) A := Sin( 2 H ) B := Cos( 2 H ) если ( A > B ) и ( B > 0 )то F := A / B иначе если (A < B ) и ( B

Алгоритм Структура цикл Задача: путь дано ведёрко с белыми и красными шарами, назовём это ведёрко Первым. И ещё два пустых ведра, которые назовём Второе и Третье. Пусть нужно все белые шары положить во второе ведёрко, а все красные в третье. Алгоритм решения этой задачи будет выглядеть так: Пока Первое ведёрко не пустое делать Начало Вынуть шар из первого ведёрка Если вынутый шар белый То положить его во второе ведёрко Иначе положить его в третье ведерко Конец

Языки программирования Языки программирования – это искусственные языки записи алгоритмов для исполнения их на ЭВМ. Программирование (кодирование) - составление программы по заданному алгоритму.

Классификация языков программирования В общем, языки программирования делятся на две группы: операторные и функциональные. К функциональным относятся ЛИСП, ПРОЛОГ и т.д. Операторные языки делятся на процедурные и непроцедурные (Smalltalk, QBE). Процедурные делятся на машино - ориентированные и машино – независимые. К машино – независимым языкам относятся: Процедурно – ориентированные (Паскаль, Фортран и др.) Проблемно – ориентированные (ЛИСП и др.) Объектно-ориентированные (Си++, Visual Basic, Java и др.)

Запись алгоритма на языке Бейсик Программа вычисления выражения у=5 х+2 х 1 способ 10 input x 20 let y=5*x^2+x*2 30 print x=; x, y=,y 40 end p