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

Основы алгоритмизации Типы алгоритмов Лекция №1 по курсу «Комбинаторные алгоритмы»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ветвление и выбор Ветвление и выбор

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