Szybszy dostęp niż przeglądarce!
13 kontakty: Algorytm pseudowielomianowy, Język formalny, Problem decyzyjny (teoria obliczeń), Problem komiwojażera, Problem liczbowy, Problem NP, Problem NP-zupełny, Problem obliczeniowy, Problem optymalizacyjny, Problem plecakowy, Problem silnie NP-zupełny, Problem zbioru niezależnego, Transformacja Turinga.
Algorytm pseudowielomianowy
Algorytm pseudowielomianowy – algorytm, którego złożoność obliczeniowa jest pseudowielomianowa.
Nowy!!: Problem NP-trudny i Algorytm pseudowielomianowy · Zobacz więcej »
Język formalny
Język formalny – podzbiór zbioru wszystkich słów nad skończonym alfabetem.
Nowy!!: Problem NP-trudny i Język formalny · Zobacz więcej »
Problem decyzyjny (teoria obliczeń)
Problem decyzyjny – pytanie sformułowane w systemie formalnym, na które możliwe sątylko odpowiedzi tak i nie.
Nowy!!: Problem NP-trudny i Problem decyzyjny (teoria obliczeń) · Zobacz więcej »
Problem komiwojażera
Rozwiązanie przykładowego problemu komiwojażera: najkrótsząścieżkąprzechodzącąprzez wszystkie czerwone punkty jest czarna pętla. Problem komiwojażera – zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
Nowy!!: Problem NP-trudny i Problem komiwojażera · Zobacz więcej »
Problem liczbowy
Problem liczbowy – taki problem decyzyjny (to nie jest warunek konieczny – może być optymalizacyjny), w którym wielkość liczb występujących w opisie każdej jego instancji nie jest ograniczona wielomianowo przez rozmiar problemu.
Nowy!!: Problem NP-trudny i Problem liczbowy · Zobacz więcej »
Problem NP
LadneraR.E. Ladner, ''On the structure of polynomial time reducibility'', J.ACM, 22, 1975, s. 151–171. Corollary 1.1. http://portal.acm.org/citation.cfm?id.
Nowy!!: Problem NP-trudny i Problem NP · Zobacz więcej »
Problem NP-zupełny
Problem NP-zupełny (NPC) – problem zupełny w klasie NP, ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym.
Nowy!!: Problem NP-trudny i Problem NP-zupełny · Zobacz więcej »
Problem obliczeniowy
Problem obliczeniowy, zadanie obliczeniowe – zadanie, które może być rozwiązane za pomocąkomputera lub innej maszyny liczącej.
Nowy!!: Problem NP-trudny i Problem obliczeniowy · Zobacz więcej »
Problem optymalizacyjny
Problem optymalizacyjny – problem obliczeniowy, którego rozwiązanie polega na znalezieniu największej bądź najmniejszej wartości pewnego parametru problemu, która spełnia określonąwłasność.
Nowy!!: Problem NP-trudny i Problem optymalizacyjny · Zobacz więcej »
Problem plecakowy
Które pudełka powinny być wybrane, aby zmaksymalizować wartość przedmiotów w plecaku i jednocześnie nie zabrać więcej niż 15 kg? Dyskretny problem plecakowy (ang. discrete knapsack problem) – jeden z najczęściej poruszanych problemów optymalizacyjnych.
Nowy!!: Problem NP-trudny i Problem plecakowy · Zobacz więcej »
Problem silnie NP-zupełny
Problem silnie NP-zupełny to taki problem decyzyjny, który nawet przy ograniczeniu maksymalnej wartości występujących w jego opisie liczb pozostaje NP-zupełny.
Nowy!!: Problem NP-trudny i Problem silnie NP-zupełny · Zobacz więcej »
Problem zbioru niezależnego
Problem zbioru niezależnego – przykład problemu NP-zupełnego z teorii grafów.
Nowy!!: Problem NP-trudny i Problem zbioru niezależnego · Zobacz więcej »
Transformacja Turinga
Transformacja Turinga (inaczej redukcja Turinga) – w teorii obliczeń relacja pomiędzy językami A i B. Mówi się, że język A jest turingowsko redukowalny do języka B (A ≤T B) jeżeli istnieje taka maszyna Turinga z wyroczniąB, że w skończonej liczbie kroków rozstrzyga przynależność słowa do A. Jeżeli dla pewnych A, B ⊆ Σ* spełniona jest relacja A ≤T B i B ≤T A to A.
Nowy!!: Problem NP-trudny i Transformacja Turinga · Zobacz więcej »
