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

Осень 2009 / Fall 2009

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

  1. Oбзор современных алгоритмов и структур данных / Review of modern algorithms and data structures
  2. Основы теории графов и линейнoй алгебры / Graph theory and linear algebra fundamentatls
  3. Итеративные методы решения линейных уравнений / Iterative methods for linear systems solutions
  4. Обработка и поиск текстовой информации / Text mining
  5. Архитектура и алгоритмы поисковых систем / Search engine architecture and algorithms
  6. Методы и алгоритмы анализа данных: классификация / Data mining methods and algorithms: classification
  7. Передача информации и Алгоритмы компрессии данных / Information transmission and data compression.
  8. Элементы криптографии / Elements of cryptography

Модуль 1 / Module 1

Лекции / Lectures

  1. Введение / Course overview [3.09.2009]
    Основы линейной алгебры и теории графов, матрицы смежности, собственные значения и вектора
  2. Основы алгоритмов и структур данных / Fundamentals of algorithms and data structures [8.09.2009]
    Oчереди, стеки, связанные списки, бинарные деревья, поиск в ширину, поиск в глубину, понятие сложности алгоритма
  3. Основы обьектно-ориентированного программирования / Basics of object-oriented programming [15.09.2009]
    Понятия классов, обьектов, методов, наследования. Практические примеры объектно-ориентированного программирования на Matlab
  4. Хеш таблицы / Hash tables [22.09.2008]
    Хеширование. Вычисление ключей. Хеш функции. Методы разрешения коллизий. Двойное хеширование
  5. Итерационные методы I / Iterative methods I [29.09.2009]
    Итеративные методы решений систем линейных уравнений. Стационарные методы. Методы Jacobi и Gauss-Seidel. Сходимость методов.
  6. Итерационные методы II / Iterative methods II [6.10.2009]
    Нахождение собственных значений и векторов матрицы с помощью степенных итерации (Power iterations). Скоросоть сходимости метода
  7. Итерационные методы III / Iterative methods III [13.10.2009]
    Нестационарые методы решения линейных систем. Метод наискорейшего спуска (Steepest Descent) и сопряженных градиентов (Conjugate Gradients).
  8. Зачет / Exam [20.10.2009]

Домашние задания / Home assignments

  1. [8.09.2009] Имплементировать классы stack и queue с основными операциями (push, pop, top, isEmpty, isFull)
  2. [15.09.2009] Имплементриовать связaнный лист (linked list) с основными операциями (find, insert, insertAfter)
  3. [22.09.2008] Имплементировать hash table с основными операциями (insert, find, delete) и создать словарь. Для поличения ASCII кодов char в Matlab использовать функцию int32()
  4. [29.09.2009] Имплементировать Jacobi и Gauss-Seidel алгоритмы решения систем линейных уравнений. Изучить и сравнить скорость сходимости на раличных тестовых натрицах - gallery('poisson'), sprandsym. рассматривать систему из 100 уравнений
  5. [6.10.2009] Имплементировать Power Iterations. Вычислить 2 (первый и второй) наибольших собственных вектора и собственных значемий. Изучить сходимость метода. Рассматривать матрицу размером 100
  6. [13.10.2009] Имплементировать методы Steepest Descent (наискорейший спуск) и Conjugate Gradient (Сопряженные градиенты) для решения систем линейных уравнений. Сравнить сходимость со сходимостью стационарных методов. Рассматривать матрицу размером 100

Модуль 2 / Module 2

Лекции / Lectures

  1. Алгоритмы веб поиска: PageRank / Web search algorithms: PageRank [27.10.2009]
    Случайные блуждания на графе. МарковсКий процесс и стохастические матрицы. Теорема Перрона-Фрабениуса. Приводимость матриц. Алгоритм PageRank. Методы ранжирования узлов графа
  2. Алгоритмы веб поиска: HITS / Web search algorithms: HITS [03.11.2009]
    HITS алгоритм. Понятия Hubs и Authorities, структура веб графа. Сравнение ранжировок, Kendall-Tau и Spearman's rho.
  3. Полнотекстовой поиск / Full text search [10.11.2009]
    Text search,indexing, инвертированный индех, хеш таблицы, Vector space model.
  4. Обработка текстовой информации / Information retrieval [17.11.2009]
    точность и полнота, aрхитектура поисковых систем
  5. Алгоритмы классификации I / Classification algorithms I [24.11.2009]
    Понятия классификация и кластеризаии. Простейшие алгоритмы для классификации - Rocchio и kNN. Training and testing. Классификация текстовых данных.
  6. Алгоритмы классификации II / Classification algorithms II [01.12.2009]
    Вероятностные методы, алгоритм Байеса. Naive Bayes classifier. Оценка качества multiclass классификатора, матрица ошибок (confusion matrix).
  7. Алгоритмы классификации III / Classification algorithms III [08.12.2009]
    Feature selection methods: "mutual information" и "chi squared" - методы выбора признаков (атрибутов) для алгоритмов кластеризации.
  8. Контрольная работа / Exam [15.12.2009]

Домашние задания / Home assignments

  1. [27.10.2009] а) Имплентировать алгоритм PageRank. Исследовать его сходимость для разных значений константы c, построить графики b) Рассчитать ранг узлов по in_degree и сравнить с рангом от PageRank (для разных значений c). Для экспериментов использовать данные: web1 и web2.
  2. [03.11.2009] а) Вычислить hubs and authorities scores для web1. b) Имплементировать алгоритм для вычисления Kendall tau и сравнить ранжировки узлов графа алгоритмами PageRank, HITS, In_Degree.
  3. [10.11.2009] Имплементировать indexer на основе hash table. Построить term-document matrix для коллекции текстов и вычислить скоррелированность текстов. Перевести весь текст в нижний регистр, использовать stop words список
  4. [17.11.2009] Имплементировать ранжированный текстовой поиск на основе созданного индекса
  5. [24.11.2009] Имплементировать Rocchio и kNN классифиакаторы для текстовых данных. Для обучения использовать любые пять групп из"20 newsgroup" (80% данных использовать для обучения 20% для верификации, достаточно обработать ~100-200 документов из каждого класса) Протестировать работу классификатора и составить матрицу ошибок (confusion matrix)
  6. [01.12.2009] Имплементировать Naive Bayes классификатор для текстовых данных. Для обучения использовать любые пять групп из "20 newsgroup". (80% данных использовать для обучения 20% для верификации, достаточно обработать ~100-200 документов из каждого класса) Протестировать работу классификатора и составить матрицу ошибок (confusion matrix)
  7. [08.12.2009] Имплементировать один из двух feature selection ("mutual information" или "chi squared") методов. Использовать его для отбора атрибутов для любого из классификаторов. Вычислить матрицу ошибок и сравнить с предыдущими результатами.

Модуль 3 / Module 3

Лекции / Lectures

  1. Алгоритмы компресси данных I / Data compression algorithms I [20.01.2009]
    Хранение и передача информации. Информационная энтропия. Сжатие без потерь. Теорема Шеннона. Алгоритм Хаффмана.
  2. Алгоритмы компресси данных II / Data compression algorithms [01.02.2010]
    Сжатие без потерь, алгоритмы RLE, LZ77, LZW
  3. Основы криптографии / Fundamentals of cryptography [08.02.2010]
    Симметричные ключи. Системы с открытыми ключами. RSA public-key cryptography
  4. Контрольная работа / Exam [22.02.2010]

Домашние задания / Home assignment

  1. [20.01.2010] Вычислить информациоанную энтропию текста.Построить гистограмму распределения частот символов. Имплементирoвать алгоритм Хаффмана для компрессии данных (encode, decode). Для тестирование использовать данные ...
  2. [01.02.2010] Имплементирoвать алгоритм LZ77
  3. [15.02.2010] Имплементирoвать RSA алгоритм. Воспользоваться библиотекой Variable Precision Integer Arithmetic

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

Научные статьи / Papers Матлаб / Matlab Книги / Textbooks Дополнительная литература / Additional literature