АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Примеры NP полных задач

Читайте также:
  1. C) Любой код может быть вирусом для строго определенной среды (обратная задача вируса)
  2. I. ПРЕДМЕТ И ЗАДАЧИ
  3. III. ЗАДАЧІ
  4. L Перевірка виконання домашньої задачі.
  5. VIII. Работа над задачей
  6. Б. На отдельной тетради решить контрольные задачи.
  7. Бухгалтерский учет его функции, задачи и принципы.
  8. ВАРІАНТИ ЗАДАЧ
  9. Введение в психологию человек. Определение психологии человека как науки. Задачи и место психологии в системе наук.
  10. Введение. Цели и задачи БЖД
  11. ВВЕДЕНИЕ. ЦЕЛИ И ЗАДАЧИ КУРСА МСС ПРОДУКЦИИ.
  12. Виды бухгалтерского учета, их значение, характеристика и выполняемые задачи.

Примеры NP-полных задач:

1. Гамильтонов цикл.

Дан граф G c n вершинами. Существует ли в графе простой цикл, проходящий через все вершины графа? Простым называется цикл, в котором вершины не повторяются. Таким образом, гамильтонов цикл — это последовательность вершин и дуг (ребер) графа, содержащая все вершины графа G по одному разу, но, может быть, содержащая не все дуги.

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

Дан граф G с п вершинами. Каждому ребру графа приписано положительное целое число di, задающее длину ребра. Кроме этого, задано некоторое положительное целое число L. Требуется ответить на вопрос: найдется ли в графе G маршрут, проходящий через все вершины графа G, такой, что его длина не превышает L?

Игры: пятнашки, тетрис, сапер.

 

 

1)что такое глубина рекурсии?

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция вызывает функцию , а функция — функцию . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

2) пример задачи, где используется перебор всех возможных вариантов

3)какой основной прием у динамического решения?

Динамическое программирование полезно, если на разных путях многократно встречаются одни и те же подзадачи; основной технический приём — запоминать решения встречающихся подзадач на случай, если та же подзадача встретится вновь.

4)что такое класс сложности?

Класс сложности — это множество задач распознавания, для решения которых существуют алгоритмы, схожие по вычислительной сложности. Два важных представителя:


1 | 2 | 3 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)