Основы алгоритмизации. Типы алгоритмов. (Лекция 1)

Сентябрь 7, 2022

Главная
Алгебра
Основы алгоритмизации. Типы алгоритмов. (Лекция 1)

Содержание

2. Понятие и свойства алгоритма Алгоритм – это набор точных предписаний, последовательное выполнение которых однозначно приводит задачу
3. Детерминированность(определенность,точность) – четкость и ясность всех предписаний: исполнителю алгоритма должно быть точно известно, какая команда алгоритма
4. Существуют следующие способы записи алгоритмов: словесно-формульная запись графическая запись (схема алгоритма, иначе, графическая схема алгоритма, блок-схема)
5. Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении
6. Алгоритм может быть следующим: задать два числа если числа равны, то взять любое из них в
7. Графическая схема алгоритма состоит из отдельных блоков, связанных линиями потоков Каждый блок описывает конкретный шаг алгоритма
8. Процесс Символ отображает функцию обработки данных любого вида. Предопределенный процесс Символ отображает предопределенный процесс, состоящий из
9. Данные Символ отображает данные, носитель данных не определен. Решение Символ отображает решение или функцию переключательного типа,
10. Линия Символ отображает поток данных или управления Соединитель Символ отображает выход в часть схемы и вход
11. . Терминатор Символ отображает начало или конец схемы программы, внешнее использование и источник или пункт назначения
12. Текст, описывающий функцию символа, следует располагать внутри данного символа. Если текст не помещается внутри символа, следует
13. Правила выполнения соединений: Стандартное направление линий потока – слева направо и сверху вниз Если направление потока
15. . Типы алгоритмов Теорема Дейкстра. Алгоритм любой сложности можно реализовать, используя только три конструкции: следования (линейные),
17. . начало Выкопать в земле ямку Опустить в ямку саженец Засыпать ямку с саженцем землей Полить
18. В схеме разветвляющийся алгоритм представляется в виде типовых структур Ветвление и выбор Разветвляющийся - алгоритм, в
19. Ветвление и выбор Полная форма Неполная форма
20. . Если друг на день рожденья Пригласил тебя к себе, То оставь подарок дома – Пригодится
22. Жена отправляет программиста в магазин. Купи батон колбасы и если будут яйца купи десяток. Программист -
23. В схеме циклический алгоритм представляется в виде типовой структуры цикл: Циклический - алгоритм, в котором некоторая
25. Алгоритм поиска Золушки:
26. Итак, алгоритмы делятся на линейные разветвляющиеся циклические ( можно также выделить в отдельный тип смешанные).
27. Алгоритмы могут классифицироваться и по другому направлению. Комбинаторные алгоритмы: Общие комбинаторные алгоритмы (например, генерация случайных чисел
29. Скачать презентацию

Слайд 2

Понятие и свойства алгоритма
Алгоритм – это набор точных предписаний, последовательное выполнение

которых однозначно приводит задачу к решению за конечное число шагов.
Алгоритм обладает следующими свойствами:

Слайд 3

Детерминированность(определенность,точность) – четкость и ясность всех предписаний: исполнителю алгоритма должно быть

точно известно, какая команда алгоритма выполняется следующей («Уходя, гасите свет»)
Результативность – способность алгоритма приводить к решению задачи за конечное число шагов
дискретность – предписание представляет собой последовательность четко выраженных отдельных команд, причем, выполнив одну команду, исполнитель выполняет другую команду, промежуточных состояний нет
массовость (универсальность) – применимость алгоритма к решению задач определенного класса, чем шире этот класс, тем ценнее алгоритм

Слайд 4

Существуют следующие способы записи алгоритмов:
словесно-формульная запись
графическая запись (схема алгоритма, иначе, графическая

схема алгоритма, блок-схема)
запись на конкретном языке программи-рования

Слайд 5

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных.

Алгоритм задается в произвольном изложении на естественном языке.
Пример.
Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Евклида).

Слайд 6

Алгоритм может быть следующим:
задать два числа
если числа равны, то

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

Слайд 7

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

описывает конкретный шаг алгоритма
Схемы алгоритмов должны соответствовать действующим стандартам на оформление схем алгоритмов, программ, данных и систем
[ГОСТ 19.701-90].
Ниже приводятся некоторые символы, определенные в стандарте и рекомендуемые к использованию в графических схемах алгоритмов.

Слайд 8

Процесс
Символ отображает функцию обработки данных любого вида.
Предопределенный процесс
Символ отображает предопределенный процесс,

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

Слайд 9

Данные
Символ отображает данные, носитель данных не определен.
Решение
Символ отображает решение

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

Слайд 10

Линия
Символ отображает поток данных или управления
Соединитель
Символ отображает выход в часть

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

Слайд 11

.
Терминатор
Символ отображает начало или конец схемы программы, внешнее использование и

источник или пункт назначения данных.
Комментарий

Слайд 12

Текст, описывающий функцию символа, следует располагать внутри данного символа.
Если текст

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

Слайд 13

Правила выполнения соединений:
Стандартное направление линий потока – слева направо и сверху

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

Слайд 14

Слайд 15

.
Типы алгоритмов
Теорема Дейкстра. Алгоритм любой сложности можно реализовать, используя только три

конструкции: следования (линейные), выбора (ветвления) и повторения (циклические).

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

В схеме линейный алгоритм представляется в виде типовой структуры следование:

Эдсгер Вибе Дейкстра

Слайд 16

Слайд 17

.
начало
Выкопать в земле ямку
Опустить в ямку саженец
Засыпать ямку с саженцем землей
Полить

саженец водой

конец

Слайд 18

В схеме разветвляющийся алгоритм представляется в виде типовых структур
Ветвление и

выбор

Разветвляющийся - алгоритм, в котором некоторые действия выполняются один раз или не выполняются в зависимости от заданного условия.

Слайд 19

Ветвление и выбор
Полная форма
Неполная форма

Слайд 20

.
Если друг на день рожденья Пригласил тебя к себе, То оставь подарок дома

– Пригодится самому…

Слайд 21

Слайд 22

Жена отправляет программиста в магазин.
Купи батон колбасы и если будут яйца

купи десяток.

Программист - продавцу. - У вас яйца есть? - Есть! - ОК. Мне 10 батонов колбасы.

Слайд 23

В схеме циклический алгоритм представляется в виде типовой структуры цикл:
Циклический -

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

Слайд 24

Слайд 25

Алгоритм поиска Золушки:

Слайд 26

Итак, алгоритмы делятся на
линейные
разветвляющиеся
циклические
( можно также выделить

в отдельный тип смешанные).

Слайд 27

Алгоритмы могут классифицироваться и по другому направлению.
Комбинаторные алгоритмы:
Общие

комбинаторные алгоритмы (например, генерация случайных чисел )

Алгоритмы на графах

Алгоритмы поиска

Алгоритмы сортировки

Алгоритмы слияния

Алгоритмы работы со строками

Основы алгоритмизации. Типы алгоритмов. (Лекция 1)

Содержание

Понятие и свойства алгоритмаАлгоритм – это набор точных предписаний, последовательное выполнение

Детерминированность(определенность,точность) – четкость и ясность всех предписаний: исполнителю алгоритма должно быть

Существуют следующие способы записи алгоритмов:словесно-формульная записьграфическая запись (схема алгоритма, иначе, графическая

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных.

Алгоритм может быть следующим: задать два числаесли числа равны, то

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

ПроцессСимвол отображает функцию обработки данных любого вида.Предопределенный процессСимвол отображает предопределенный процесс,

ДанныеСимвол отображает данные, носитель данных не определен. РешениеСимвол отображает решение

ЛинияСимвол отображает поток данных или управленияСоединительСимвол отображает выход в часть

. ТерминаторСимвол отображает начало или конец схемы программы, внешнее использование и

Текст, описывающий функцию символа, следует располагать внутри данного символа. Если текст

Правила выполнения соединений:Стандартное направление линий потока – слева направо и сверху

.Типы алгоритмовТеорема Дейкстра. Алгоритм любой сложности можно реализовать, используя только три

.началоВыкопать в земле ямкуОпустить в ямку саженецЗасыпать ямку с саженцем землейПолить

В схеме разветвляющийся алгоритм представляется в виде типовых структур Ветвление и

Ветвление и выборПолная формаНеполная форма

.Если друг на день рожденья Пригласил тебя к себе, То оставь подарок дома

Жена отправляет программиста в магазин. Купи батон колбасы и если будут яйца

В схеме циклический алгоритм представляется в виде типовой структуры цикл: Циклический -