Сложность вычислений 4. NP-полные задачи

Uploaded By: Myvideo

Published on

25 Aug 2024

1 view

0

0 votes

0

About Share Download Add to

Извиняемся. Последний кусок лекции не записался. В качестве компенсации предлагаем вам изучить оставшийся материал по текущей версии книжки лектора (с 394 страницами): Раскраски, c. 103. Теорема (там доказана сводимость 3SAT к 3COL без использования посредника NAE-3SAT); Покрытие множествами и задача о рюкзаке, c. 109. 00:00:00 - заставка 00:02:00 - напоминание с предыдущей лекции 00:07:16 - определения CLIQUE, INDSET, VERTEXCOVER 00:13:47 - полнота VERTEXCOVER 00:34:10 - теорема о частном случае 00:43:54 - план доказательства полноты 3COL 00:45:56 - сводимость 3SAT к NAE-3SAT 00:57:00 - сводимость NAE-3SAT к 3COL (не доведено) Дата лекции: Лектор: Мусатов Даниил Владимирович Оператор: Иванов Максим Монтажёр: Хатымов Ренат Плейлист:

Share with your friends

Link:

Embed:

<iframe width="640" height="360" src="//myvideo.cc/embed/Y3cvT1d6eFRLbnJkQmthUlJ5c2NNUEVNem84SktzTWVpWHF0b21ZNzVXUT0" frameborder="0" webkitallowfullscreen mozallowfullscreen allowfullscreen></iframe>

Video Size:

Custom size:

x

Autoplay video

Hide player controls

Hide resume playing

Add to Playlist:

Favorites

My Playlist

Watch Later

Квантовая реальность: Пространство, время и иллюзии - Теория всего

2 days ago

01:30:19

Квантовая реальность: Пространство, время и иллюзии - Теория всего

1 33%

ВидеоВС РФ сожгли пикап ВСУ с расчётом БПЛА под КураховоФронт на Донбассе кипит, мы уже писали о том, что ВС РФ активно

2 days ago

00:00:23

ВидеоВС РФ сожгли пикап ВСУ с расчётом БПЛА под КураховоФронт на Донбассе кипит, мы уже писали о том, что ВС РФ активно

47 41%

Третья сложность цикличного вычисления (Надёр жёпы СЭМа)

3 days ago

00:06:02

Третья сложность цикличного вычисления (Надёр жёпы СЭМа)

1 23%

Расчет заземляющих устройств

7 days ago

01:29:29

Расчет заземляющих устройств

1 89%

ВЕБИНАР. КОНФИГУРАТОР СОУЭ: онлайн-подбор и расчет оборудования для сложных и распределенных систем.

1 week ago

01:01:06

ВЕБИНАР. КОНФИГУРАТОР СОУЭ: онлайн-подбор и расчет оборудования для сложных и распределенных систем.

1 5%

ВЕБИНАР. Модуль расчета звукового давления. Быстрый и точный расчет проектов СОУЭ в AutoCAD!

1 week ago

01:16:32

ВЕБИНАР. Модуль расчета звукового давления. Быстрый и точный расчет проектов СОУЭ в AutoCAD!

2 7%

Работа с Серво и ШД. 2 часть обучения программированию ПЛК Omron. Импульсное управление.

1 week ago

01:10:04

Работа с Серво и ШД. 2 часть обучения программированию ПЛК Omron. Импульсное управление.

25 23%

Компьютер для ИИ за 12 млн.руб. - 2x RTX 6000 Ada Generation / 2x AMD EPYC 9754 / RAM 6Tb /SSD 32Tb

1 week ago

00:27:40

Компьютер для ИИ за 12 млн.руб. - 2x RTX 6000 Ada Generation / 2x AMD EPYC 9754 / RAM 6Tb /SSD 32Tb

1 82%

Задорнов, Михаил Николаевич - Биография

1 week ago

00:09:07

Задорнов, Михаил Николаевич - Биография

1 34%

Математика - + конспект от YandexGPT

1 week ago

01:39:02

Математика - + конспект от YandexGPT

9 52%

Спортивный анализ данных - + конспект от YandexGPT

1 week ago

01:20:18

Спортивный анализ данных - + конспект от YandexGPT

7 73%

НЕСНИЖАЕМЫЙ остаток и МАКСИМАЛЬНЫЙ запас в расчете заказа поставщику. Варианты расчета при закупках!

2 weeks ago

00:17:51

НЕСНИЖАЕМЫЙ остаток и МАКСИМАЛЬНЫЙ запас в расчете заказа поставщику. Варианты расчета при закупках!

3 32%

50 Способов получения дохода Расчет пассивного дохода от инвестиций

2 weeks ago

00:01:14

50 Способов получения дохода Расчет пассивного дохода от инвестиций

10 93%

Мой сайт ГидРаВПТ.Рф на платформе NETHOUSE

2 weeks ago

00:19:14

Мой сайт ГидРаВПТ.Рф на платформе NETHOUSE

1 32%

ЭТО БУДЕТ НА ВПР по математике 7 класс | РАЗБОР ДЕМО ВАРИАНТА 2023 2024 год

2 weeks ago

00:49:56

ЭТО БУДЕТ НА ВПР по математике 7 класс | РАЗБОР ДЕМО ВАРИАНТА 2023 2024 год

3 23%

HYPERPC Компьютер для ИИ за 12 млн.руб. - 2x RTX 6000 Ada Generation / 2x AMD EPYC 9754 / RAM 6Tb /SSD 32Tb

2 weeks ago

00:27:39

HYPERPC Компьютер для ИИ за 12 млн.руб. - 2x RTX 6000 Ada Generation / 2x AMD EPYC 9754 / RAM 6Tb /SSD 32Tb

68 87%

Flownex: современные технологии моделирования и расчет сложных гидравлических процессов

2 weeks ago

00:02:38

Flownex: современные технологии моделирования и расчет сложных гидравлических процессов

1 36%

Konstantin Vladimirov Практика языка C (МФТИ, 2023-2024). Семинар 8.2. Решение уравнений и вычисление функций.

2 weeks ago

01:36:31

Konstantin Vladimirov Практика языка C (МФТИ, 2023-2024). Семинар 8.2. Решение уравнений и вычисление функций.

41 42%

Компьютер для ИИ за 12 млн.руб. - 2x RTX 6000 Ada Generation / 2x AMD EPYC 9754 / RAM 6Tb / SSD 32Tb

2 weeks ago

00:27:39

Компьютер для ИИ за 12 млн.руб. - 2x RTX 6000 Ada Generation / 2x AMD EPYC 9754 / RAM 6Tb / SSD 32Tb

121.7K 46%

Умножение в столбик. Как правильно умножать в столбик Как объяснить умножение в столбик

2 weeks ago

00:14:39

Умножение в столбик. Как правильно умножать в столбик Как объяснить умножение в столбик

235 47%

Как объяснить деление в столбик Деление чисел уголком. Деление на многозначного на однозначное.

2 weeks ago

00:11:46

Как объяснить деление в столбик Деление чисел уголком. Деление на многозначного на однозначное.

231 43%

Деление трехзначных чисел на однозначное. Как объяснить ребенку деление трехзначного числа

2 weeks ago

00:12:44

Деление трехзначных чисел на однозначное. Как объяснить ребенку деление трехзначного числа

260 33%

Письменное сложение трехзначных чисел. Сложение трехзначных чисел в столбик

2 weeks ago

00:06:24

Письменное сложение трехзначных чисел. Сложение трехзначных чисел в столбик

44 47%

Нейросети скоро захватят весь мир )

2 weeks ago

00:01:43

Нейросети скоро захватят весь мир )

2 38%

0 Comments

Guest