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

1. АЛГОРИТМ И ЕГО СВОЙСТВА

ПРИМЕРЫ АЛГОРИТМОВ

2. Алгоритм — точное описание последовательности элементарных действий, которые необходимо выполнить исполнителю для выполнения

работы, решения задачи.
Более 1000 лет назад (в 825 году)
ученый из города Хорезма Абдулла (или
Абу Джафар) Мухаммед бен Муса альХорезми создал книгу по математике, в
которой описал способы выполнения
арифметических
действий
над
многозначными числами.

3.

!
Исполнитель алгоритма – человек или автомат способный
выполнять ограниченный набор элементарных действий.
Неформальный
исполнитель
понимает смысл алгоритма,
может его корректировать и
изменять, а также отказаться
выполнять
одну и ту же команду
выполняет каждый раз поразному
неформальный исполнитель сам
отвечает за свои действия
в
роли
неформального
исполнителя
чаще
всего
Художник Василий
Тропинин «Золотошвейка» (1826)
выступает
человек
Формальный
исполнитель
не размышляет над выполняемыми командами, а строго
следует пошаговым инструкциям алгоритма
одну и ту же команду всегда
выполняет одинаково
за
действия
формального
исполнителя отвечает управляющий им объект
в роли формального исполнителя чаще всего выступает
техническое устройство

4.

Исполнителя характеризуют:
• Среда - это «место обитания» исполнителя (Turbo-Pascal);
• элементарные действия (команда – это предписание
исполнителю совершить элементарное действие, преданное на
доступном языке);
• система команд - набор всех команд исполнителя;
• отказ - это ситуация, в которой исполнитель не может выполнить
команду.

5. Пример 1

МК
Свойства алгоритма
Дискретность
Детерминированность
Понятность
Результативность
Массовость
Массовость
Дискретность
Детерминированность
Понятность
Результативность
Выполнение
Каждая
При
Алгоритм
точном
команда
пригоден
не
алгоритма
исполнении
алгоритма
должен
для решения
разбивается
определяет
содержать
команд
любой
на
последовательность
однозначное
предписаний,
алгоритма
задачи
из некоторого
процесс
действие
смысл
должен
законченных
класса
которых
исполнителя,
прекратиться
задач,
может
дейстт. е.
и
вий-шагов.
недвусмысленно
восприниматься
за
алгоритм
конечное
правильно
Только
число
исполнителем
указывает,
шагов,
работает
выполнив
и при
на
неоднокакая
некоодно
этом
действие,множестве
команда
значно,
должен
тором
т.
быть
должна
е. можно
запись
получен
выполняться
исходных
алгоритма
ответ
приступать
на данных,
следуюдолжна
вопроск
выполнению
щей.
быть
задачи.
которое
настолько
Многократное
Вназывается
качестве
следующего.
чёткой
одного
областью
выполнение
и полной,
из Произвести
возможных
применичтобы
алго-у
каждоеалгоритма.
ритма
исполнителя
ответов
мости
при
отдельное
может
одном
не возникло
быть
действие
иустановление
томпотребности
исполнителю
же наборе
тогов
предписывает
входных
принятии
факта,
что задача
данных,
каких-либо
специальное
решений
дает
самостоятельных
неодинаковые
указание
имеет.
в
записи алгоритмаи –выходной
промежуточные
решений.
команда.результаты.

6. Пример 3

МК
1 Дискретность. Процесс решения задачи должен быть
разбит на последовательность отдельных шагов,
выполняемых строго один за другим.
2. Понятность. Алгоритм должен быть понятен
исполнителю, и он должен быть в состоянии выполнить
его команды.
3. Детерминированность. Будучи понятным, алгоритм
не должен содержать команды, смысл которых может
восприниматься неоднозначно.
4. Результативность. При точном исполнении
алгоритма процесс решения задачи должен
прекратиться за конечное число шагов и при этом
должен быть получен результат.
5. Массовость. Алгоритм должен обеспечивать решение
всего класса задач данного типа. Это свойство
характерно для алгоритмов, реализуемых на ЭВМ.

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

Способы представления алгоритмов
1. Словесно-формульное описание. Состоит из перечня
действий, каждый из которых имеет порядковый номер.
Выполняется алгоритм последовательно, шаг за шагом.
Используется для решения несложных задач из-за отсутствия
наглядности.
Пример
1. Присвоить переменным “a” и “b” численные значения.
2. Найти сумму квадратов величин “a” и “b” и присвоить
эту величину переменной “х”.
3. Найти произведение величины “x” на сумму величин “a”
и “b” и присвоить эту величину переменной “y”.

8.

2. Математическая форма записи алгоритмов
Пример
ДАНО:
Вид уравнений
x = a2 + b2, y = x*(a + b) заданы коэффициенты а,b
НАЙТИ:
Значение У
РЕШЕНИЕ:
Вычислить значение х, подставив значения
коэффициентов a,b
x = a2 + b2
Вычислить значение y, подставив значения
коэффициентов a,b и вычисленное ранее значение х
y = x*(a + b)

9.

3. Табличная форма
a
b
a2 + b2
x*(a + b)
1
2
5
15
3
4
25
175

10. 2. Математическая форма записи алгоритмов

Способы представления алгоритмов
4. Графическое описание алгоритмов (блок-схемы).
Таблица 1 - Типовые блоки блок-схем по ГОСТ 19.701–90.
Наименование
1. Данные
Обозначение
Описание
Этот символ используется для обозначения операций ввода
данных и вывода результатов, не конкретизируя устройства ввода
или вывода
2. Процесс
Обработка данных любого вида (действие, выполнение
определенной операции или группы операций). Внутри символа
указываются выполняемые действия. Например, операции
присваивания, вычисления
3. Подготовка
Модификация команды или группы команд (установка
переключателя, модификация индексного регистра). Внутри
символа записывается имя переключателя и условия его
модификации

11.

4. Предопределенный
процесс
5.
Использование ранее созданных алгоритмов и программ. Внутри
блока записывается имя подпрограммы и параметры, при которых
программа будет выполняться
Решение
а)
б)
Выбор направления вычисления алгоритма в зависимости от
условия. Возможны
•один вход и ряд альтернативных выходов (а).
В случае, если символ имеет несколько выходов, то их следует
показывать:
• несколькими линиями от данного символа к другим символам (б);
• одной линией от данного символа, которая затем разветвляется в
соответствующее число линий (в).
Внутри символа записывается проверяемое условие
в)
6. Граница цикла
Символ, состоящий из двух частей, отображает начало и конец
цикла. Блоки, составляющие тело цикла, записываются между
этими символами
7. Соединитель
Символ отображает выход в часть схемы и вход из другой части
этой схемы и используется для обрыва линии и продолжения ее в
другом месте
8. Терминатор
Начало или конец схемы
9. Комментарий
Символ используют для добавления описательных комментариев
или пояснительных записей

12.

5. Описание на каком-либо языке программирования
(программа).
Программа - это форма представления алгоритма для исполнения его машиной.
Пример
15
0127
сложить
число
2677
3656
с числом Результат поместить в ячейку с данным адресом
Программирование это процесс описания алгоритма решения задачи
посредством использования языков программирования, т.е. в виде программы.
Естественные языки. Они возникают в некоторой социальной группе для общения её членов. Для них
характерно
1) многозначность слов, наличие синонимов;
2) зависимость слов и выражений от контекста;
3) нечёткость правил построения выражений.
Искусственные языки. Для них характерно чёткое разграничение синтаксической и семантической
(смысловой) частей, однозначная определённость словаря. Контекстно-независимы. К таким языкам
относятся разные формализованные языки, включая языки программирования.
Формализованные языки - система языковых средств или их символов с жёсткими законами их
сочетаемости.

13.

Базовые алгоритмические структуры
1.Следование
Действие 1
Действие 2
…………..
Действие n

14.

2 Ветвление
Четыре разновидности ветвления
F
Условие 1
условие
T
Действие 1
Условие 2
Действие 1
T
Действие 2
.......................................
................
F
Условие n
F
T
условие
Действие 1
F
Условие 2
T
Действие 2
F
F
«если….то»
T
F
F
T
Условие 1
T
Действие n
...........................................
............
F
Условие n
T
Действие n
F
Действие (n+1)
Действие 1
Действие 2
Структура
«выбор»
Структура «выбор…иначе»
«если…то…иначе»

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

3. Цикл
Три разновидности цикла
для i=1 до n
действие
Условие
F
«цикл с
предусловием»
T
действие
Условие
T
действие
F
«цикл с
постусловием»
«цикл со счётчиком»

16. 2 Ветвление

Пример 1.
Нахождение наибольшего общего делителя
Блок-схема алгоритма решения задачи
начало
Ввод a, b
a=b
Т
Вывод а
F
a:= a - b
Т
a>b
F
b:= b - a
конец

17. 3. Цикл

Пример 2.
Вычисление среднего арифметического n чисел
1 n
Блок-схема алгоритма s xi
n i 1
начало
Ввод n
s:=0
для i =1 до n
ввод чисел хi
s:=s + xi
s:= s/n
вывод s
конец

18. Пример 1. Нахождение наибольшего общего делителя

Процесс создания и этапы обработки
программы
Для создания программы нужны:
Текстовый редактор.
Транслятор.
Редактор связи.
Отладчик.
Загрузчик.
Библиотека стандартных функций.

19. Пример 2. Вычисление среднего арифметического n чисел

Этапы обработки программы
Текст программы
(исходный модуль)
Компиляция
Этап
трансляции
Объектный модуль
Редактор
связей
Этап сборки
Загрузочный модуль
Загрузчик
Результаты счета
Этап
загрузки
Исходные
данные

20. Процесс создания и этапы обработки программы

1. Этап трансляции
Программа, записанная на языке высокого уровня, называется исходным
модулем. Существует два способа трансляции исходного модуля:
Интерпретация;
Компиляция.
Интерпретатор
осуществляет
пооператорную
трансляцию
и
выполнение
программы в оперативной памяти (синхронный перевод речи иностранца).
Компилятор преобразует исходный код в объектный, адрес загрузки которого
обычно не привязан к конкретному адресу оперативной памяти (заблаговременно
переведенный доклад, который в дальнейшем будет озвучен).
После компиляции программы исходный модуль превращается в объектный
модуль

21. Этапы обработки программы

2.Этап сборки (компоновки)
На базе полученных в ходе компиляции объектных модулей и модулей
разнообразных библиотек создается загрузочный модуль. Сборка программных
модулей осуществляется редактором связи (компоновщиком, линкером).
3. Этап загрузки
Загрузочный модуль это законченная программа с расширением *.exe, *.com, которую
можно запустить на любом компьютере.