Алгоритмы и структуры данных [2011 г.]

Reply to topic
 
Author
Message

admin ®

Longevity: 6 years 11 months

Posts: 25

Post 30-Jan-2012 17:25

[Quote]

Алгоритмы и структуры данных
Производитель: compscicenter.ru
Год выпуска: 2011-2012
Язык: русский
Автор: Куликов Александр Сергеевич, Дворкин Михаил Эдуардович
Продолжительность: 17:09:43 (1 часть), 29:41:29 (2 часть)
Формат видео: FLV
Видео: VP6F 1280x720 25.00fps 119kbps
Аудио: MPEG Audio Layer 3 44100Hz stereo 96kbps
Описание: Совместный проект Школы анализа данных Яндекса, CS клуба, Академии современного программирования и ФМЛ №239. Это курсы подготовительного года обучения. Занятия предыдущего семестра начались в 2011 году.

Часть 1

Лекции курса
13.09.2011, 18:30
Лекция 1 «Введение»
Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ. Время работы алгоритма, O-символика. Скорость роста функций: логарифм, полином, экспонента.
20.09.2011, 18:30
Лекция 2 «Рекуррентные соотношения»
Метод "разделяй и властвуй". Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск.
27.09.2011, 18:30
Лекция 3 «Алгоритмы сортировки»
Сортировка слиянием: с рекурсией и без. Сортировка с помощью кучи. Нижняя оценка (nlogn) для сортировки. Быстрая сортировка: анализ среднего времени работы, анализ глубины рекурсии, элиминация хвостовой рекурсии.
04.10.2011, 18:30
Лекция 4 «Алгоритмы сортировки»
Быстрая сортировка (продолжение). Порядковые статистики: нахождение за линейное в среднем время.
11.10.2011, 18:30
Лекция 5 «Элементарные структуры данных»
Абстрактные типы данных, интерфейс и реализация. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ учётных стоимостей операций: функция потенциала, истинные и учётные стоимости. Стек, очередь, дек. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков. Корневое дерево: бинарное дерево, дерево с произвольным ветвлением, представление "левый ребёнок — правый сосед".
18.10.2011, 18:30
Лекция 6 «Динамическое программирование»
Предварительные сведения: ациклические ориентированные графы. Общие принципы динамического программирования, часто используемые подзадачи. Кратчайшие пути в ациклических ориентированных графах. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности. Стоимость редактирования: граф на подзадачах, нахождение кратчайшего пути в данном графе.
25.10.2011, 18:30
Лекция 7 «Динамическое программирование»
Задача о рюкзаке: рюкзак с повторениями и без, ленивые вычисления. Перемножение последовательности матриц: представление порядка перемножения в виде дерева, оценка на количество порядков. Независимые множества в деревьях. О времени и памяти алгоритмов, основанных на методе динамического программирования.
01.11.2011, 18:30
Лекция 8 «Двоичные деревья поиска»
Дерево поиска: поиск, вставка, удаление, поиск следующего и предыдущего элемента за время, пропорциональное высоте. АВЛ-дерево (или какое-нибудь другое сбалансированное дерево): верхняя оценка на высоту, малое и большое вращение.
15.11.2011, 18:30
Лекция 9 «Декартовы деревья»
Декартовы деревья, операции split и merge, реализация стандартных операций деревьев поиска через split и merge.
22.11.2011, 18:30
Лекция 10 «Сплей-деревья»
Верхняя оценка O(logn) на среднюю стоимость операций.
29.11.2011, 18:30
Лекция 11 «Декомпозиция графов»
Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности.
06.12.2011, 18:30
Лекция 12 «Декомпозиция графов (продолжение)»
Поиск в глубину в ориентированных графах: ориентированные ациклические графы, топологическая сортировка вершин, наличие стока и истока в ациклическом графе, выделение компонент сильной связности.
13.12.2011, 18:30
Лекция 13 «Пути в графах»
Расстояния в графе. Поиск в ширину: обход, дерево кратчайших путей, сравнение с поиском в глубину. Алгоритм Дейкстры: адаптация поиска в ширину введением дополнительных вершин; установка будильников; алгоритм Дейкстры; альтернативный взгляд на алгоритм: последовательное расширение множества вершин, до которых расстояние уже посчитано; время работы алгоритма при различных реализациях очереди с приоритетами.

Часть 2

13.02.2012, 18:30
Лекция 1 «Пути в графах»
Кратчайшие пути при наличии рёбер отрицательного веса: алгоритм Беллмана-Форда; определение наличия цикла отрицательного веса в графе. Кратчайшие пути в ациклических ориентированных графах. Кратчайшие пути между всеми парами вершин: алгоритм Флойда-Уоршолла, алгоритм Джонсона.
13.02.2012, 18:30
Лекция 2 «Жадные алгоритмы»
Общие принципы жадного метода. Непрерывная и дискретная задачи о рюкзаке. Задача о выборе заявок. Минимальное покрывающее дерево: свойство разреза, жадная стратегия.
20.02.2012, 18:30
Лекция 3 «Потоки»
05.03.2012, 18:30
Лекция 4 «Задача линейного программирования и симплекс-метод»
12.03.2012, 18:30
Лекция 5 «Числовые алгоритмы»
Элементарная арифметика: сложение, умножение, деление. Арифметика сравнений: сложение, умножение, возведение в степень, алгоритм Евклида, расширенный алгоритм Евклида, деление. Проверка чисел на простоту.
19.03.2012, 18:30
Лекция 6 «RSA»
Генерация случайных простых чисел. Криптография: схемы с закрытым ключом, RSA.
26.03.2012, 18:30
Лекция 7 «Быстрое преобразование Фурье»
Быстрое вычисление значений многочлена в точках: два способа задания многочленов — коэффициентами и значениями в точках; вычисление значений многочлена в точках методом "разделяй и властвуй"; дискретное преобразование Фурье; быстрое преобразование Фурье. Интерполяция: интерполяция в терминах матриц; матрица Вандермонда; интерполяция как домножение на обратную матрицу.
02.04.2012, 18:30
Лекция 8 «Линейное программирование»
Линейное программирование: общий вид задачи, двойственность. Задача о максимальном потоке. Задача о паросочетании в двудольном графе.
09.04.2012, 18:30
Лекция 9
16.04.2012, 18:30
Лекция 10 «Алгоритм Кнута-Морриса-Пратта»
Введение: во многих задачах решение ищется среди экспоненциального большого множества кандидатов. Задача пропозициональной выполнимости: задача поиска; алгоритм, задающий задачу поиска. Задача о коммивояжере: оптимизационные задачи и задачи поиска; сравнение с задачей о нахождении покрывающего дерева. Задачи о независимом множестве, вершинном покрытии и клике, длиннейший путь. Задача о рюкзаке и сумме подмножества: задача об унарном рюкзаке; задача о сумме подмножества как более просто формулирующася задача.
04.05.2012, 18:30
Лекция 11 «Суффиксные деревья»
Построение суффиксного дерева за линейное время.
11.05.2012, 18:30
Лекция 12 «NP-полные задачи»
Задачи поиска, классы P и NP. Сведения. Доказательство NP-полноты задач выполнимости, 3-выполнимости, выполнимости схемы, задачи о независимом множестве.


Last edited by admin on 2012-10-27 19:44; edited 1 time in total
[Profile] [PM]

anabol1k

Longevity: 9 years 8 months

Posts: 766

Post 27-Oct-2012 17:41 (after 8 months 28 days)

[Quote]

Торрент обновлён! Добавлены 11 и 12 занятия во второй части.

_________________
http://2v3.su/ Создание сайтов
[Profile] [PM]
Display posts from previous:    
Reply to topic

The time now is: Today 05:14

All times are GMT



You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum