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

2008 - 2009

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

  1. Oбзор современных алгоритмов и структур данных
  2. Основы теории графов и линейнай алгебра
  3. Современные информационные технологии information retieval
  4. Архитектура и алгоритмы поисковых систем, PageRank, Hits
  5. Измерения в интернете
  6. Передача информации и элементы криптографии
  7. Распределенные системы и алгоритмы, map-reduce
  8. Алгоритмы компрессии данных
  9. Алгоритмы для электронной коммерции
  10. Рандомизированные (случайные) алгоритмы

Лекции

Модуль 1

  1. [03.09.2008] Основы линейной алгебры и теории графов, матрицы смежности, собственные значения и вектора
  2. [10.09.2008] Основы алгоритмов и структур данных: очереди, стеки, деревья, поиск в ширину, поиск в глубину, понятие сложности алгоритма
  3. [17.09.2008] Maрковские цепи, случайные блуждания, стохастические процессы
  4. [24.09.2008] PageRank aлгоритм, теорема Перрона-Фробениуса, приводимость матрицы
  5. [01.10.2008] HITS алгоритм. Понятия Hubs и Authorities, структура веб графа
  6. [08.10.2008] Архитектура поисковых систем, инвертированный индех, хеш таблицы и хеш функции, ранжирование, точность и полонота, information retrieval
  7. [15.10.2008] Сингулярное разложение матрицы (SVD), Латенто-семантический анализ (LSI), Спектральная кластеризация графов
  8. [22.10.2008] Зачет

Модуль 2

  1. [29.10.2008] Основы криптографии
  2. [05.11.2008] Методы измерений в интернете (гостевая лекция - Spylog)
  3. [12.11.2008] Распределенные системы, архитекруа, параллельное программирование, MPI
  4. [19.11.2008] MapReduce. функциональное программирование, использование в информационных технологиях
  5. [26.11.2008] Закон Амдала, балансировние нагрузки, многоуровневые схемы делeния графa
  6. [03.12.2008] Сжатие данных, информационная энтропия, теорема Шеннона, алгоритм Хаффмана
  7. [10.12.2008] Сжатие данных без потерь, алгоритмы RLE, LZ77, LZW
  8. [17.11.2008] Контрольная работа

Модуль 3

  1. [26.01.2009] Сдача ДЗ
  2. [02.02.2009] Дискретное преобразование Фурье, FFT, сжатие с потерями, сжатие изображений, JPEG
  3. [16.02.2009] Рандомизированные алгоритмы, Лас Вегас и Монте Карло, семплирование, приближенное умножение матриц
  4. [02.03.2009] Экзамен

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

Модуль 1

  1. Рассмотреть поведение алгоритма BFS при замене очереди на стек. Написать на Matlab stack и queue.
  2. Имплементировать алгоритм PageRank, подсчитать PageRank для двух графов из раздела "Данные" и отсортировать узлы в графах по рангу.
  3. Имплементировать алгоритм HITS, подсчитать hubs и authorities для двух графов

Модуль 2

  1. Написать генератор для линейной конгруентной последовательности
  2. Имплементировать процедуру параллельного умножения матриц
  3. Имплементировать процедуру параллельного умножения разряженной матрицы на вектор, сбалансировать вычислительные нагрузки между процессорами.
  4. Вычислить информационную энтропию текста
  5. Написать процедуру построения кодировочного дерева алгоритма Хаффмана

Модуль 3

  1. Фильтрaция изображений с помощью дискретного косинус предобразования (DCT)
  2. Приблеженное умножение матриц (Монте-Карло алгоритм) с использованием 1) равномерного и 2) неравномерного семплирования

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

Книги Статьи

Данные