|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Chislov 2:5020/400 19 Aug 2002 16:59:07
To : Stanislav Shwartsman
Subject : Re: Типы NP-полных задач
--------------------------------------------------------------------------------
SS> Самые известные, базовые проблемы (которые мы в
SS> ВУЗе изучали):
SS> 1. Circuit-SAT
SS> Given a boolean combination circuit composed
SS> of AND-OR-NOT gates,
SS> is satifable ?
SS> 2. Boolean Formula Satisfiability (CNF-SAT,
SS> 3-CNF-SAT)
SS> 3. Clique
SS> 4. Vertex Cover
SS> 5. Set Cover
SS> 6. Hamilton Cycle
SS> 7. Travelling Salesman Problem
SS> Дерево редукции:
SS> 7 -> 6 -------> 2 -> 1
SS> 5 -> 4 -> 3 /
SS> Hадо - могу PDF с лекциями выслать. Hа англите.
SS> Основные проблемы
SS> (см. выше) с доказательствами.
Привет!
Вышли и мне, плиз, лекции по NP задачам. Особенно интересуют задачи про
р-центры и р-медианы.
Спасибо.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
