\documentclass[11pt,fleqn,a4paper]{article}
% 
% Packages used:
%
\usepackage[koi8-r]{inputenc}
\usepackage[russian,english]{babel}
\usepackage{fullpage}
\advance\textwidth by 5mm
\advance\textheight by 2cm
\advance\topmargin by -5mm
%
% Common customization:
%
\pagestyle{headings}
\def\rightmark{\fbox{\parbox{161mm}{Э.А.Гирш: <<Информатика>> (1й семестр, поток МО ЭВМ, декабрь 2005/6 уч.г.)}}}
\thispagestyle{empty}
%
% Things to customize for the course are here:
%
%
% The document
%
\begin{document}
\selectlanguage{russian}

\centerline{\LARGE Вопросы к коллоквиуму по курсу <<Информатика>>}
\centerline{\small (1й семестр, поток МО ЭВМ, декабрь 2005/6 уч.г.)}
%\centerline{\bfseries\itshape (Предварительный список)}

\begin{enumerate}
\item Массовая задача. Тезис Ч\"ерча. 
      Равнодоступная адресная машина. 
      Время работы алгоритма и используемая память.

\item Рекурсия, ее реализация на компьютере и способы избавления от нее
      (на примере задачи о рюкзаке).

\item Структуры данных (массив, файл, очередь, очередь с приоритетами,
      стек, одно- и двунаправленные списки, словарь).

\item Красно-черные деревья. Реализация операций над ними.
      Порядковая статистика для красно-черных деревьев.
\item B${}^+$-деревья. Реализация операций над ними.
\item Хеш-таблицы. Построение универсального семейства хеш-функций.

\item Сложность рекурсивных алгоритмов.
\item Алгоритм Штрассена для умножения матриц над кольцом. 
      Умножение булевых матриц.
\item Нахождение пары ближайших точек на плоскости. 
\item Рекурсивный алгоритм для умножения чисел.

\item Сортировка на четырех лентах.
\item HeapSort.
\item QuickSort. Randomized QuickSort.
\item Поиск $k$-го элемента в массиве.
\item Лексикографическая сортировка.

\item Задача о поиске подстроки: решение при помощи конечного автомата
      и при помощи таблицы откатов.

\item Конечные автоматы. Регулярные выражения.
      Замкнутость регулярных языков относительно теоретико-множественных операций.
      Алгоритмические проблемы, разрешимые для регулярных языков.

\item Лемма о разрастании для регулярных языков.
      Язык, не являющийся регулярным.

%\item Дискретное преобразование Фурье (ДПФ).
%      Теорема об отрицательно обернутой свертке.
%      Вычисление ДПФ.
%\item Алгоритм Ш\"енхаге-Штрассенa
%      (без вычисления ДПФ, но с ``простым'' рекурсивным алгоритмом).

\item Рекурсивно-перечислимые и рекурсивные множества.
%      Многоленточные машины Тьюринга.
      Универсальная равнодоступная адресная машина.
      Существование рекурсивно-перечислимого, но не рекурсивного множества.

\item Классы $\mathcal{P}$, $\mathcal{NP}$, $\mathcal{PSPACE}$, $\mathcal{EXP}$.
      Полиномиальные свед\'ения. $\mathcal{NP}$-полные задачи.

\item $\mathcal{NP}$-полнота задач Circuit-SAT и SAT.

\item Вероятностные алгоритмы. Класс $\mathcal{RP}$. Алгоритм для выяснения того,
      что число является составным.

\item Классы DTime${}_R(f)$, доказательство того, что они различны.

\item Общая схема кодирования с открытым ключом.
      Односторонние функции, сильно односторонние функции.
      RSA. 

\item Задача о поиске подстроки: алгоритм с использованием
      случайных чисел.
%
%\item Приближенные алгоритмы. Приближенные алгоритмы для задач
%      о рюкзаке, покрытии множествами, наименьшей общей
%      надпоследовательности, наименьшего вершинного покрытия,
%      задачи о коммивояжере в метрическом пространстве.

%\item Параллельные алгоритмы. Модели параллельных вычислений.
%      Принцип Брента. Параллельные алгоритмы для умножения булевых матриц,
%      достижимости в графе, вычисления определителя, арифметических
%      операций над целыми числами.


\end{enumerate}

\end{document}

