Недетерминированные алгоритмы

1. Недетерминированные алгоритмы

НЕДЕТЕРМИНИРОВАННЫЕ
АЛГОРИТМЫ
Работу выполнили:
Иванов Макар
Таушева Олеся
(Группа 1213)

2. Цель и задачи

Цель работы: изучение np-алгоритмов.
Задачи:
Выяснить, что такое np-алгоритмы и в
чем их отличительная черта.
Рассмотреть типовые np-задачи.
Рассмотреть проблему P ≠ NP

3. Определение NP-алгоритмов

NP (non-deterministic polynomial) это класс задач, которые можно
решить на недетерминированной
машине Тьюринга за
полиномиальное время.

4. Машина Тьюринга

В недетерминированной
машине Тьюринга для
каждой комбинации
состояния и символа
существует несколько
вариантов перехода и
действия.

5. NP-сложные и NP-полные задачи

Класс NP-сложные
задачи – это
задачи, к которым
может быть
сведена любая
другая NP задача
за
полиномиальное
время.
NP-полные задачи
– это задачи класса
NP, к которым
можно свести
любую другую
задачу этого класса
за
полиномиальное
время.

6. P = NP?

7. Раскраска графа

Раскрасить заданный граф в n-е количество
цветов.

8. Раскладка по ящикам

5
6
4
10
5
1
10
6
10
9
4
2
10
9
10
3
10
1
10
3
2
10

9. Задача о ранце

#include <iostream>
#include <windows.h>
#include <vector>
using namespace std;
int knapsack2(const int* weight, const
int* cost, int V, int N)
{
vector<vector<int> > dp(V + 1,
vector<int>(N + 1, 0));
for (size_t j = 1; j <= N; j++)
{
for (int w = 1; w <= V; w++)
{

10. Задача о сумме подмножеств

#include<iostream>
using namespace std;
int a[107];
void printmask(int mask, int n)
{
for (int i = 1; i <= n; i++)
{
if (mask % 2)
{

11. Задача коммивояжера

#include "stdafx.h"
#include "iostream"
#include "fstream"
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
vector<int> put;
vector<int> minput;
fstream fin, fout;
int graph[1000][1000];//вершины графа хранятся в статическом
двумерном массиве
int minrast=-1;//устанавливаем минимальную дистанцию

12. Задача коммивояжера

13. Спасибо за внимание

СПАСИБО ЗА ВНИМАНИЕ