Алгоритм и его свойства. Примеры алгоритмов презентация

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

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

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

Пример 1
Исполнитель: человек
Объекты алгоритма: ключ, дверь
Алгоритм
«Закрыть входную дверь ключом»
Вставить ключ в замочную скважину.
Повернуть ключ два раза на 180 градусов против часовой стрелки.
Вынуть ключ из замочной скважины.

Пример 3
Алгоритм «Построение перпендикуляра к прямой, проходящей через заданную точку O, лежащую на прямой с помощью циркуля и линейки»
Выполнить
Провести окружность с центром в точке O и радиусом 1 см.
Обозначить точки пересечения окружности с прямой: левую - A, правую - B.
Провести окружность с центром в точке A и радиусом равным AB.
Провести окружность с центром в точке В и радиусом равным AB.
Обозначить точки пересечения окружностей: верхнюю - C, нижнюю - D.
Провести прямую СD.

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

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

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

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

3. Табличная форма

Способы представления алгоритмов
4. Графическое описание алгоритмов (блок-схемы).
Таблица 1 - Типовые блоки блок-схем по ГОСТ 19.701–90.

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

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

2 Ветвление
Четыре разновидности ветвления

3. Цикл
Три разновидности цикла

Пример 1.
Нахождение наибольшего общего делителя
Блок-схема алгоритма решения задачи

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

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

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

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