Участник:Mikhail Dvorkin

Материал из Википедии — свободной энциклопедии

Содержание 1 Об участнике 2 Не забыть сделать 3 Цели и интересы 4 Какая от меня польза кроме вреда? 4.1 Алгоритмы и структуры данных 4.2 NP-полные задачи 4.3 Разное

[править] Об участнике

• Михаил Эдуардович Дворкин
• дворкин@дождь.ифмо.ру
• darnley.livejournal.com
• dvorkin.moikrug.ru

[править] Не забыть сделать

• Теория вычислительной сложности
• Задача проверки изоморфизма графов
• Задача SATCNF
• Задача k-SAT
• Задача 2-SAT
• Теорема Кука — переписать с нуля
• Задача распознавания
• Планарный граф
• Физико-техническая школа (Санкт-Петербург) — викифицировать и дополнить.
• Дизъюнкция, Конъюнкция, Отрицание
• Нормальная форма (логика)
• Конъюнктивная нормальная форма, Дизъюнктивная нормальная форма
• Булева формула — улучшить, совместить с пропозициональной формулой
• Формальная грамматика и иже с ними
• Аксиомы отделимости - дополнить
• Консенсусное число и вообще все параллельное программирование
• Полином Жегалкина

[править] Цели и интересы

• Максимально расширить Список NP-полных задач
• Рассказать в википедии о теории вычислительной сложности
• Улучшить существующие статьи по теории графов
• Улучшить существующие статьи по математической логике

[править] Какая от меня польза кроме вреда?

Мой вклад.

[править] Алгоритмы и структуры данных

• Алгоритм Беллмана-Форда

[править] NP-полные задачи

• Какуро
• Обобщённое судоку
• Задача выполнимости булевых формул

[править] Разное

• Театр Дождей
• Никитина, Наталья Васильевна