|
|
|
Polski Serwis Naukowy - OnLine od 1999 roku
 RSS
Dodaj do:
Warto przeczytać: Problem uodparniania się bakterii na działanie antybiotyków jest bagatelizowany. Zanim opracowane zostaną nowe antybiotyki, może minąć wiele lat - oceniła w rozmowie z PAP prof. Waleria Hryniewicz, przewodnicząca Narodowego Programu Ochrony Antybiotyków (NPOA).18 ... Pod hasłem "Gdzie jest matematyka?" rozpocznie się 26 listopada w Ośrodku Szkoleniowo-Wypoczynkowym w Soczewce koło Płocka trzydniowa konferencja zorganizowana przez Stowarzyszenie na rzecz Edukacji Matematycznej, Instytut Matematyki Un... Czy myśleliście kiedyś o posiadaniu trzeciej ręki? Szwedzcy badacze odkryli sposób przekonania ludzi, że posiadają dodatkową kończynę. W kontrolowanych warunkach laboratoryjnych naukowcom udało się zmylić uczestników, tak aby uwierzyli, że proteza ręk... Z biotechnologiami zetknęliśmy się wszyscy. Najpopularniejszym biofarmaceutykiem jest dowolna szczepionka. Są nimi także np. insuliny. Ostatnio przybywa leków biotechnologicznych, powstających po wygaśnięciu patentów na leki wytworzone p... [i]Rozmowa z endokrynologiem dziecięcym,
prof. dr n. med. Tomaszem Romerem [/i]
prof. dr hab. n. med. Tomasz Romer[size=9]Wybitny specjalista w dziedzinie endokrynologii; założyciel i członek Zespołu Koordynacyjnego ds. Sto...
Ostatnio na Forum:
Dyskusje
8
odp.
4
odp. Reklama:
 Problem spełnialnościCzy wiesz że...? Koniunkcyjna postać normalna (ang. conjunctive normal form, CNF) danej formuły logicznej to równoważna jej formuła zapisana w postaci koniunkcji klauzul. Rachunek zdań to dział logiki matematycznej badający związki między zdaniami (zmiennymi zdaniowymi) lub funkcjami zdaniowymi utworzonymi za pomocą spójników zdaniowych ze zdań lub funkcji zdaniowych prostszych. Rachunek zdań określa sposoby stosowania spójników zdaniowych w poprawnym wnioskowaniu. Problem spełnialności to pytanie rachunku zdań - czy dla danej formuły logicznej istnieje takie podstawienie (wartościowanie) zmiennych zdaniowych, żeby formuła była prawdziwa. Jest równoważne negacji odpowiedzi na pytanie czy "negacja tej formuły jest tautologią". Problem spełnialności jest rozstrzygalny - można wypróbować wszystkich podstawień których jest Determinizm (łac. determinare — oddzielić, ograniczyć, określić) — koncepcja filozoficzna, według której wszystkie zdarzenia mają zawsze swoją przyczynę, a zatem znając stan wszechświata w danym momencie można teoretycznie przewidzieć wszystkie przyszłe wydarzenia i nie ma tu miejsca na przypadkowość czy działanie wolnej woli.
Rozstrzygalność (decydowalność) problemu matematycznego to następująca jego właściwość: zawsze można określić czy dana odpowiedź na pytanie stawiane przez problem jest poprawna. Szczególnie ciekawy jest problem spełnialności formuł w koniunkcyjnej postaci normalnej (ang. CNF - conjunctional normal form), których klauzule mają nie więcej niż k literałów (k-SAT). Literałem nazywamy zmienną lub zmienną zanegowaną, klauzulą nazywamy alternatywę literałów, natomiast formuła to koniunkcja klauzul. 1-SAT i 2-SAT mają rozwiązania w P, czyli w deterministycznym czasie wielomianowym, natomiast już 3-SAT jest NP-zupełny, czyli takim, że każdy problem z klasy NP jest do niego redukowalny przy pomocy redukcji w czasie wielomianowym. Problem P (ang. deterministic polynomial - deterministycznie wielomianowy) to problem decyzyjny, dla którego rozwiązanie można znaleźć w czasie wielomianowym.
Klauzula (ang. clause) to zbiór literałów, który jest prawdziwy wtedy i tylko wtedy, gdy ich alternatywa jest prawdziwa. Klauzula pusta jest zawsze fałszywa.
Czy wiesz że...? beta Zmienna zdaniowa - bezargumentowy symbol w rachunku zdań. Zmiennym zdaniowym w procesie zwanym wartościowaniem przyporządkowywane są wartości prawda lub fałsz.
Tautologia (wywodzi się od greckich słów ταυτος – ten sam i λογος – mowa) – wyrażenie, które jest prawdziwe na mocy swojej formy - budowy (dokładniej: które jest prawdziwe w każdej niepustej dziedzinie; zdanie zawsze prawdziwe). W logicznym znaczeniu zostało użyte po raz pierwszy przez Ludwika Wittgensteina (Tractatus logico-philosophicus 1922).
Problem NP-zupełny (NPC) czyli 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. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym. Taka definicja problemów NP-zupełnych implikuje fakt, że jeśli tylko potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w czasie wielomianowym wszystkie problemy NP. Problemy NP-zupełne można więc traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności). Powyższa treść oraz zamieszczone w niej powiązane definicje/pojęcia - udostępniane są na licencji Creative Commons: uznanie autorstwa, na tych samych warunkach, z możliwością obowiązywania dodatkowych ograniczeń.
Zobacz szczegółowe informacje o warunkach korzystania
Wszystkie hasła znajdujące się w naszym mirrorze Wikipedii mają znaczenie informacyjne i edukacyjne. Nie mogą być traktowane jako porady. |
, gdzie 
to liczba zmiennych w formule. Metoda ta ma więc złożoność wykładniczą.