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

Рисунок.1.1
 

 
 


нет 
 

да 

 
Ввод a,b,c 
a+b>c ʌ a+c>b ʌ b+c>a 
6 
p=(a+b+c)/2 




S
p p
a
p
b
p
c




Вывод S 
7 
2
Конец 
Вывод “Такого 
треугольника” 

---

3 
Схема и структура блок схема известно читателям по курсам информатики. 
Мы и в дальнейшем часто будем пользоваться именно такой формой 
представления алгоритмов. Так как при таком подходе легко логически 
представить идею и сущность алгоритмов. А также из такой формы будет 
легко перейти к одному из алгоритмических языков, то есть к программе 
алгоритма. 

В качестве самостоятельной работы составить блок-схему решения 
квадратного уравнения с учетом возможных значений дискриминанта

и
 
в 
соответствии с этим, оформить выдачу ответа. 
Создание вычислительных машин было необходимым шагом 
технического прогресса в связи с появлением широкого класса задач 
требующих большой объем вычислений. Создание вычислительных машин в 
свою очередь выдвинула проблему составления определенных инструкций 
для управления работой вычислительных машин. Таким образом, появилась 
необходимость проектирования алгоритмов для ВМ (вычислительных 
машин) и составления программ в соответствии с этими алгоритмами. 
Несмотря на большое быстродействие современных компьютеров 
существуют и появляются все новые задачи, требующие такого объема 
вычисления, что не под силу даже современным ВМ. В ходе изложения мы 
ещё не раз обратим внимание на класс таких задач.
Мы здесь приведем одну хорошо известную среди специалистов 
задачу, связанную с шахматами: определить маршрут проходящий по 
правилу хода конём от клетки А1 и приходя по всем клеткам шахматной 
доски только по одному разу и возвращающуюся в исходную клетку А1. 
Если изложить данную задачу в терминах теории графов, то получим 
Гамильтонов граф, вершины которого расположены на клетках шахматной 
доски, а ребра графа - это линии соединяющие те клетки, по которым 
движется шахматная фигура при совершении хода конем. При этом число 
возможных 
вариантов 
маршрутов 
исчисляется 
по 
формуле 
4
8
20
16
16
21
2 3 4
6
8
28 10 .
N

 




Как видно, даже в этой на вид простой 
задаче мы сталкиваемся с таким огромным количеством вариантов. Если в 
таком графе каждое ребро имеет определенную цену перехода и нам 
необходимо из всех возможных маршрутов выбрать наименьший по цене 
маршрут, 
то 
такая 
задача 
не 
под 
силу 
даже 
современным 
быстродействующим ВМ. Вместе с тем для сравнения мы должны хранить 
информацию о каждом маршруте, для чего потребуется такой объем памяти, 
для которого не хватит объема памяти ВМ. Поэтому при проектировании 

---

4 
алгоритмов мы должны оценивать их как по объему вычислений, так и по 
объему памяти для реализации построенного алгоритма. В дальнейшем мы 
будем оценивать каждый предложенный алгоритм именно по этим 
показателям.
Для иллюстрации изложенного подхода рассмотрим процесс 
вычисления 
значения 
многочлена 
в 
некоторой 
точке 
0
.
х
х

: 
 
1
0
1
1
...
n
n
n
n
n
P x
a x
a x
a
x
a




 

. 
Определим 
число 
арифметических 
операций для вычисления значения многочлена в точке 
0
.
х
х

Первый 
подход - вычисление в лоб, т.е. последовательное вычисление 
арифметических операций. Число умножений для каждого слагаемого 
соответственно

 



1
1
2
... 1
.
2
n n
n
n
n


 

  
Число сложений 
.
n
Всего 


1
2
n
n
n
 

операций.
Второй подход - вычисление по схеме Горнера, когда многочлен 
представляется в виде 
 






0 0
1
0
2
0
1
0
...
...
.
n
n
n
P x
a x
a
x
a
x
a
x
a









При 
этом число необходимых операций будет 
n
умножений и 
n
сложений. 
Эффективность второго подхода очевидна.
Прежде чем переходить к проектированию алгоритма решения 
определенной задачи мы должны, предварительно, убедится в корректности 
постановки задачи. Это означает, во-первых, существование решения задачи, 
во-вторых, если нет особых оговорок, единственность решения. Для этого 
необходимо наличие всех условий обеспечивающих существование и 
единственность решения. Для иллюстрации рассмотрим следующую задачу:
На сумму 133 000 сумов необходимо купить 10 тетрадей по цене 5 000, 
11 000 и 18 000 сумов. Определите количество каждого вида тетрадей.