Теория алгоритмов

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2010. – 16 слайдов. Содержание: Определения эйлерового пути, эйлерового цикла и эйлерова графа. Алгоритм нахождения эйлерова цикла. Алгоритм Прима. Приближенный алгоритм-1 для метрической «TSP». Алгоритм Кристофидеса для метрической «TSP».

Воробьев С. - 2011. – 20 слайдов. Содержание: Введение. Решаемые проблемы. Задача кластеризации. Мера модулярности. Алгоритмы кластеризации. k-clique percolation. Алгоритм Керниган-Лин. Betweenness centrality. Алгоритм Гирван-Ньюмана. Особенность разбиения жадным алгоритмом. Спектральный метод Ньюмана (spectral partitioning). Алгоритм распространения меток.

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2011. – 13 слайдов. В материале рассматриваются полиномиальные и матричные тождества. Содержание: Алгоритм Фрейвалда. Корректность алгоритма. Доказательство. Полиномиальные тождества. Лемма Шварца-Зиппеля и ее доказательство. Упражнение.

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2011. – 9 слайдов. Содержание: Теорема об ускорении. Классы временной сложности. Теорема об иерархии. Классы пространственной сложности. «Карта памяти» лекции.

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2010. – 15 слайдов. Содержание: Приближенный алгоритм с гарантированной точностью. Покрытие множества. Жадный алгоритм в задаче о покрытии. Покрытие на каждом шаге. Точность жадного алгоритма: верхняя оценка. Как обмануть жадный алгоритм? Нижняя...

60 слайдов. (Автор не указан). Содержание: LRU – «least recently used». CLOCK. LFU – «least frequently used». LRD – «least reference density». GCLOCK – «generalized CLOCK». Improved GCLOCK. CAR – «CLOCK with Adaptive Replacement». ARC – «Adaptive Replacement Cache». CART – «CAR with Temporal filtering». MQ – «Multiple Queue». LIRS – «Low Inter-reference Recency...

Агаев Н. - М.: Факультет Вычислительной математики и кибернетики МГУ, 2011. – 31 слайд. Содержание: Понятие кластеризации Меры близости. Классификация алгоритмов. Неиерархические алгоритмы кластеризации. Иерархические алгоритмы кластеризации.

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2011. – 28 слайдов. Содержание: История алгоритмов. Теория сложности. Обозначения. Тривиальное и разумное вычисления. Дискретный логарифм. Наибольший общий делитель. Алгоритм Евклида. Задача коммивояжера. Переборный алгоритм для TSP....

Борисенко О. - 2010. – 43 слайда. Для хранения и обработки больших объёмов данных требуется много памяти. Таким образом, разумно использовать внешнюю память для хранения информации. Для этого необходимы специальные структуры, которые были бы ориентированы на работу с использованием жесткого диска. В презентации производится подробный обзор используемых структур. Основные...

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН; Факультет Вычислительной математики и кибернетики МГУ, 2010. – 16 слайдов. Параллельный вероятностный алгоритм Луби – алгоритм нахождения максимального по включению независимого множества в графе. Для реализации данного алгоритма требуется полилогарифмическое время «в среднем».

Кузюрин Н.Н., Фомин С.А. - М.: Институт системного программирования РАН, 2010. – 26 слайдов. Содержание: RAM — random access machine. RAM: набор команд. RAM: моделирование FOR через GOTO. RAM: меры сложности алгоритмов. Машина Тьюринга. Симулятор Машины Тьюринга. Машина Тьюринга: Удвоение строки. Машина Тьюринга: Унарное сложение. Машина Тьюринга: Распознавание четных...