Современные Компьютерные Технологии
Осень 2010
Тематический план курсa
- Oбзор современных алгоритмов и структур данных.
- Основы теории графов и линейнoй алгебры.
- Итеративные методы решения линейных уравнений.
- Ранжирование на графе: PageRank, Hits.
- Обработка текстовой информации.
- Архитектура и алгоритмы поисковых систем.
Модуль 1
Лекции. Линейная Алгебра и Теория Графов
- [8.09.2010] Введение. Основы алгоритмов и структур данных
Основы линейной алгебры и теории графов, матрицы смежности,
собственные значения и вектора. Oчереди, стеки, связанные списки, бинарные деревья,
поиск в ширину, поиск в глубину, понятие сложности алгоритма
- [15.09.2010] Итерационные методы I
Итерационные методы решений систем линейных уравнений. Стационарные методы. Методы Jacobi, Gauss-Seidel, SOR. Сходимость методов.
- [20.10.2009] Итерационные методы II
Нестационарые методы решения линейных систем. Метод наискорейшего спуска (Steepest Descent) и
сопряженных градиентов (Conjugate Gradients).
- [22.10.2010] Итерационные методы III
Нахождение собственных значений и векторов матрицы с помощью степенных итерации (Power iterations). Скоросоть сходимости метода
- [28.10.2010] Зачет
Домашние задания
- [08.09.2010] Имплементировать классы stack и queue с основными операциями (push, pop, top, isEmpty, isFull)
- [15.09.2010] Имплементировать Jacobi и Gauss-Seidel алгоритмы решения систем линейных уравнений. Изучить и сравнить скорость сходимости на раличных тестовых натрицах
- gallery('poisson'), sprandsym. рассматривать систему из 100
уравнений
- [20.10.2010]
Имплементировать методы Steepest Descent (наискорейший спуск) и Conjugate Gradient (Сопряженные градиенты) для решения систем линейных уравнений.
Сравнить сходимость со сходимостью стационарных методов. Рассматривать матрицу размером 100
- [22.10.2010] Имплементировать Power Iterations. Вычислить 2 (первый и второй) наибольших собственных вектора и собственных значемий.Изучить сходимость метода. Рассматривать матрицу размером 100
Модуль 2
Лекции
- [10.11.2010] Поисковые системы и алготирм Pagerank
Архитектура и методы работы поисковых систем. Методы ранжирования узлов
графа. Алгоритм PageRank. Сравнение порядка ранжирования. Kendall's
tau. Spearman's coefficient
- [17.11.2010] Случайные блуждание на графе.
Случайные блуждания на графе. Марковский процесс и стохастические
матрицы.Стационарное состояние. Фундаментальная теорема Марковских цепей.
Теорема Перрона-Фрабениуса
- [24.11.2010] Web и Поисковых Системы
Стрктура Web. Сильно связанные компоненты. Распределение степеней
узлов. Диаметр графа. Понятия Hubs и Authorities. HITS алгоритм
Архитектура поисковых систем.
- [01.12.2010] Полнотекстовой поиск
Алгебраическая модель представления текстовых документов. Векторная модель. Матрица
терм-частота. Индексирование. Инвертированный индекс. Схожесть документов. TF-IDF
- [08.12.2010] Качество поиска
Tочность и полнота. Precision at r. Метрики MAP и nDCG.
- [15.12.2010] Машинное обучение ранжированию
Обучение с "учителем", постановка задачи, поточечные методы, регрессия.
- [22.12.2010] Зачет. Сдача ДЗ.
- [27.12.2010] Экзамен
Домашние задания
- [10.11.2010]
а) Имплентировать алгоритм PageRank. Исследовать его сходимость для
разных значений константы c, построить графики сходимости.
b) Рассчитать ранг узлов по in_degree и сравнить с рангом от PageRank (для разных значений c). Для экспериментов использовать данные:
web1 и web2.
- [17.11.2010]
а) Вычислить Pagerank решением линейной системы. Сравнить скорость
сходимости линейной системы со скоростью сходимости степенных интераций. Для экспериментов использовать данные:
web1 и web2.
b) Сравнить порядок ранжирования узлов по in_degree и pagerank для
обоих графов с помощью Spearman's coefficient и Kendal's tau.
- [24.11.2010]
а) Имплементировать алгоритм HITS. Вычислить значения hubs и
authorities для
web1. Сравнить ранжирование по in-degree,out-degree, hubs,
authorities, pagerank.
b) Построить распределения степеней узлов (in_degree, out_degree) для
графа web3.
и частоты слов в
тексте
Alice in Wonderland (частотная таблица здесь ).
Найти показатель alpha в степенном законе для всех распределений
- [01.12.2010]
Имплементировать индексатор. Построить матрицу терм-документ для
коллекции текстов (перевести все слова в
нижний регистр)
Вычислить кореляционную матрицу текстов.
- [08.12.2009]
Использовать в индексторе TF-IDF меру. Исключить из индекса стоп слова
stop words
- [15.12.2009]
Имплементировать ранжированный текстовой поиск на основе созданного
индекса.
Литература к курсу
Matlab
-
Matlab primer
-
MATLAB 7. Программирование, численные методы а>
-
Matlab в инженерных и научных расчетах
-
Численные методы. Использование Matlab
-
Introduction ro Object-Orineted Programming in MATLAB
-
Inside MATLAB Objects
Учебники:
-
Introduction to Algorithms. Thomas Cormen, Charles Leiserson, Ronlad Rivest, Clifford Stein. MIT Press, 2003.
Алгоритмы. Построение и Анализ. Томас Кормен, Чарльз Лейзерсон, Рональд Ривер, Клиффорд Штейн
-
Matrix Computations. Gene H. Golub , Charles F. Van Loan, The Johns Hopkins University Press, 1996.
Матричные вычисления. Джине Голуб и Чарльз Ван Лоун
- Структуры и алгоритмы обработки данных, C++ . А.А. Кубенский
-
Templates for the Solution of Linear Systems:
Building Blocks for Iterative Methods, R. Barrett, M. Berry, T.F. Chan, et. al.
-
Understanding Search Engines Soumen. Michael Berry, Murray Browne, SIAM, 2005.
-
Mining the Web. Soumen Chakrabarti, Morgan Kaufmann, 2002.
-
An Introduction to Information Retrieval. Christopher D. Manning, Prabhakar Raghavan, Hinrich Schutze,
Cambridge University Press, 2008
Обзоры и научные статьи: