Современные Компьютерные Технологии

Осень 2010

Тематический план курсa

  1. Oбзор современных алгоритмов и структур данных.
  2. Основы теории графов и линейнoй алгебры.
  3. Итеративные методы решения линейных уравнений.
  4. Ранжирование на графе: PageRank, Hits.
  5. Обработка текстовой информации.
  6. Архитектура и алгоритмы поисковых систем.

Модуль 1

Лекции. Линейная Алгебра и Теория Графов

  1. [8.09.2010] Введение. Основы алгоритмов и структур данных
    Основы линейной алгебры и теории графов, матрицы смежности, собственные значения и вектора. Oчереди, стеки, связанные списки, бинарные деревья, поиск в ширину, поиск в глубину, понятие сложности алгоритма
  2. [15.09.2010] Итерационные методы I
    Итерационные методы решений систем линейных уравнений. Стационарные методы. Методы Jacobi, Gauss-Seidel, SOR. Сходимость методов.
  3. [20.10.2009] Итерационные методы II
    Нестационарые методы решения линейных систем. Метод наискорейшего спуска (Steepest Descent) и сопряженных градиентов (Conjugate Gradients).
  4. [22.10.2010] Итерационные методы III
    Нахождение собственных значений и векторов матрицы с помощью степенных итерации (Power iterations). Скоросоть сходимости метода
  5. [28.10.2010] Зачет

Домашние задания

  1. [08.09.2010] Имплементировать классы stack и queue с основными операциями (push, pop, top, isEmpty, isFull)
  2. [15.09.2010] Имплементировать Jacobi и Gauss-Seidel алгоритмы решения систем линейных уравнений. Изучить и сравнить скорость сходимости на раличных тестовых натрицах - gallery('poisson'), sprandsym. рассматривать систему из 100 уравнений
  3. [20.10.2010] Имплементировать методы Steepest Descent (наискорейший спуск) и Conjugate Gradient (Сопряженные градиенты) для решения систем линейных уравнений. Сравнить сходимость со сходимостью стационарных методов. Рассматривать матрицу размером 100
  4. [22.10.2010] Имплементировать Power Iterations. Вычислить 2 (первый и второй) наибольших собственных вектора и собственных значемий.Изучить сходимость метода. Рассматривать матрицу размером 100

Модуль 2

Лекции

  1. [10.11.2010] Поисковые системы и алготирм Pagerank
    Архитектура и методы работы поисковых систем. Методы ранжирования узлов графа. Алгоритм PageRank. Сравнение порядка ранжирования. Kendall's tau. Spearman's coefficient
  2. [17.11.2010] Случайные блуждание на графе.
    Случайные блуждания на графе. Марковский процесс и стохастические матрицы.Стационарное состояние. Фундаментальная теорема Марковских цепей. Теорема Перрона-Фрабениуса
  3. [24.11.2010] Web и Поисковых Системы
    Стрктура Web. Сильно связанные компоненты. Распределение степеней узлов. Диаметр графа. Понятия Hubs и Authorities. HITS алгоритм Архитектура поисковых систем.
  4. [01.12.2010] Полнотекстовой поиск
    Алгебраическая модель представления текстовых документов. Векторная модель. Матрица терм-частота. Индексирование. Инвертированный индекс. Схожесть документов. TF-IDF
  5. [08.12.2010] Качество поиска
    Tочность и полнота. Precision at r. Метрики MAP и nDCG.
  6. [15.12.2010] Машинное обучение ранжированию
    7. Обучение с "учителем", постановка задачи, поточечные методы, регрессия.
  7. [22.12.2010] Зачет. Сдача ДЗ.
  8. [27.12.2010] Экзамен

Домашние задания

  1. [10.11.2010] а) Имплентировать алгоритм PageRank. Исследовать его сходимость для разных значений константы c, построить графики сходимости. b) Рассчитать ранг узлов по in_degree и сравнить с рангом от PageRank (для разных значений c). Для экспериментов использовать данные: web1 и web2.
  2. [17.11.2010] а) Вычислить Pagerank решением линейной системы. Сравнить скорость сходимости линейной системы со скоростью сходимости степенных интераций. Для экспериментов использовать данные: web1 и web2. b) Сравнить порядок ранжирования узлов по in_degree и pagerank для обоих графов с помощью Spearman's coefficient и Kendal's tau.
  3. [24.11.2010] а) Имплементировать алгоритм HITS. Вычислить значения hubs и authorities для web1. Сравнить ранжирование по in-degree,out-degree, hubs, authorities, pagerank. b) Построить распределения степеней узлов (in_degree, out_degree) для графа web3. и частоты слов в тексте Alice in Wonderland (частотная таблица здесь ). Найти показатель alpha в степенном законе для всех распределений
  4. [01.12.2010] Имплементировать индексатор. Построить матрицу терм-документ для коллекции текстов (перевести все слова в нижний регистр) Вычислить кореляционную матрицу текстов.
  5. [08.12.2009] Использовать в индексторе TF-IDF меру. Исключить из индекса стоп слова stop words
  6. [15.12.2009] Имплементировать ранжированный текстовой поиск на основе созданного индекса.

Литература к курсу

Matlab Учебники: Обзоры и научные статьи: