СПб.: Санкт-Петербургский государственный университет (СПбГУ);
Санкт-Петербургское отделение Математического института им.
В.А.Стеклова (ПОМИ) РАН, Гирш Э.А., 2005 г.
Курс лекций прочитан в Санкт-Петербургском государственном
университете (СПбГУ) в 2005 г. Материал включает в себя конспекты
лекций по указанному курсу.
Введение в предмет. Литература. Модели вычислений. Сложность
алгоритмов.
Представление данных.
Рекурсия и избавление от нее.
Словари. Деревья. Красно-черные деревья.
Сложность рекурсивных алгоритмов. Умножение матриц (над кольцом и булевых). Простой рекурсивный алгоритм для умножения целых чисел. Нахождение пары ближайших точек на плоскости.
Сортировка произвольных данных. Порядковые статистики.
Лексикографическая сортировка.
Конечные автоматы. Задача о поиске подстроки.
Вычислимость и сложность.
Введение в криптографию с открытым ключом.
Вопросы к коллоквиуму по курсу «Информатика».
Представление данных.
Рекурсия и избавление от нее.
Словари. Деревья. Красно-черные деревья.
Сложность рекурсивных алгоритмов. Умножение матриц (над кольцом и булевых). Простой рекурсивный алгоритм для умножения целых чисел. Нахождение пары ближайших точек на плоскости.
Сортировка произвольных данных. Порядковые статистики.
Лексикографическая сортировка.
Конечные автоматы. Задача о поиске подстроки.
Вычислимость и сложность.
Введение в криптографию с открытым ключом.
Вопросы к коллоквиуму по курсу «Информатика».