Алгоритмы и алгоритмизация

1. Алгоритмы и алгоритмизация

АЛГОРИТМЫ И
АЛГОРИТМИЗАЦИЯ
Существует множество различных определений алгоритма:
Алгоритм – это точный набор инструкций, описывающих последовательность действий
некоторого исполнителя для достижения результата, решения некоторой задачи.
Алгоритм – это всякая система вычислений, выполняемых по строго определённым
правилам, которая после какого-либо числа шагов заведомо приводит к решению
поставленной задачи. (А. Колмогоров)
Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от
варьируемых исходных данных к искомому результату. (А. Марков)
Алгоритм – строго детерминированная последовательность действий, описывающая
процесс преобразования объекта из начального состояния в конечное, записанная с
помощью понятных исполнителю команд. (Угринович Николай Дмитриевич)
Алгоритм – однозначно, доступно и кратко описанная последовательность процедур для
воспроизводства процесса с обусловленным задачей алгоритма результатом при заданных
начальных условиях.

2. Например, «кипячение чайника»:

Открыть крышку чайника
Наполнить чайник водой
Закрыть крышку чайника
Поставить чайник на плиту
Включить плиту
Дождаться закипания чайника
Выключить плиту
Мы все с этим отлично справляемся. А вот ребенку необходимо это
объяснять.

3. Например, «кипячение чайника»:

Открыть крышку чайника
Наполнить чайник водой
Закрыть крышку чайника
Поставить чайник на плиту
Включить плиту
Дождаться закипания чайника
Выключить плиту
Мы все с этим отлично справляемся. А вот ребенку необходимо это
объяснять.

4. Например, «кипячение чайника»:

Открыть крышку чайника
Наполнить чайник водой
Закрыть крышку чайника
Поставить чайник на плиту
Включить плиту
Дождаться закипания чайника
Выключить плиту
Мы все с этим отлично справляемся. А вот ребенку необходимо это
объяснять.

5. Например, «кипячение чайника»:

Открыть крышку чайника
Наполнить чайник водой
Закрыть крышку чайника
Поставить чайник на плиту
Включить плиту
Дождаться закипания чайника
Выключить плиту
Мы все с этим отлично справляемся. А вот ребенку необходимо это
объяснять.

6. Например, «кипячение чайника»:

Открыть крышку чайника
Наполнить чайник водой
Закрыть крышку чайника
Поставить чайник на плиту
Включить плиту
Дождаться закипания чайника
Выключить плиту
Мы все с этим отлично справляемся. А вот ребенку необходимо это
объяснять.

7. Например, «кипячение чайника»:

Открыть крышку чайника
Наполнить чайник водой
Закрыть крышку чайника
Поставить чайник на плиту
Включить плиту
Дождаться закипания чайника
Выключить плиту
Мы все с этим отлично справляемся. А вот ребенку необходимо это
объяснять.

8. Например, «кипячение чайника»:

Открыть крышку чайника
Наполнить чайник водой
Закрыть крышку чайника
Поставить чайник на плиту
Включить плиту
Дождаться закипания чайника
Выключить плиту

9. Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:

Дискретность. Это свойство состоит в том, что алгоритм должен
представлять процесс решения задачи как последовательное выполнение
простых шагов. При этом для выполнения каждого шага алгоритма требуется
конечный отрезок времени, т.е. преобразование исходных данных в результат
осуществляется во времени дискретно. В приведенном выше алгоритме
видна необходимость строгого соблюдения последовательности выполнения
действий (например, если шаг 2 поставить после шага 6, то будет достигнут не
совсем ожидаемый результат).
Детерминированность — определённость. В каждый момент времени
следующий шаг работы однозначно определяется состоянием системы. Таким
образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же
исходных данных. С другой стороны, существуют вероятностные алгоритмы, в
которых следующий шаг работы зависит от текущего состояния системы и
генерируемого случайного числа.
Понятность — алгоритм для исполнителя должен включать только те
команды, которые ему (исполнителю) доступны, которые входят в его систему
команд.

10.

Завершаемость (конечность, результативность) — при корректно заданных
исходных данных алгоритм должен завершать работу и выдавать результат за
конечное число шагов. С другой стороны, вероятностный алгоритм может и
никогда не выдать результат, но вероятность этого равна 0.
Массовость. Алгоритм решения задачи разрабатывается в общем виде, т.е.
он должен быть применим для некоторого класса задач, различающихся
лишь исходными данными.
Правильность (результативность). Алгоритм правильный, если его
выполнение дает правильные результаты решения поставленной задачи.

11. Основные типы алгоритмов

Существует 4 вида алгоритмов:
• линейный,
• циклический,
• разветвляющийся,
• вспомогательный.

12.

Линейный (последовательный) алгоритм — описание действий,
которые выполняются однократно в заданном порядке.
Линейными являются алгоритмы отпирания дверей, заваривания чая,
приготовления одного бутерброда. Линейный алгоритм применяется при
вычислении арифметического выражения.
Циклический алгоритм — описание действий, которые должны
повторяться указанное число раз или пока не выполнено заданное
условие. Перечень повторяющихся действий называется телом цикла.
Многие процессы в окружающем мире основаны на многократном
повторении одной и той же последовательности действий. Каждый год
наступают весна, лето, осень и зима. Жизнь растений в течение года
проходит одни и те же циклы. Подсчитывая число полных поворотов
минутной или часовой стрелки, человек измеряет время.

13.

Пример – «сложение 20 чисел»:
• сумма = первое число
• повторить 19 раз
– взять следующее число
– увеличить сумму на это число
конец цикла
Другой алгоритм – поедание каши
Пока каша не кончилась или не наелся повторяй
–
–
–
–
–
–
–
Зачерпнуть кашу ложкой
Открыть рот
Засунуть ложку с кашей в рот
Прикрыть рот
Вытянуть ложку
Прожевать кашу
Проглотить кашу
конец цикла
Условие – это выражение, находящееся между словом «если» и словом «то» и
принимающее значение «истина» или «ложь».

14.

Разветвляющийся алгоритм — алгоритм, в котором в зависимости от
условия выполняется либо одна, либо другая последовательность
действий.
Пример – нахождение наибольшего из 2 чисел.
Пример – решение квадратного уравнения:
• Найти дискриминант
• Если дискриминант меньше нуля
– то корней нет
– иначе: если дискриминант равен нулю
• то корень кратности 2 равен …
• иначе первый корень равен…, второй корень равен …
В общем случае схема разветвляющего алгоритма будет выглядеть так:
«если условие, то..., иначе...». Такое представление алгоритма получило
название полной формы.
Неполная форма, в которой действия пропускаются: «если условие, то...».

15.

Вспомогательный алгоритм — алгоритм, который можно использовать в
других алгоритмах, указав только его имя.
Вспомогательный алгоритм - это алгоритм решения некоторой подзадачи из
исходной (основной) задачи.
В языках программирования вспомогательные алгоритмы называют
подпрограммами или процедурами.
Каждая процедура должна иметь свое уникальное имя.

16. Блок-схема алгоритма

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

17.

18. Основные конструкции алгоритмов

• Условие
• Внутри ромба пишется условие. Например, «Х=2?».
• Выходы из ромба помечаются «да» и «нет»

19.

20. Циклы

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

21. Циклы

Виды циклов
Безусловные циклы
Цикл с предусловием
Цикл с постусловием
Цикл с выходом из середины
Цикл cо счётчиком
Вложенные циклы

22. Безусловные циклы

Иногда в программах используются циклы, выход из которых не предусмотрен
логикой программы. Такие циклы называются безусловными, или бесконечными.
Специальных синтаксических средств для создания бесконечных циклов, ввиду
их нетипичности, языки программирования не предусматривают, поэтому такие
циклы создаются с помощью конструкций, предназначенных для создания
обычных (или условных) циклов. Для обеспечения бесконечного повторения
проверка условия в таком цикле либо отсутствует (если позволяет синтаксис, как,
например, в цикле LOOP…END LOOP языка Ада), либо заменяется константным
значением (while true do … в Паскале).

23. Цикл с предусловием

Цикл с предусловием — цикл, который
выполняется, пока истинно некоторое условие,
указанное перед его началом. Это условие
проверяется до выполнения тела цикла, поэтому
тело может быть не выполнено ни разу (если
условие с самого начала ложно). В большинстве
процедурных языков программирования
реализуется оператором while, отсюда его
второе название — while-цикл.

24. Цикл с постусловием

Цикл с постусловием — цикл, в котором условие проверяется
после выполнения тела цикла. Отсюда следует, что тело
всегда выполняется хотя бы один раз. В языке Паскаль этот
цикл реализует оператор repeat..until; в Си — do…while.
В трактовке условия цикла с постусловием в разных языках
есть различия. В Паскале и языках, произошедших от него,
условие такого цикла трактуется как условие выхода (цикл
завершается, когда условие истинно, в русской терминологии
такие циклы называют ещё «цикл до»), а в Си и его потомках
— как условие продолжения (цикл завершается, когда
условие ложно, такие циклы иногда называют «цикл
пока»).....

25. Цикл с выходом из середины

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

26. Цикл с выходом из середины

Легко видеть, что с помощью цикла с выходом из середины можно
легко смоделировать и цикл с предусловием (разместив команду
выхода в начале тела цикла), и цикл с постусловием (разместив
команду выхода в конце тела цикла).
Часть языков программирования содержат специальные конструкции
для организации цикла с выходом из середины.
В тех языках, где подобных конструкций не предусмотрено, цикл с
выходом из середины может быть смоделирован с помощью любого
условного цикла и оператора досрочного выхода из цикла (такого, как
break в Си), либо оператора безусловного перехода goto.

27. Цикл cо счётчиком

Цикл со счётчиком — цикл, в котором некоторая переменная изменяет своё
значение от заданного начального значения до конечного значения с некоторым
шагом, и для каждого значения этой переменной тело цикла выполняется один
раз. В большинстве процедурных языков программирования реализуется
оператором for, в котором указывается счётчик (так называемая «переменная
цикла»), требуемое количество проходов (или граничное значение счётчика) и,
возможно, шаг, с которым изменяется счётчик. Например, в языке Оберон-2
такой цикл имеет вид:
FOR v := b TO e BY s DO
... тело цикла
END
(здесь v — счётчик, b — начальное значение счётчика, e — граничное
значение счётчика, s — шаг).

28. Вложенные циклы

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

29. Языки программирования. Технологии программирования

ЯЗЫКИ ПРОГРАММИРОВАНИЯ.
ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ
Язык программирования – формальная знаковая система, предназначенная для описания
алгоритмов в форме, которая удобна для исполнителя (например, компьютера).
Язык программирования позволяет программисту точно определить то, на какие события
будет реагировать компьютер, как будут храниться и передаваться данные, а также какие
именно действия следует выполнять над этими данными при различных обстоятельствах.
Язык программирования определяет набор лексических, синтаксических и семантических
правил, используемых при составлении компьютерной программы.
Лексика – изучает значения слов.
Синтаксис – описывает структуру программ как наборов символов (безотносительно к
содержанию). Синтаксису языка противопоставляется его семантика. Синтаксис языка
описывает «чистый» язык, в то же время семантика приписывает значения (действия)
различным синтаксическим конструкциям.

30. Языки программирования высокого и низкого уровня

Язык программирования низкого уровня – язык программирования, близкий к
программированию непосредственно в машинных кодах. Как правило, использует
особенности конкретного семейства процессоров. Общеизвестный пример
низкоуровневого языка – язык ассемблера.
Язык программирования высокого уровня – язык программирования, разработанный
для быстроты и удобства использования программистом.

31. Языки программирования высокого и низкого уровня

Язык программирования низкого уровня – язык программирования, близкий к
программированию непосредственно в машинных кодах. Как правило, использует
особенности конкретного семейства процессоров. Общеизвестный пример
низкоуровневого языка – язык ассемблера.
Язык программирования высокого уровня – язык программирования, разработанный
для быстроты и удобства использования программистом.
Наиболее распространёнными языками подобного типа являются C++, Visual Basic, Java,
Perl, Delphi (Pascal) и др.