Информатика
(поток математиков, 1 курс, 2002/03 уч. г.)

• Фрагменты конспекта (in Russian).

  Предупреждение: Данные фрагменты конспекта не полностью отражают курс! В них имеются  пропуски и неточности. Часть материала дана лишь схематически. Разбиение на "лекции" - произвольно.

  Лекции первого семестра.

  • Лекция 2: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Представление данных. Очередь. Стек. Рекурсия.
  • Лекция 3: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    HeapSort. QuickSort. Поиск k-го элемента в массиве.
  • Лекция 4: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Файлы. Сортировка на четырех лентах. Списки. Хеш-таблицы. Деревья.
  • Лекция 5: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Граф и его представление в машине. Поиск в глубину. Минимальное остовное дерево.
  • Лекция 6: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Нахождение кратчайших путей. Лексикографическая сортировка. Изоморфизм деревьев. Максимальный поток.
  • Лекция 7: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Рисование планарного графа. Сложность рекурсивных алгоритмов. Умножение матриц (над кольцом и булевых). Нахождение пары ближайших точек на плоскости.
  • Лекция 8: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Нахождение пары пересекающихся отрезков. Построение выпуклой оболочки.
  • Список вопросов к коллоквиуму (по лекциям первого семестра):
    HTML file, TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Список успешно сдавших этот коллоквиум в первом семестре.

  Лекции второго семестра:

  • Лекция 9: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Теория формальных языков (I): языки, регулярные выражения и грамматики; недетерминированные конечные автоматы.
  • Лекция 10: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Теория формальных языков (II): праволинейные грамматики, их эквивалентность регулярным выражениям, детерминированным и недетерминированным конечным автоматам; лемма о разрастании для них; свойства регулярных языков.
  • Лекция 11: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Теория формальных языков (III): бесконтекстные языки, лемма о разрастании для них, магазинные автоматы, проверка принадлежности бесконтектному языку.
  • Лекция 12: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Теория формальных языков (IV): рекурсивно-перечислимые языки, алгоритмическая неразрешимость.
  • Лекция 13: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Элементы теории сложности: классы P, NP, RP; NP-полные задачи; вероятностная проверка простоты числа.
  • Лекция 14: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Приближенные алгоритмы для задач о рюкзаке и коммивояжере.
  • Лекция 15: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Приближенные алгоритмы для задач о покрытии множествами и о кратчайшей общей надпоследовательности. Поиск подстроки.
  • Лекция 16: TeX source, DVI file, Postscript file, compressed Postscript file, PDF
    Алгоритм Шенхаге-Штрассена (часть I: сам алгоритм).
  • Лекция 17: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Алгоритм Шенхаге-Штрассена (часть II: вычисление ДПФ и оценка времени работы всего алгоритма).
  • Лекция 18: TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
    Параллельные алгоритмы.
  • Предварительный список вопросов к зачету (по лекциям второго семестра - для сдавших коллоквиум):
    HTML file, TeX source, DVI file, Postscript file, compressed Postscript file, PDF file.
  
  

• Полезная литература:

  • A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974. Перевод: А. Ахо, Дж. Хопкрофт, Дж. Ульман, Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

  • T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms. MIT Press/McGraw-Hill, 1990. Перевод: Т. Кормен, Ч. Лейзерсон, Р. Ривест, Алгоритмы: построение и анализ. М.: МЦНМО, 2000.

  • A. V. Aho and J. Ullman, The theory of parsing, translation and compiling. Volume 1: Parsing. Prentice-Hall, 1972. Перевод: А. Ахо, Дж. Ульман, Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ. М.: Мир, 1978.

  • S. Ginsburg, The mathematical theory of context-free languages. Mc. Graw-Hill, 1966. Перевод: С. Гинзбург, Математическая теория контекстно-свободных языков. М.: Мир, 1970.
  
  

• Ссылки (менее полезные для сдачи курса, чем указанная выше литература):

  • J. Håstad, Advanced Algorithms (lecture notes in English: compressed Postscript file, 490 Kb).
  • E. A. Hirsch, Efficient Algorithms (lecture notes in Russian).
  • J. V. Romanovsky, Discrete Analysis (lecture notes in Russian). This monograph was published in 2000.