Алгоритм. Лекция 1

1. Алгоритм

1.
2.
3.
4.
5.
ПОНЯТИЕ АЛГОРИТМА
СВОЙСТВА АЛГОРИТМОВ
СПОСОБЫ ЗАПИСИ АЛГОРИТМОВ
ПРАВИЛА ПОСТРОЕНИЯ СХЕМЫ АЛГОРИТМА
ЗАДАЧИ
ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ

2.

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

3.

Само слово «алгоритм» возникло в Европе после перевода на
латынь его книги, в которой имя писалось как «Алгоритми»
Научное определение понятия алгоритма было дано в 1930 году

4. Алгоритм -

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

5.

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

6.

формальное описание способа решения задачи путем разбиения ее
на последовательность элементарных операций
«Формальное» означает, что описание должно быть абсолютно
полным и должно учитывать все возможные ситуации, которые
могут возникнуть по ходу решения

7.

Алгоритмизация – процесс разработки алгоритма для
решения задачи
Примеры алгоритмов:
Рецепты из кулинарной книги;
Инструкции к прибору;
Правила дорожного движения;…

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

1.
2.
3.
4.
5.
6.
7.
Однозначность
Массовость
Детерминированность
Корректность
Конечность
Эффективность
Дискретность

9. Способы записи алгоритмов

Описательный
(словесно-формульный)
–
алгоритм
записывается на естественном, математическом языке
Графический – в виде блок-схем

10.

Блок-схема – графическое изображение алгоритма в
виде
геометрических фигур (блоков), соединенных линиями
Внутри блока записывается действие, которое нужно выполнить,
или условие, которое нужно проверить

11. Основные блоки (по ГОСТу):

12. Правила построения алгоритма решения задачи:

1.
2.
3.
4.
Выявить исходные данные, результаты, назначить им
имена
Выбрать метод (порядок) решения задачи
Разбить метод решения задачи на этапы (с учетом
возможностей ЭВМ)
Изобразить каждый этап в виде соответствующего блока
схемы алгоритма и указать стрелками порядок их
выполнения

13. В полученной схеме при любом варианте вычислений:

предусмотреть выдачу результатов или сообщений об их
отсутствии
обеспечить возможность после выполнения любой операции,
так или иначе, перейти к блоку «Конец»

14. Пример задачи

Даны длины катетов прямоугольного треугольника. Определить
периметр этого треугольника. Составить алгоритм решения задачи

15. Решение

1.
Выделяем исходные данные и результаты
Исходные данные: a, b – длины катетов
Результат: p – периметр
2.
3.
4.
Метод и этапы: вычислим гипотенузу с, пользуясь теоремой
Пифагора, а затем вычислим периметр
Используемые формулы:
Блок-схема:

16. Основные алгоритмические структуры:

Следование
Ветвление
Цикл

17. Программа

18.

Язык программирования – совокупность средств и правил
представления алгоритма в виде, пригодном для выполнения
вычислительной машиной
Язык
программирования – формализованный язык для
описания алгоритма решения задачи на компьютере

19.

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

20.

Алфавит
– фиксированный набор основных
допускаемых для составления текста программы
символов,
Синтаксис – правила написания конструкций языка из букв
алфавита
Семантика – правила
конструкций языка
однозначного толкования отдельных

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

22. 1. Постановка задачи

Выполняется специалистом в предметной области на естественном
языке
Определяется цель задачи, ее содержание и общий подход к
решению
Учитываются
ограничения,
программным обеспечением
накладываемые
аппаратным
и

23. 2. Анализ задачи и моделирование

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

24. 3.Разработка или выбор алгоритма решения задачи

Выбирается оптимальное решение
Неточности
в постановке, анализе задачи или разработке
алгоритма могут привести к скрытой ошибке – программист
получит неверный результат, считая его правильным

25. 4. Проектирование общей структуры программы

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

26. 5. Кодирование

Запись алгоритма на языке программирования

27. 6. Отладка и тестирование программы

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

28. Тестирование должно:

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

29.

Отладчики – специальные программы, которые позволяют
выполнять программу по отдельным шагам, просматривая при
этом значения переменных

30. 7. Анализ результатов

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

31. 8. Публикация результатов работы, передача заказчику для эксплуатации

32. 9. Сопровождение программы

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

33. Типы ошибок в программах

1.
Синтаксические (ошибки компиляции)
2.
3.
Ошибки выполнения
Семантические (ошибки в алгоритме)