Информатика
(поток информатики, 1й курс набора 2005 г.)

• Список сдававших коллоквиумы.

• Второй семестр.

  • Вопросы к второму коллоквиуму.

• Первый семестр.

  • Программа первого коллоквиума (по лекциям первого семестра):
    TeX source, PDF file, Postscript file, compressed Postscript file.

  • В помощь студентам: файлы, скомпилированные из обрывков конспектов других (но в ряде случаев похожих) курсов предыдущих лет. Разбиение материала на «лекции» условно. Файлы эти безусловно содержат неточности, ошибки и пропуски, не покрывают целиком курс, и ни в коем случае не могут служить заменой собственному конспекту. Итак:

    • План лекции 1: Введение в предмет. Литература. Модели вычислений. Сложность алгоритмов.
      [.tex] [.pdf] [.ps] [.ps.gz]
    • План лекции 2: Представление данных.
      [.tex] [.pdf] [.ps] [.ps.gz]
    • Лекция 3: Рекурсия и избавление от нее.
      [.tex] [.pdf] [.ps] [.ps.gz]
    • План лекции 4: Словари. Деревья. Красно-черные деревья.
      [.tex] [.pdf] [.ps] [.ps.gz]
    • Лекция 5: B⁺-деревья. Хеш-таблицы.
      Материал лекции 5 отсутствует. О хеш-таблицах можно прочесть в книге Кормена, Лейзерсона и Ривеста.
    • Лекция 6: Сложность рекурсивных алгоритмов. Умножение матриц (над кольцом и булевых). Простой рекурсивный алгоритм для умножения целых чисел. Нахождение пары ближайших точек на плоскости.
      [.tex] [.pdf] [.ps] [.ps.gz]
    • Лекция 7: Сортировка произвольных данных. Порядковые статистики.
      [.tex] [.pdf] [.ps] [.ps.gz]
    • Лекция 8: Лексикографическая сортировка.
      [.tex] [.pdf] [.ps] [.ps.gz]
    • Лекция 9: Конечные автоматы. Задача о поиске подстроки.
      [.tex] [.pdf] [.ps] [.ps.gz]
    • Лекция 10: Вычислимость и сложность (много пробелов!).
      [.tex] [.pdf] [.ps] [.ps.gz]
    • Лекция 11: Введение в криптографию с открытым ключом.
      [.tex] [.pdf] [.ps] [.ps.gz]

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

    • 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.

  • Дополнительная литература по теории чисел:

    • И.М.Виноградов, Основы теории чисел. М.: Наука, 1981.