Лекция 1_ОАИП_2020

03.09.2020
Романькова Т.Л.
Понятие и свойства алгоритма
Алгоритм – это набор точных предписаний, последовательное выполнение которых однозначно приводит задачу к решению за конечное число шагов.
Алгоритм обладает следующими свойствами:

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

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

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

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

03.09.2020
Романькова Т.Л.
Псевдокод

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

03.09.2020
Романькова Т.Л.
Процесс
Символ отображает функцию обработки данных любого вида.
Предопределенный процесс
Символ отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле).

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

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

03.09.2020
Романькова Т.Л.
Терминатор
Символ отображает начало или конец схемы программы, внешнее использование и источник или пункт назначения данных.
Комментарий

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

03.09.2020
Романькова Т.Л.

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

03.09.2020
Романькова Т.Л.

03.09.2020
Романькова Т.Л.
То, что не понял на лекции, поймешь на экзамене!
Профессор на лекции:
- Студенты, не стесняйтесь, спрашивайте. Глупых вопросов не бывает, бывают только глупые ответы.
- Господин профессор, а если я встану на трамвайные рельсы двумя ногами, а руками схвачусь за токопроводящую линию, я поеду как трамвай?

03.09.2020
Романькова Т.Л.
Типы алгоритмов
Теорема Дейкстра. Алгоритм любой сложности можно реализовать, используя только три конструкции: следования (линейные), выбора (ветвления) и повторения (циклические).
Линейный - алгоритм, в котором все указанные действия выполняются один раз в том порядке, в котором они записаны.
В схеме линейный алгоритм представляется в виде типовой структуры следование:
Эдсгер Вибе Дейкстра

03.09.2020
Романькова Т.Л.

03.09.2020
Романькова Т.Л.
Например, алгоритм посадки дерева:
Выкопать в земле ямку;
Опустить в ямку саженец;
Засыпать ямку с саженцем землей;
Полить саженец водой.

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

03.09.2020
Романькова Т.Л.
В схеме разветвляющийся алгоритм представляется в виде типовых структур
Ветвление и выбор
Разветвляющийся - алгоритм, в котором некоторые действия выполняются один раз или не выполняются в зависимости от заданного условия.

03.09.2020
Романькова Т.Л.
Ветвление и выбор
Полная форма
Неполная форма

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

03.09.2020
Романькова Т.Л.

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

03.09.2020
Романькова Т.Л.
В схеме циклический алгоритм представляется в виде типовой структуры цикл:
Циклический - алгоритм, в котором некоторая последовательность действий может выполняться несколько раз в зависимости от заданного условия.

03.09.2020
Романькова Т.Л.

03.09.2020
Романькова Т.Л.
Алгоритм поиска Золушки:

03.09.2020
Романькова Т.Л.
Итак, алгоритмы делятся на
линейные
разветвляющиеся
циклические
( можно также выделить в отдельный тип смешанные).

03.09.2020
Романькова Т.Л.
Пример1. Вычислить значение функции
,где

03.09.2020
Романькова Т.Л.
Исходными данными являются ω, t, x.
Результат – f.
Промежуточная величина – h.

03.09.2020
Романькова Т.Л.
Вычисление h
начало
Ввод
ω, t, x
Вычисление f
Вывод
ω, t, x,f
конец

Пример 2. Составить алгоритм вычисления функции.
Предусмотреть вывод номера расчетной формулы.

начало
Ввод
х
π
<
<
x
0
5
.
2
sin
2
2
−
=
x
x
y
N=1
x
x
y
2
2
sin
4
+
=
N=3
Вывод
x, y, n
0
Ј
x
5
.
7
cos
2
3
−
+
=
x
x
y
N=2
Конец
да
нет
да
нет

Пример3. Примером разветвляющегося алгоритма может служить алгоритм начисления стипендии по среднему баллу.
- в качестве исходного данного задается значение среднего балла сдачи сессии студеном;
- если средний балл меньше 4, то стипендия – 0$;
- если средний балл больше 8, то начисляется стипендия в 500$;
- в остальных случаях начисляется стипендия размером в 200$;
- выводится значение начисленной стипендии.

03.09.2020
Романькова Т.Л.
Пример 4. Составить алгоритм вычисления функции для значений аргумента x, изменяющегося в интервале от xнач до xкон с шагом ∆x, и заданных констант a и b. Такая задача называется задачей о табулировании функции.

03.09.2020
Романькова Т.Л.

03.09.2020
Романькова Т.Л.
Пример 5. Ниже приведен алгоритм вычисления

03.09.2020
Романькова Т.Л.
Алгоритмы могут классифицироваться и по другому направлению.
Комбинаторные алгоритмы:
Общие комбинаторные алгоритмы (например, генерация случайных чисел )
Алгоритмы на графах
Алгоритмы поиска
Алгоритмы сортировки
Алгоритмы слияния
Алгоритмы работы со строками

03.09.2020
Романькова Т.Л.
Алгоритмы сжатия данных
Криптографические алгоритмы
Цифровая обработка сигналов
И т.д.
Теоретико-числовые алгоритмы

03.09.2020
Романькова Т.Л.
Основные принципы разработки и анализа алгоритмов
При построении алгоритма для сложной задачи используют системный подход с использованием декомпозиции (нисходящее проектирование сверху-вниз) и синтеза (программирование снизу-вверх). При формировании алгоритма используют дедуктивный и индуктивный методы.
При дедуктивном подходе рассматривается частный случай общеизвестных алгоритмических моделей. Здесь при заданных предположениях известный алгоритм приспосабливается к условиям решаемой задачи.
Индуктивный способ предполагает эвристический системный подход. В этом случае общих и наиболее удачных методов не существует. Возможны некоторые подходы, позволяющие в каждом конкретном случае находить и строить алгоритмы.

03.09.2020
Романькова Т.Л.
Одним из системных методов разработки алгоритмов является структурное программирование.
Принципы структурного программирования:
Принцип абстракции.
Этот принцип позволяет разработчику рассматривать программу в нужный момент без лишней детализации. Детализация увеличивается при переходе от верхнего уровня абстракции к нижнему.

03.09.2020
Романькова Т.Л.
Принцип формальности.
Он предполагает строгий методический подход к программированию, придает творческому процессу определенную строгость и дисциплину
Принцип модульности.
В соответствии с этим принципом программа разделяется на отдельные законченные фрагменты, модули, которые просты по управлению и допускают независимую отладку и тестирование. В результате отдельные ветви программы могут создаваться разными группами программистов.