Просмотр исходного текста страницы Курс лекций «Сложность алгоритмов» (ИСПРАН, 4 курс МФТИ)

<!-- Курс лекций «Сложность алгоритмы» для 6 курса МФТИ. -->

Семестровый курс по выбору<ref>К экзамену допускаются только студенты, посетившие хотя бы одно занятие до декабря, либо, в случае критических проблем — траблы с расписанием и т.п., другая страна, тяжелая работа — договорившиеся об этом до декабря по [mailto:stas-fomin@yandex.ru email].</ref>
для студентов 4-го курса ФУПМ МФТИ.


;Лекторы: д.ф.-м.н. [mailto:nnkuz@ispras.ru Н.Н. Кузюрин], [mailto:stas-fomin@yandex.ru С.А. Фомин]

Место чтения курса в 2011 году - ИСПРАН,
Солженицына, можно найти в общем, 110 аудитория.

Время: по средам, 11:45.

Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса.

Ведется [https://spreadsheets.google.com/pub?hl=en&hl=en&key=0Ao6tsK_6FZElcGVLNjEtY3lfOHhmVHZPdGJZOXI3WHc&single=true&gid=7&output=html список посещений].

= Условия сдачи курса =

Есть два варианта:
* Исследовательский → участие в проектах [[Blog:AlgoNetMining/Идеи_для_майнинга]], показ результатов, обсуждение.
* Обычный. Изучаете нижеуказанные темы, там есть все материалы → книга, слайды, видеолекции, а также все задачи, которые могут дать на экзамене. (См. «Subpages» каждой темы, они там).

В результате, получате экзамен.

= Тренировка =

[[Special:MediawikiQuizzer/Algs-4-course-ispras|Проверь себя]], помнишь ли элементарные понятия и факты из курса.
Тест возможно будет на экзамене, чтобы отсеять совсем невменяемых.


----

= Темы =

На этих страницах слайды презентаций, задачи, и т.п.
Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.

* [[Несложно о сложности. Примеры алгоритмов]]
* [[Формально об алгоритмах. Вычислительные модели]]
* [[Жадный алгоритм в задачах о покрытии]]
* [[Жадный алгоритм покрытия для почти всех исходных данных]]
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
* [[Жадный алгоритм в задаче о рюкзаке]]
* [[Динамическое программирование для задачи о рюкзаке]]
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
* [[Полиномиальный в среднем алгоритм для SAT]]
* [[Вероятностная проверка тождеств]]
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]
* [[MAX-SAT: вероятностное округление]]
* [[MAX-SAT: дерандомизация]]
<!-- {:Дерандомизация Люби} -->
* [[MAX-CUT: вероятностное округление]]
* [[Параллельный алгоритм Люби для максимального по включению независимого множества]]

* Модель случайных графов Ердоша-Реньи. Существование рамсеевских графов.
* Пороговая функция вероятности <tt>p</tt> свойства случайных графа <m>G_{n,p}</m> быть связным, при <m>p>\frac{c\ln n}{n}, c>1</m>.

== Книга ==

Специальная верстка для чтения с ноутбуков и КПК:
* альбомная ориентация
* крупные беззасечные шрифты

Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).

Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.

[[File:book-advanced-algorithms.pdf|512px]]

== Примечания и ссылки ==
* Рекомендуется прочитать хотя бы [http://ru.wikiversity.org/wiki/%D0%9F%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%B8_%D0%BD%D0%B0%D1%83%D1%87%D0%BD%D1%8B%D0%B5_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BD%D0%B0_%D1%8F%D0%B7%D1%8B%D0%BA%D0%B5_Python первые лекции] по введению в Python и научные вычисления.

<references/>