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

• Точное предписание, задающее вычислительный процесс, начинающийся с произвольного набора исходных данных и направленный на получение полностью определяемых ими результатов

• Абстрактный вычислительный алгоритм применяется к математическим объектам, записывается в математических терминах и не связан с конкретным языком программирования

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

 Конечность (финитность)

◦ Всегда заканчивается после конечного числа шагов

 Определенность (детерминированность)

◦ Однозначность и недвусмысленность выполняемых действий на каждом шаге

 Результативность (направленность)

◦ Получение результата, в том числе в точках неопределенности с выдачей соответствующей информации

 Массовость

◦ Алгоритм служит для решения целого класса задач

6. Способы задания алгоритмов

Способы задания алгоритма

 Словесный

 Алгоритмические системы

 Языки программирования

 Языки схем алгоритмов

 Схемы алгоритмов Янова, Ляпунова, операторные схемы Лаврова и проч.

Алгоритм Евклида

Даны два целых положительных числа m и n

. Требуется найти их наибольший общий делитель, т.е. наибольшее положительное

целое число, которое нацело делится как на m, так и на n

. Е1. {Нахождение остатка}

Разделим m на n

. Пусть остаток равен r, где  ≤ r ≤ n

. Е2. {Проверка на нуль}

Если r = , алгоритм заканчивает работу и ответ n

. Е3. {Замена}

Положить m  n, n  r и возврат к шагу Е1.

Схема алгоритма см лист 17 лекции 3

7. Простые схемы алгоритмов. Типовые структуры

Схема алгоритма см лист 17-18 лекции 3

8. Синтаксические диаграммы циклов

Не знаю где это!!!

10. Структурный подход к проектированию алгоритмов и программ

Нисходящая разработка

 это проектирование сверху – вниз (top-down), декомпозиция и пошаговая разработка алгоритмов (декомпозиция – представление сложного объекта в виде совокупности простых)

◦ решение частных задач приводит к решению общей задачи

◦ выбранная последовательность индивидуальных действий разумна

◦ выбранная декомпозиция позволяет получить инструкции, в каком - либо смысле более

близкие к языку, на котором в конечном счете будет сформулирована программа

Восходящая разработка

 это проектирование снизу - вверх (down-top), разработка алгоритмов путем объединения инструкций в элементарные процедуры («кластеры действий»)

 элементарные процедуры затем используются на следующем, более высоком уровне иерархии процедур

11. Структурное программирование. Теорема о структуризации

◦ Разработка ясных, локально простых, удобочитаемых программ с древовидной

Структурой

◦ Программирование с использованием только базовых конструкций

 Основная теорема

Любая простая программа функционально эквивалентна структурированной программе,

составленного из элементов базисного множества (следование, ветвление, цикл) с

исполнением функций и предикатов исходной программы, а также присваиваний и тестов

над дополнительным счет

12. Обращение неструктурированных программ в структурированные

 дублирование процессов

 введение переменной состояния

 метод булевских функций

Эти три стратегии преобразования программ помогают овладеть методами проектирования и понимания алгоритмов и программ

13. Метод дублирования процессов

См лист 6-7 лекции 4

14. Метод булевского признака

См лист 11-13 лекции 4

15. Метод переменной состояния

См лист 8-10 лекции 4

16. Программирование. Общие понятия