Теория алгоритмов. Зюзысов В.М. - 62 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Найти остовное дерево минимальной длины. Эта задача решается с помощью жадного
алгоритма сложности Ο(n log n)[22, стр.357–358].
Кратчайший путь на графе, состоящем из n вершин и m ребер. Сложность алгоритма
Ο(m n) [22, стр.377–382].
•
•
•
•
•
•
•
•
•
•
•
•
•
Связные компоненты графа. Определяются подмножества вершин в графе (связные
компоненты), такие, что две вершины,
принадлежащие одной и той же компоненте,
всегда связаны цепочкой дуг. Если n – количество вершин, а m – количество ребер, то
сложность алгоритма Ο(n+m) [22, стр.364–365].
Быстрое преобразование Фурье [8, стр. 284–302], требующее Ο(n log n)
арифметических операций, – один из наиболее часто используемых алгоритмов в
научных вычислениях.
Умножение целых чисел. Алгоритм Шёнхаге-Штрассена [8, стр. 304–308]. Сложность
алгоритма порядка Ο(n log n log log n). Отметим, что школьный метод для умножения
двух n-разрядных чисел имеет сложность порядка Ο(n
2
).
Умножение матриц. Алгоритм Штрассена [8, стр. 259–261] имеет сложность порядка
Ο(n
log 7
), для умножения двух матриц размера n×n. Очевидный алгоритм имеет порядок
сложности Ο(n
3
).
Класс E: задачи, экспоненциальные по природе
К экспоненциальным задачам относятся задачи, в которых требуется построить
множество всех подмножеств данного множества, все полные подграфы некоторого графа
или же все поддеревья некоторого графа.
Существует масса примеров задач с экспоненциальной сложностью. Например,
чтобы вычислить
для заданного натурального k, нам только для записи конечного
ответа потребуется около 2
)2(
2
k
n
шагов (где n – число цифр в двоичной записи k), не говоря
даже о самом вычислении.
Задачи не попадающие ни в класс P, ни в класс E
На практике существуют задачи, которые заранее не могут быть отнесены ни к
одному из рассмотренных выше классов. Хотя в их условиях не содержатся
экспоненциальные вычисления, однако
для многих из них до сих пор не разработан
эффективный (т.е. полиномиальный) алгоритм.
К этому классу относятся следующие задачи [14, с. 207]:
задача о выполнимости: существует ли для данной булевской формулы, находящейся в
КНФ, такое распределение истинностных значений, что она имеет значение истина?
задача коммивояжера (Коммивояжер хочет объехать все
города, побывав в каждом
ровно по одному разу, и вернуться в город, из которого начато путешествие. Известно,
что переезд из города i в город j стоит c(i, j) рублей. Требуется найти путь
минимальной стоимости.);
решение систем уравнений с целыми переменными;
составление расписаний, учитывающих определенные условия;
размещение обслуживающих
центров (телефон, телевидение, срочные службы) для
максимального числа клиентов при минимальном числе центров;
оптимальная загрузка емкости (рюкзак, поезд, корабль, самолёт) при наименьшей
стоимости;
оптимальный раскрой (бумага, картон, стальной прокат, отливки), оптимизация
маршрутов в воздушном пространстве, инвестиций, станочного парка;
задача распознавания простого числа; самый лучший в настоящее время
тест на
простоту имеет сложность порядка Ο(L(n)
L(L(L(n)))
), где L(n) – количество цифр в числе n

Страницы