Схема на раздела

◄17 април - 23 април
►1 май - 7 май

  • 16.04.2006. Търсене с връщане назад. NP ( NP PNPNP[1]

    Пример: Да се провери дали дадено естествено число има делител.

    1.5. NP NP NP задачи, които са поне толкова трудни, колкото всяка друга задача в NP. NP трудна, ако всяка проверяваща задача в NP NP задача е сводима към NP NP P. Една NP NP пълна, когато всяка друга NP NPNP

    Забележка: Не всяка NP NP пълна: напр. stop NP-труден, но не е NP

    1.5. Stop проблем. Разпознаване дали две различни програми смятат една и съща функция.

    2. Търсене с връщане. Примери

    Удовлетворимост на булева функция. Оцветяване на Граф. (*)Най-дълъг прост път в цикличен граф. Разходка на коня (не е NP

    3.1. [2]

    3.2. (*)Ограничено Алфа-Бета отсичане.

    [1] http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP

    [2] http://en.wikipedia.org/wiki/Alpha-beta_pruning

◄17 април - 23 април
►1 май - 7 май