1

1. Постановка задачи формулировка условия задачи; определение конечных целей решения задачи; определение формы выдачи результатов; описание данных (их типов, диапазонов величин, структуры и т. п.). 1. Постановка задачи формулировка условия задачи; определение конечных целей решения задачи; определение формы выдачи результатов; описание данных (их типов, диапазонов величин, структуры и т. п.). 2 Постановка задачи Неформализованное описание предметной области и целей Формализованное описание задачи: 1. Дано … 2. Найти …

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

3. Разработка алгоритма выбор метода проектирования алгоритма; выбор формы записи алгоритма (блок-схемы, псевдокод и др.); выбор тестов и метода тестирования; проектирование алгоритма. 4 Разработка алгоритма Модель решения задачи Алгоритм решения задачи

4. Программирование выбор языка программирования; уточнение способов организации данных; запись алгоритма на выбранном языке программирования. 5 Программирование Алгоритм решения задачи Текст программы на языке программирования

5. Отладка и тестирование программы синтаксическая отладка; отладка семантики и логической структуры; тестовые расчеты и анализ результатов тестирования; совершенствование программы. 6 Отладка и тестирование программы Текст программы на языке программирования Работающая программа в машинных кодах

6. Анализ результатов решения задачи по результатам расчетов. Уточнение в случае необходимости математической модели с повторным выполнением этапов 2 – 5. 7

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

Слово алгоритм происходит от algorithmi - латинской формы написания имени арабского математика IX в. Аль-Хорезми, который сформулировал правила выполнения четырех арифметических действия над многозначными числами. Алгоpитм – заранее заданное понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов. 9

Исполнитель алгоритма – это объект, умеющий выполнять определенный набор действий. Исполнителем может быть человек, робот, животное. Множество команд, которые может выполнять исполнитель – это система команд исполнителя (СКИ). 10

11 Компьютер – основной исполнитель алгоритмов в информатике. Процесс выполнения алгоритма сложения двух чисел компьютером:

1. Дискретность – выполнение алгоритма разбивается на последовательность законченных действий-шагов (команд). Только выполнив одно действие, можно приступать к исполнению следующего. 2. Понятность – алгоритм не должен содержать предписаний, смысл которых может восприниматься исполнителем неоднозначно. Алгоритм составляется из команд, входящих в СКИ. Алгоритм всегда рассчитан на выполнение не размышляющего исполнителя. 12

3. Детерминированность (определенность и однозначность) – каждая команда алгоритма определяет однозначное действие исполнителя, и должно быть однозначно определено, какая команда выполняется следующей. То есть если алгоритм многократно применяется к одному и тому же набору исходных данных, то на выходе он получает каждый раз один и тот же результат. 13

4. Результативность – исполнение алгоритма должно закончиться за конечное число шагов, и при этом должен быть получен результат решения задачи. Одним из возможных результатов может быть установление того факта, что задача решений не имеет. Свойство результативности содержит в себе свойство конечности завершение работы алгоритма за конечное число шагов. 5. Массовость – алгоритм пригоден для решения любой задачи из некоторого класса задач, т.е. алгоритм правильно работает на некотором множестве исходных данных, которое называется областью применимости алгоритма. 14

15 Используются следующие способы записи алгоритма: - на естественном (разговорном) языке; - на условном алгоритмическом языке (псевдокод); - на языке программирования; - геометрический в виде блок-схемы.

Словесный способ записи алгоритма ориентирован на исполнителя-человека. ПРИМЕР. Алгоритм перевоза через реку Волка, Козы и Капусты, при условии, что в лодке можно перевозить только один из указанных объектов, а на берегу вместе не могут находиться Коза и Волк, Коза и Капуста: 1) перевезти Козу; 2) вернуться на исходный берег; 3) перевезти Волка; 4) вернуться на исходный берег с Козой; 5) перевезти Капусту; 6) вернуться на исходный берег; 7) перевезти Козу. 16

17 Алгоритмический язык Паскаль н.ц. для n от 1 до 5 н.ц. для k от 1 до 5 B[n,k]:=n+k к.ц. For n:=1 To 5 Do For k:=1 To 5 Do B[n,k]:=n+k;

Блок-схема алгоритма это графическое описание алгоритма как последовательности функциональных блоков, каждый из которых подразумевает выполнение определенного действия алгоритма. 18

19

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

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

Определение суммы двух чисел A и B, значения которых вводятся с клавиатуры. 22

23 Обеспечивает в зависимости от результата проверки некоторого условия выбор одного из альтернативных путей работы алгоритма. Структура «ветвление» существует в двух основных вариантах: «неполная развилка» и «полная развилка»

Вычисление значения x для произвольных a и b, значения которых вводятся с клавиатуры. 24

25 Цикл с параметром (цикл со счетчиком) предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла), изменяющейся в заданном диапазоне. При каждом значении параметра цикла выполняются действия, входящие в тело цикла. Для применения цикла с параметром необходимо, чтобы количество повторений цикла было известно заранее.

26 Блок-схема алгоритма нахождения суммы N первых натуральных чисел. Параметр цикла (счетчик) – переменная I, значение которой изменяется от 1 до N с шагом 1. При каждом прохождении цикла к значению переменной S прибавляется значение переменной I.

27 Алгоритмические структуры «цикл с предусловием» и «цикл с постусловием» можно использовать для организации итерационного цикла, для которого число повторений тела цикла заранее определить нельзя. Выход из итерационного цикла осуществляется при выполнении некоторого условия.

28 Тело цикла выполняется до тех пор, пока условие истинно. Если при первой проверке условие оказалось ложным, тело цикла не выполняется ни разу.

29 Тело цикла выполняется до тех пор, пока условие ложно. Если при первой проверке условие оказалось истинным, тело цикла выполнится один раз.

30 В зависимости от используемых в алгоритме базовых алгоритмических структур, различают три основных типа алгоритмов: линейные, разветвленные, циклические. Если алгоритм не содержит базовых структур ветвления и цикла, он считается линейным. Если в алгоритме присутствует хотя бы одна структура ветвления, но нет ни одного цикла, алгоритм называется разветвленным. Если алгоритм содержит хотя бы одну циклическую структуру, он называется циклическим. Разные алгоритмические структуры могут встраиваться друг в друга.

31 Составить алгоритм вычисления значения функции y для произвольных a, b, x, значения которых вводятся с клавиатуры.

32 Составить программу вычисления значения функции y для произвольного x:

33

Найти сумму 10 произвольных целых чисел, значения которых вводятся с клавиатуры. 34 Начало Конец n := 10; k := 1; s :=0 k