Алгоритм – это последовательность элементарных шагов, выполнение которой позволяет получать однозначный результат (не зависящий от того, кто выполнял эти шаги) или за конечное число шагов прийти к выводу о том, что решения не существует. Задача называется алгоритмически неразрешимой, если не существует машины, модели или алгоритма, которые ее бы решали.
Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Создание алгоритма, пусть самого простого, — процесс творческий. Другое дело – реализация уже имеющегося алгоритма, ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не способен его понять.
Такой субъект или объект принято называть формальным исполнителем. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Совокупность действий (шагов) образует систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя.
Свойства алгоритмов
Технологическая информатика. Лекция 1. Алгоритмы, графические символы и блок-схемы
Несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от других инструкций:
· дискретность – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых или ранее определенных шагов; каждое действие исполняется только после того, как закончилось исполнение предыдущего;
· определенность – каждое действие, правило алгоритма должно быть четким, однозначным и не оставлять место для произвола, и не требовать никаких дополнительных указаний или сведений о решаемой задаче;
· результативность – алгоритм должен приводить к решению задачи за конечное число шагов;
· массовость – алгоритм должен быть применим для некоторого класса задач, различающихся только исходными данными.
Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам.
Первое правило – необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (в виде, удобном для записи, поиска и хранения в ПК) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, в результате своей работы выдает данные, которые называются выходными.
Второе правило – для работы алгоритма требуется память. В памяти размещаются входные, выходные и промежуточные данные. Поименованная ячейка памяти называется переменной. В теории алгоритмов размеры памяти не ограничиваются.
Третье правило – дискретность.
Четвертое правило – детерменированность. После каждого шага (действия) необходимо указывать, какой шаг выполняется следующим, либо дать команду остановки.
Пятое правило – сходимость (результативность). Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считается результатом работы алгоритма.
Виды алгоритмов
Виды алгоритмов как логико-математических средств:
· механические – или детерминированные, жесткие, задают определенные действия в единственной и достоверной последовательности, обеспечивая однозначный и требуемый результат;
Лекція 1.1. Алгоритм. Схема алгоритма
· гибкие – дают последовательность нахождения решения задачи несколькими путями или способами, или это такие алгоритмы, в которых достижение результата однозначно не определено;
· линейные – набор действий, выполняемых во времени последовательно, друг за другом;
· разветвляющиеся – алгоритмы, содержащие хотя бы одно условие, в результате проверки которого программа переходит к одному из двух возможных шагов;
· циклические – алгоритмы, предусматривающие многократное повторение одного и того же действия, но над новыми данными;
· подчиненные (вспомогательные) – алгоритмы, ранее разработанные и целиком использованные при алгоритмизации задачи (обычно на их основе создаются подпрограммы).
Процессы вычислений циклической структуры в свою очередь можно разделить на три группы:
· циклические процессы, для которых количество повторений известно – счетные циклы или циклы с заданным количеством повторений;
· циклические процессы, завершающиеся по достижении или нарушении некоторых условий — итерационные циклы;
· циклические процессы, из которых возможны два варианта выхода: по завершении процесса и досрочный выход по какому-либо дополнительному условию – поисковые цикл ы.
Методы изображения алгоритмов
На практике распространены формы представления алгоритмов:
· словесная — в виде последовательности записей на естественном языке;
· графическая — в виде совокупности графических знаков;
· псевдокоды – полуформализованное описание алгоритма на условном языке, включающем в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.;
· программная – текст на языке программирования.
Запись алгоритмов на естественном языке (словесная форма) не получила широкого распространения, из-за отсутствия наглядности; ввиду возможности неоднозначного толкования записей, и их многословности. Пример словесной формы алгоритма:
1. Определить форматы переменных А, С и В.
2. Ввести значения А и В с клавиатуры.
3. Сравнить А и В.
4. Если А больше В, то переменной С присвоить значение А.
5. Если В больше А, то переменной С присвоить значение В.
6. Если А равно В, переменной С присвоить значение 0.
7. Вывести на экран значения А, В и С.
Запись алгоритма в виде совокупности графических знаков называется блок-схемой, и получила широкое распространение в научной и учебной литературе. На изображение схем алгоритмов существует ГОСТ 19.701-90. Знаки (блоки) соединены линиями информационного потока (стрелками); каждый знак имеет определенный смысл (см. табл. 1) и соответствует одному шагу (действию) алгоритма.
Внутри блока дается описание соответствующего действия. Для простоты чтения схем желательно, чтобы линия входила в блок сверху, а выходила снизу, или шла слева направо. Блоки должны быть одного масштаба. В случае, когда схема алгоритма не умещается на листе, используются соединители. В Microsoft Word для выполнения алгоритмов используется панель инструментов «Рисование – Автофигуры – Блок-схема».
Выполнение алгоритма в виде блок-схемы перед программированием существенно облегчает процесс создания и отладки программы, определения форматов и перечня переменных, поиск ошибок, редактирование алгоритма в будущем.
Знаки для изображения схем алгоритмов
| Обозначение (графическое изображение) | Название | Назначение | Наименование автофигуры в Word |
| Терминатор | Начало или завершение программы или подпрограммы | Знак завершения | |
| Процесс | Обработка данных (вычисления, пересылки т.п.) | Процесс | |
| Решение | Ветвления, выбор, итерационные и поисковые циклы | Решение | |
| Данные | Операции ввода-вывода | Данные | |
| Подготовка | Счетные циклы | Подготовка | |
| Документ | Вывод на бумагу | Документ | |
| Архив | Данные, хранящиеся в архиве или взятые из архива | — | |
| Документ | Документ, подготовленный вручную | — | |
| Файл | Файл или база данных | Магнитный диск | |
| Предопреде-ленный процесс | Вызов подпрограмм (процедур) | Типовой процесс | |
| Источник или приемник данных | Указание источника или приемника данных | — | |
| Монитор | Вывод информации на экран | Дисплей | |
| Соединитель | Маркировка разрывов линий | Узел | |
| Соединитель | Маркировка разрывов линий | Ссылка на другую страницу | |
| Комментарий | Пояснения к действиям | Выноска | |
| Поток информации | Линии, связывающие блоки | Стрелка |
В теории программирования доказано [1, 2], что для записи любого сложного алгоритма достаточно трех базовых структур: следование – последовательное выполнение действий (рис. 1, а); ветвление – соответствует выбору одного из двух вариантов действий (рис. 1, б); цикл-пока – определяет повторение действий, пока не будет нарушено условие, выполнение которого проверяется в начале цикла (рис. 2).
Рис. 1. Базовые алгоритмические структуры: а) следование, б) ветвление
Рис. 2. Базовая структура: цикл-пока
На основе базовых структур строятся дополнительные структуры для изображения алгоритмов: выбор (рис. 3), цикл-до, счетный цикл.
Рис. 3. Дополнительная структура «выбор» и реализация ее через базовые структуры
Рис. 4. Дополнительная структура: цикл – до
Рис. 5. Дополнительная структура: цикл с заданным числом повторений (счетный цикл).
На основе алгоритмов создается программное обеспечение (ПО) для решения прикладных задач.
Источник: poisk-ru.ru
Блок-схема
Блок-схема — распространенный тип схем (графических моделей), описывающих алгоритмы или процессы, в которых отдельные шаги изображаются в виде блоков различной формы, соединенных между собой линиями, указывающими направление последовательности.
- 1 Стандарты выполнения
- 2 Основные элементы схем алгоритма
- 3 Представление алгоритмов в виде графов
- 4 Программы
- 5 См. также
- 6 Примечания
Стандарты выполнения [ править | править код ]
Правила выполнения схем определяются следующими документами:
- ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения. [1]
- ГОСТ 19.002-80. Схемы алгоритмов и программ. Правила выполнения. [2]
- ГОСТ 19.003-80. Схемы алгоритмов и программ. Обозначения условные графические. [3][4]
Данные документы в частности регулируют способы построения схем и внешний вид их элементов.
Основные элементы схем алгоритма [ править | править код ]
Описание других элементов схем можно найти в соответствующих ГОСТ (указаны выше).
Представление алгоритмов в виде графов [ править | править код ]
Основная статья: Граф-схема алгоритма
Порядок выполнения действий задается путем соединения вершин дугами, что позволяет рассматривать блок-схемы не только как наглядную интерпретацию алгоритма, удобную для восприятия человеком, но и как взвешенный ориентированный граф (т. н. граф-схема алгоритма, ГСА). Подобное представление алгоритмов используется при построении систем логического управления, реализующих заданные управляющие алгоритмы, в задачах распараллеливания вычислений и т. д.
Программы [ править | править код ]
Для автоматического создания блок-схем из исходных текстов программ и их создания вручную существуют свободные программы — Diagram Designer, Dia, Kivio (входит в пакет KOffice), OpenOffice.org Draw, processWave.org, yEd Graph Editor, AFCE, коммерческие программы Microsoft Visio, diamFC, также существуют программы, предоставляемые как онлайн-услуги (например, Flowchart.com и LucidChart (англ.) русск. [5] ).
См. также [ править | править код ]
- Диаграмма Насси — Шнейдермана
- UML
- Диаграмма связей
- Псевдокод (язык описания алгоритмов)
- ДРАКОН
Примечания [ править | править код ]
- ↑ абГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения
- ↑ГОСТ 19.002-80. Схемы алгоритмов и программ. Правила выполнения
- ↑ГОСТ 19.003-80. Схемы алгоритмов и программ. Обозначения условные графические. (ссылка 2)
- ↑ГОСТ 19.003-80. Схемы алгоритмов и программ. Обозначения условные графические
- ↑LucidChart
| Текущая версия статьи о компьютерах. Помогите Традиции, исправьте и дополните её. |
Эта статья ещё далека от совершенства, и для её улучшения, по меньшей мере, нужно:
- Незавершённые статьи о компьютерах
- Традиция:Статьи без ссылок на источники
- Традиция:Статьи с неверным использованием шаблона rq
- Теория алгоритмов
- Разработка программного обеспечения
- Визуализация данных
- Моделирование
- Проектирование
Источник: traditio.wiki
Алгоритмы. Блок-схемы
среда — «место обитания» исполнителя;
элементарные действия;
система команд — команды только из
некоторого строго заданного списка;
отказы — возникают, если команда
вызывается при недопустимом для нее
состоянии среды.
10. Универсальный исполнитель алгоритмов
11. 2. Этапы решения задач с использованием компьютера
12. Этапы решения задач
постановка задачи;
формализация задачи (математическая
модель);
выбор (или разработка) метода решения;
разработка алгоритма;
составление программы;
тестирование и отладка программы;
анализ результатов.
13. Классы алгоритмов
вычислительные;
информационные;
управляющие.
14. Схема работы алгоритма
Аргументы
(дано)
АЛГОРИТМ
Результаты
(найти)
15. 3. Свойства алгоритмов
16. Понятность для исполнителя
Исполнитель алгоритма должен понимать,
как его выполнять.
Алгоритм должен включать только те
команды, которые входят в его систему
команд.
17. Дискретность
Discretus (лат.) –
разделенный, прерывистый.
Алгоритм должен представлять процесс
решения задачи как последовательное
выполнение простых шагов (этапов).
18. Определенность
Каждое правило алгоритма должно быть четким,
однозначным и не оставлять места для произвольной
трактовки.
Благодаря этому свойству выполнение алгоритма
носит механический (формальный) характер и не
требует никаких дополнительных указаний или
сведений о решаемой задаче.
19. Что это?
20. Рецепт: «Всыпьте немного муки»
21. Результативность
(или конечность)
За конечное число шагов алгоритм либо должен
приводить к решению задачи, останавливаться из-за
невозможности получить решение с выдачей
соответствующего сообщения, либо неограниченно
продолжаться в течение времени, отведенного для
исполнения алгоритма, с выдачей промежуточных
результатов.
22.
Приведите пример
бесконечной команды
23. Массовость
Алгоритм решения задачи разрабатываться в общем
виде, т.е. он должен быть применим для некоторого
класса задач, различающихся лишь исходными
данными.
24. Порядок выполнения алгоритма
• действия выполняются в порядке их
записи;
• нельзя менять местами никакие два
действия алгоритма;
• нельзя не закончив одного действия
переходить к следующему.
25. 4. Формы записи алгоритма
26. Словесная
Запись на естественном языке.
1.
2.
3.
4.
Рецепт «Омлет на сковородке»
Разбить яйца в миску, взболтать их вилкой, влить
молоко, перемешать, посолить.
Подогреть сковороду с маслом.
Влить яйца и жарить минут 5 на медленном огне.
Перемешать омлет, чтобы он поджарился
равномерно.
Накрыть его крышкой и подержать минуты 2-3 так он станет пышным.
27. Псевдокод
Полуформализованные описания алгоритмов на
условном алгоритмическом языке, включающие в
себя как элементы языка программирования, так и
фразы естественного языка, общепринятые
математические обозначения и др.
28. Программная
Тексты программ (листинги) на языках
программирования.
29. Программа —
это алгоритм
для компьютера
30. Графическая
Изображения из графических символов.
Алгоритм изображается в виде
последовательности связанных между собой
функциональных блоков.
Такое графическое представление называется
схемой алгоритма или блок-схемой.
31. 5. Блок-схемы, правила их построения
32. Символы блок-схем
Начало / конец
Ввод/вывод
Действие
Логический блок
(условие)
33. Символы блок-схем
Предопределенный процесс
(подпрограмма)
Блок модификации
Соединитель
Межстраничный
соединитель
Линии
34. Правила построения блок-схем
блок-схема
выстраивается в одном
направлении: сверху вниз и слева
направо;
все
повороты соединительных линий
выполняются под углом 90º.
35. 6. Примеры алгоритмов
36.
37.
38.
39.
40.
41.
42.
43. Домашнее задание
Происхождение слова «алгоритм»
Примеры алгоритмов из окружающей
жизни
Преимущества и недостатки различных
способов записи алгоритмов
Источник: ppt-online.org