TIN 20. Časová a paměťová složitost

Card Set Information

Author:
hrbi
ID:
222964
Filename:
TIN 20. Časová a paměťová složitost
Updated:
2013-06-16 09:06:30
Tags:
tin
Folders:

Description:
mssz 2013
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user hrbi on FreezingBlue Flashcards. What would you like to do?


  1. Složitost algoritmů
    • vychází z Church-Turingovy teze - každý algoritmus je implementovatelný nějakým TS
    • vyjádření požadovaných zdrojů (čas, prostor) jako funkci délky vstupního řetězce
    • dvě třídy problémů:
    • algoritmicky ani částečně rozhodnutelné (funkce algoritmicky nevyčíslitelné)
    • algoritmicky alespoň částečně rozhodnutelné (funkce algoritmicky vyčíslitelné)
    • různé případy analýzy složitosti:
    • složitost nejhoršího případu
    • složitost nejlepšího případu
    • složitost průměrného případu (vážený průměr)
  2. Složitost výpočtů TS
    • časová složitost: počet kroků TS provedený od počátku do konce výpočtu
    • prostorová složitost: počet buněk pásky TS požadovaný pro daný výpočet
    • je-li časová složitost n, pak prostorová složitost není větší než n+1
    • k-páskový DTS (resp. NTS) M přijímá jazyk L v čase TM: N → N, jestliže M přijme (resp. může přijmout) každé w ∈ L v nanejvýš TM(|w|) krocích
    • k-páskový DTS (resp. NTS) M přijímá jazyk L v prostoru SM: N → N, jestliže M přijme (resp. může přijmout) každé w ∈ L při použití nanejvýš SM(|w|) buněk pásky
  3. Asymptotické omezení složitosti
    • vyloučení aditivních a multiplikativních konstant
    • asymptotické horní omezení: O(f(n)) = {g(n) | ∃c > 0 ∃n0 ∈ N: ∀n ≥ n0 ⇒ 0 ≤ g(n) ≤ cf(n)}
    • asymptotické dolní omezení: Ω(f(n)) = {g(n) | ∃c > 0 ∃n0 ∈ N: ∀n ≥ n0 ⇒ 0 ≤ cf(n) ≤ g(n)}
    • asymptotické oboustranné omezení: Θ(f(n)) = {g(n) | ∃c1, c2 > 0 ∃n0 ∈ N: ∀n ≥ n0 ⇒ 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n)}
  4. Třídy složitosti
    • prostředek pro kategorizaci problémů dle jejich složitosti
    • DTime[t(n)] = {L | ∃ k-páskový DTS M: L = L(M) ∧ TM ∈ O(t(n))}
    • NTime[t(n)] = {L | ∃ k-páskový NTS M: L = L(M) ∧ TM ∈ O(t(n))}
    • DSpace[s(n)] = {L | ∃ k-páskový DTS M: L = L(M) ∧ SM ∈ O(t(n))}
    • NSpace[s(n)] = {L | ∃ k-páskový NTS M: L = L(M) ∧ SM ∈ O(t(n))}
  5. Běžně užívané třídy
    • logaritmické:
    • LOGSPACE = ∪DSpace(k log(n))
    • NLOGSPACE = ∪NSpace(k log(n))
    • polynomiální:
    • P = ∪DTime(nk)
    • NP = ∪NTime(nk)
    • PSPACE = ∪DSpace(nk)
    • NPSPACE = ∪NSpace(nk)
    • exponenciální:
    • EXP = ∪DTime(2nk)
    • NEXP = ∪NTime(2nk)
    • EXPSPACE = ∪DSpace(2nk)
    • NEXPSPACE = ∪NSpace(2nk)
    • k-exponenciální (věž exponenciál o výšce k):
    • k-EXP = ∪DTime(22...2nl)
    • k-NEXP = ∪NTime(22...2nl)
    • k-EXPSPACE = ∪DSpace(22...2nl)
    • k-NEXPSPACE = ∪NSpace(22...2nl)
    • elementární:
    • ELEMENTARY = ∪k-EXP
  6. Vlastnosti tříd složitosti
    • k-páskový DTS v čase t(n) → 1-páskový DTS v čase O(t(n)2)
    • NTS v čase t(n) → DTS v čase 2O(t(n))
    • NSpace[s(n)] ⊆ DSpace[s2(n)]
    • PSPACE = NPSPACE
    • k-EXPSPACE = k-NEXPSPACE
  7. Doplněk třídy
    • třída jazyků, které jsou doplňkem jazyků dané třídy
    • L ∈ C ⇔ L ∈ co-C
    • prostorové třídy jsou obvykle uzavřeny vůči doplňku, časové spíše ne (co-NP, co-NEXP)
  8. Redukovatelnost
    • R je třída funkcí
    • jazyk L1 ⊆ Σ1* je redukovatelný na jazyk L2 ⊆ Σ2*, jestliže existuje f ∈ R taková, že w ∈ L1 ⇔ f(w) ∈ L2
    • L1Rm L2
  9. Polynomiální redukce
    • jazyka L1 ⊆ Σ1* na jazyk L2 ⊆ Σ2* je funkce f: Σ1* → Σ2* taková, že:
    • 1. ∀w ∈ L1 ⇔ f(w) ∈ L2
    • L1R
    • 2. f je Turingovsky vyčíslitelná v polynomiálním čase
    • značíme L1Pm L2
  10. Jazyky C-těžké a C-úplné
    • R je třída funkcí, C třída jazyků
    • L0 je C-těžký vzhledem k R redukovatelnosti, jestliže ∀L ∈ C: L ≤Rm L0
    • L0 je C-úplný vzhledem k R redukovatelnosti, jestliže L0 ∈ C a L0 je C-těžký
    • příklady:
    • NP, PSPACE, EXP úplnost vůči polynomiální redukovatelnosti
    • P, NLOGSPACE úplnost vůči redukovatelnosti v deterministickém logaritmickém prostoru
    • NEXP úplnost vůči exponenciální redukovatelnosti
  11. Příklady problémů
    • LOGSPACE: existence cesty mezi dvěma uzly v neorientovaném grafu
    • NLOGSPACE: existence cesty mezi dvěma uzly v orientovaném grafu, 2-SAT
    • P-úplný: splnitelnost Hornových klauzulí, náležitost řetězce do jazyka BKG
    • NP-úplný: 3-SAT, SAT, existence kliky dané velikosti, existence Hamiltonovské kružnice, barvitelnost, obchodní cestující, knapsack
    • co-NP-úplný: ekvivalence RV bez iterace
    • PSPACE-úplný: ekvivalence RV, náležitost řetězce do jazyka KG, nejlepší tah v Sokobanu
    • EXP-úplný: nejlepší tah v šachu
    • EXPSPACE-úplný: ekvivalence RV s kvadrátem
    • mimo ELEMENTARY: ekvivalence RV s negací
  12. SAT problém
    • V = {v1, v2, ..., vn} je konečná množina Booleovských proměnných
    • literál: proměnná vi nebo její negace vi
    • klausule: výroková formule obsahující literály spojené spojkou ∨ (nebo)
    • SAT-problém: je dána množina proměnných V a množina klausulí nad V, je tato množina klausulí splnitelná
    • NP-úplný problém

What would you like to do?

Home > Flashcards > Print Preview