Алгоритмы и алгоритмизация_лк5 (1)

1. ФГБОУ ВО ЧГУ им. И.Н. Ульянова факультет радиоэлектроники и автоматики кафедра автоматики и управления в технических системах

ФГБОУ ВО ЧГУ ИМ. И.Н. УЛЬЯНОВА
ФАКУЛЬТЕТ РАДИОЭЛЕКТРОНИКИ И АВТОМАТИКИ
КАФЕДРА АВТОМАТИКИ И УПРАВЛЕНИЯ В
ТЕХНИЧЕСКИХ СИСТЕМАХ
АЛГОРИТМЫ И
АЛГОРИТМИЗАЦИЯ
Лекция 1.5.
доцент Васильева Л.Н.

2.

•В
программировании
под
задачей
понимается
получение
требуемого
результата с использованием средств
программирования.
• Решение задач на ПК – совместная
деятельность программиста и компьютера,
при этом человек выполняет творческую
часть работы, а компьютер обрабатывает
информацию
в
соответствии
с
разработанной программой.

3. Алгоритм

АЛГОРИТМ
Термин происходит от
имени узбекского
математика эпохи
Возрождения альХорезми, который в IX
в.н.э. установил правила
выполнения четырех
арифметических
действий над числами в
десятичной системе
счисления.

4.

В течении длительного времени термин
«алгоритм» употреблялся преимущественно
математиками, как правило решения различных
задач.
Известна попытка Г. Лейбница (XVII в.) найти
общий
алгоритм
решения
любых
математических задач. Идея построения
алгоритма проверки правильности любой
теоремы при любой системе аксиом.

5. Алгоритмически неразрешимая задача

АЛГОРИТМИЧЕСКИ
НЕРАЗРЕШИМАЯ ЗАДАЧА
- это задача, для которой
невозможно построить
алгоритм решения.
Широкое употребление термина
«алгоритм» связано с развитием в
50-е гг. XX в. кибернетики – науки
об управлении и связи в живом и
машине.

6. Алгоритм

АЛГОРИТМ
- конечная последовательность, детерминированных
арифметических и логических действий над
исходными и промежуточными данными задачи
обработки информации, выполнение которых
приводит к правильному ее решению, т.е. получению
требуемых выходных данных.

7.

Попытки построения формального определения
алгоритма привели к возникновению
теории алгоритмов (20-30 годы XX в.)
В теорию внесли вклад
А.Тьюринг (Англия),
Э.Пост (США),
А.Н.Колмогоров (СССР),
А.А.Марков (СССР).

8.

Алгоритм
описывает
процесс
преобразования исходных данных
в результаты.
Для решения любой задачи
необходимо:
1. Ввести исходные данные.
2. Преобразовать исходные
данные в результаты (выходные
данные).
3. Вывести результаты.

9. По отношению к процессу решения данные могут быть

ПО ОТНОШЕНИЮ К ПРОЦЕССУ
РЕШЕНИЯ ДАННЫЕ МОГУТ БЫТЬ
❖исходные
❖промежуточные
❖результаты
Важно определить наименование данных, их тип,
структуру и ограничения, накладываемые на
значения.

10.

11.

• Постоянная величина – величина,
значение которой не изменяется в
процессе исполнения алгоритма, а
остается одним и тем же, указанным
в тексте алгоритма.
• Переменная величина - величина,
значение
которой
меняется
в
процессе исполнения алгоритма.

12.

Взаимосвязь понятий
Данные
Данные
Алгоритм:
1-ая команда
2-ая команда
………………..
N-ая команда
Исполнитель
Результаты

13. Исполнитель

ИСПОЛНИТЕЛЬ
Центральным
объектом
в
схеме
является Исполнитель – это тот объект
(или субъект) для управления которым
составляется алгоритм
Основной
характеристикой
исполнителя,
с
точки
зрения
управления, является система команд
исполнителя (СКИ) - это конечное
множество команд, которые понимает
исполнитель, т.е. умеет их выполнять

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

СВОЙСТВА АЛГОРИТМОВ:
Результативность;
Дискретность;
Однозначность;
Понятность;
Массовость;
Переносимость.

15. Форма записи алгоритма

ФОРМА ЗАПИСИ АЛГОРИТМА
На практике наиболее распространены следующие
формы представления алгоритмов:
• словесная (запись на естественном языке);
• графическая
символов);
(изображения
из
графических
• псевдокоды (на условном алгоритмическом языке );
•программная (тексты на языках программирования).

16. Словесное описание алгоритма

СЛОВЕСНОЕ ОПИСАНИЕ АЛГОРИТМА
представляет собой описание последовательных
этапов обработки данных. Алгоритм задается в
произвольном изложении на естественном языке
Словесный способ не имеет широкого
распространения, так как такие описания:
• строго не формализуемы;
• страдают многословностью записей;
• допускают
неоднозначность
толкования
отдельных предписаний.

17. Словесное описание алгоритма нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида)

СЛОВЕСНОЕ ОПИСАНИЕ АЛГОРИТМА НАХОЖДЕНИЯ
НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ (НОД) ДВУХ НАТУРАЛЬНЫХ
ЧИСЕЛ
(АЛГОРИТМ ЭВКЛИДА)
1.
2.
3.
4.
5.
задать два числа;
если числа равны, то взять любое из них в качестве
ответа и остановиться, в противном случае
продолжить выполнение алгоритма;
определить большее из чисел;
заменить большее из чисел разностью большего и
меньшего из чисел;
повторить алгоритм с шага 2.

18. Графическое описание алгоритма

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

19. Основные блоки графической записи алгоритма

ОСНОВНЫЕ БЛОКИ ГРАФИЧЕСКОЙ ЗАПИСИ АЛГОРИТМА

20. Общие правила проектирования графических алгортимов

ОБЩИЕ ПРАВИЛА ПРОЕКТИРОВАНИЯ
ГРАФИЧЕСКИХ АЛГОРТИМОВ
1. В начале алгоритма должны быть блоки
ввода значений входных данных.
2. После ввода значений входных данных
могут следовать блоки обработки и блоки
условия.
3. В конце алгоритма должны располагаться
блоки вывода значений выходных данных.
4. В алгоритме должен быть только один
блок начала и один блок окончания.
5. Связи
между
блоками
указываются
направленными или ненаправленными
линиями.

21. Базовые алгоритмические структуры

БАЗОВЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ
Вид алгоритма.
Ключевые
слова
Алгоритм, в котором есть структура
СЛЕДОВАНИЕ называется линейным. Ключевых слов нет.
Следование – расположение действий
друг за другом
Алгоритм, в котором есть структура Если…то…иначе…;
ВЕТВЛЕНИЕ
называется
разветвляющимся. Ветвление – выбор При…(в значении
действия от какого-либо условия.
если)
Алгоритм, в котором есть структура
ЦИКЛ называется циклическим.
Цикл – неоднократное повторение
каких-либо действий.
От…до…;
…раз;
Пока…;
Если…(в значении
пока…);
Структура

22.

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

23.

Зная длины трех сторон треугольника, вычислить
площадь и периметр треугольника.
Пусть a, b, c – длины сторон
треугольника. Необходимо
найти
S
–
площадь
треугольника, P – периметр.
Для нахождения площади
можно
воспользоваться
формулой Герона:
, где r – полупериметр.
Входные данные: a, b, c.
Выходные данные: S, P.

24.

Разветвляющиеся алгоритмы
В разветвляющемся алгоритме имеются
варианты
решения задачи
в
разные
зависимости
от результата проверки какого-либо условия.

25. Структуры ветвления

СТРУКТУРЫ ВЕТВЛЕНИЯ
ветвление
неполное ветвление
многоальтернативный
выбор

26.

Блок-схема алгоритма решения квадратного уравнения

27.

Циклические алгоритмы
Циклический алгоритм предполагает
наличие
действий,
выполняющихся
многократно.

28.

Вычислить факториал числа n (n!=1×2×3 …×n)
Входные данные: n – целое
число, факториал которого
необходимо вычислить.
Выходные данные: factorial–
значение факториала числа
n, произведение чисел от 1
до n, целое число.
Промежуточные данные:
I – целочисленная
переменная, принимающая
значения от 2 до n с шагом 1,
параметр цикла.