Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
SPISTREŚCI
Wstęp
1.
ZADANIE,ALGORYTM,REPREZENTACJAALGORYTMU
5
7
1.1.
ZADANIE,DANE,ALGORYTMłłł
łłł
łł...
...
...
...
...
...
...
...
...
...
...
...
...
7
1.1.1.Zadanie,informacjaodanychłłł
łłł
łłł
łłł
łłł
łłł
ł...
7
1.1.2.Wybranewłasnościicharakterystykioperatorainformacjiłłł
łłł
ł...
..
11
1.1.3.Algorytm,dokładnośćalgorytmu,rodzajealgorytmówłłł
łłł
łłł...
15
1.2.
REPREZENTACJAALGORYTMUłłł
łłł
łłł
łłł
łłł
ł...
.
22
1.2.1.Iteracjałłł
łłł
łłł
łłł
łłł
łłł
łłł
łłł
łłł
ł..
22
1.2.2.Rekurencja,zależnościrekurencyjnełłł
łłł
łłł
łłł
łłł
ł...
.
24
1.2.3.Indukcja,zasadyindukcjimatematycznejłłł
łłł
łłł
łł...
...
...
...
...
.
25
1.2.4.Poprawnośćalgorytmu,poprawnośćprogramułłł
łłł
łłł
łłł...
27
2.
30
2.1.RODZAJEPROBLEMÓWłłł
łłł
łłł
łłł
łłł
łłł
łł...
.
31
2.2.KODOWANIEDANYCHPROBLEMÓWDECYZYJNYCHłłł
łłł...
..
34
2.3.MODELEOBLICZEŃłłł
łłł
łłł
łłł
łłł
łłł
łłł
ł...
35
2.3.1.Wprowadzeniełłł
łłł
łłł
łłł
łłł
łłł
łłł
łłł
ł..
35
2.3.2.Deterministyczna,jednotaśmowamaszynaTuringa(DTM)łłł
łłł
ł...
.
37
2.3.3.Złożonośćczasowaalgorytmówiproblemówłłł
łłł
łłł
łłł
ł.
41
2.3.4.Deterministyczna,wielotaśmowamaszynaTuringa(k-DTM)łłł
łłł...
.
43
2.3.5.NiedeterministycznamaszynaTuringa(NDTM)łłł
łłł
łłł
łłł.
44
2.3.6.ProbabilistycznamaszynaTuringa(PMT)łłł
łłł
łłł
łłł
łł...
45
2.3.7.KwantowamaszynaTuringa(QTM-QuantumTuringMachine)łłł
łł..
48
2.3.8.Modeleobliczeńniejednostajnychłłł
łłł
łłł
łłł
łłł
łł...
48
2.3.8.1.Obwodylogiczne
48
2.3.8.2.Bramkiiobwodyodwracalne
49
MODELEOBLICZEŃ.MASZYNYOBLICZAJĄCE
3.
ZŁOŻONOŚĆOBLICZENIOWA.HIERARCHIEZŁOŻONOŚCI
51
51
3.1.TRANSFORMACJEPROBLEMÓW,KLASYFIKACJEPROBLEMÓW,
HIERARCHIEZŁOŻONOŚCIłłł
łłł
łłł
łłł
łłł
łłł
ł..
3.1.1.Transformacjeproblemówdecyzyjnychłłł
łłł
łłł
łłł
łłł..
3.1.2.Klasyfikacjeproblemówłłł
łłł
łłł
łłł
łłł
łłł
łłł..
3.1.2.1.KlasyPiNP.
3.1.2.2.ProblemyNP-zupełne.TechnikidowodzeniaNP-zupełności
3.1.2.3.SilnaNP-zupełność
3.1.3.Rozwinięcieklasyfikacjiproblemów.Hierarchiezłożonościłłł
łłł
ł.
3.1.3.1.Problemykomplementarne.Klasaco-NP.
3.1.3.2.Złożonośćpamięciowa.ProblemyPSPACE
52
55
56
58
61
64
64
66
