Конспект лекций по предмету "Проектирование алгоритмов" Лекция 1 введение в проектирование алгоритмов. Оценка алгоритмов по объему и времени. Схема горнера для вычисления значений многочленов

---

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

---

2 
решения. Вместе с тем мы должны помнить, что создателями этих 
алгоритмов и их программных модулей являются освещение процесса 
создания алгоритмов, исследование их по качеству и эффективности.
Учитывая вышесказанное, вернемся к поставленной задаче вычисления 
площади треугольника по известным длинам сторон. Можно воспользоваться 
известной формулой Герона 




S
p p
a
p
b
p
c




, где 


1
2
p
a
b
c

 
Предварительно, перед применением этой формулы, мы должны убедиться в 
существовании такого треугольника. Известно, что для существования 
треугольника с длинами сторон равными а, b, c, необходимо выполненные 
неравенств треугольника: сумма любых двух сторон больше третьей 
стороны которые выражаются в виде 
;
;
a
b
c a
c
b b
c
a
 
 
 
. Нарушение 
любого из этих трех неравенств свидетельствует о том, что такой 
треугольник не существует. Следовательно, для полноты алгоритма эти 
условия также должны быть учтены в алгоритме и искомый алгоритм может 
быть представлен в виде следующей блок-схемы: