\documentclass[12pt]{article}
\usepackage[koi8-r]{inputenc}
\usepackage{fullpage,url}
\usepackage[russian,english]{babel}
%\advance\topmargin by -5mm
%\advance\textheight by 15mm
%\advance\textwidth by 1cm 
\begin{document}
\selectlanguage{russian}
\centerline{\large\bfseries 
Программа экзамена по с/к\ \ {\sc Эффективные алгоритмы --- II}
}
\bigskip
\begin{enumerate}
\item 
Поиск минимального сечения.
\item 
Поиск минимального остовного дерева.
\item 
Детерминированный поиск подстроки за линейное время.
\item
Полиномиальный алгоритм для решения задачи линейного программирования: 
подробное описание алгоритма (без доказательств лемм).
\item
Полиномиальный алгоритм для решения задачи линейного программирования: 
доказательства лемм.
\item
Вероятностная проверка простоты числа. 
\item
Рисование планарного графа.
\item
Параллельный алгоритм для задачи о максимальном независимом множестве.
\item
Приближенный алгоритм для задачи о рюкзаке.
\item
Приближенный алгоритм для задачи о покрытии множествами.
\item
Приближенный алгоритм для задачи о раскраске графа.
\item
Приближенный алгоритм для задачи о коммивояжере в метрическом пространстве.
\item
Вероятностный алгоритм для 3-SAT. 
\item
Приближенный алгоритм для минимального вершинного покрытия.
\item
Вычисление максимального потока.
\item
Приближенный подсчет количества наборов,
выполняющих формулу в ДНФ: подробное описание 
детерминированного алгоритма в общем случае
(со всеми конструкциями, но без доказательств) с оценкой времени
его работы.
\item
Приближенный подсчет количества наборов,
выполняющих формулу в ДНФ: подробное описание детерминированного
алгоритма в общем случае
(доказательство корректности и всего, необходимого для нее).
\item
Приближенный подсчет количества наборов,
выполняющих формулу в ДНФ: детерминированный алгоритм 
для формул с короткими конъюнкциями,
доказательство корректности и полиномиальной оценки времени его работы.
\end{enumerate}

\bigskip
\centerline{\bfseries Основной источник} 
\medskip
\noindent{}Конспект лекций, 
\url{http://logic.pdmi.ras.ru/~hirsch/students/index.html}
\smallskip

\bigskip
\centerline{\bfseries Дополнительная литература:}
\smallskip
\begin{enumerate}
\item R.Motwani, P.Raghavan, ``Randomized Algorithms''.
      Cambridge University Press, 1995.
\item R.Motwani, Approximation Algorithms.
\item А.Ахо, Дж.Хопкрофт, Дж.Ульман,
      ``Построение и анализ вычислительных алгоритмов''.
      М.: Мир, 1979.
\item Кормен, Лейзерсон, Ривест, \ldots.
\item C.H.Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
\item N.Karmarkar, A New Polynomial-Time Algorithm for Linear Programming,
      \emph{Combinatorica} 4(4) 373--396, 1984.
\item J.H{\aa}stad, электронный конспект курса по алгоритмам.
\item U.Zwick, электронный конспект курса по алгоритмам.
\item N.Nisan, A.Wigderson, Hardness and Randomness,
      \emph{JCSS} 49(2) 149--167, 1994.
\item M.Luby, B.Veli\^ckovi\'c, A.Wigderson,
      Deterministic Approximate Counting of Depth-2 Circuits.
\item M.Luby, B.Veli\^ckovi\'c,
      On Deterministic Approximation of DNF. 
\item J.H{\aa}stad, PhD Thesis.
\end{enumerate}
\bigskip
\centerline{\bfseries Полезные адреса в Интернет:}
\smallskip
\url{http://logic.pdmi.ras.ru/~hirsch/}\hfill(Э.А.Гирш),
\url{http://theory.stanford.edu/people/motwani/}\hfill(Rajeev Motwani),
\url{http://www.nada.kth.se/~johanh/}\hfill(Johan H{\aa}stad),
\url{http://www.math.tau.ac.il/~zwick/}\phantom{WWWWWWWWWW}\hfill(Uri Zwick),
\url{http://www.cs.huji.ac.il/~noam/}\hfill(Noam Nisan),
\url{http://www.icsi.berkeley.edu/~luby/}\hfill(Michael Luby),
\url{http://www.cs.huji.ac.il/~avi/}\hfill(Avi Wigderson).
\end{document}