Teória vypočítateľnosti a zložitosti; EWSTranslate
Druhé vydanie
Springer Verlag, New York, 2011
ISBN 978-1461406815
Toto prepracované a rozšírené vydanie teórie vypočítateľnosti a zložitosti obsahuje základné materiály, ktoré predstavujú základné poznatky z výpočtovej teórie. Kniha je autonómna a jej úvodná kapitola popisuje kľúčové matematické pojmy a notácie a nasledujúce kapitoly, ktoré prechádzajú od kvalitatívnych aspektov klasickej výpočtovej teórie ku kvantitatívnym aspektom teórie zložitosti. Prvé vydanie, ktoré sa zameriava na obmedzenia vyčísliteľnosti a rozdiely medzi uskutočniteľnými a nevyriešenými, završujú špeciálne tituly o nedeklarovateľnosti, úplnosti NP a relatívnej vypočítateľnosti.
Zásadne nový obsah v tomto druhom vydaní obsahuje:
* kapitola o nejednotnosti, ktorá študuje booleovské okruhy, kurzy poradenstva a dôležitý výsledok Karp-Liptona
* definície a vlastnosti tried základnej pravdepodobnostnej zložitosti
* štúdia striedavého Turingovho stroja a tried uniformných obvodov
* úvod do počítania tried, vrátane výsledkov Valiant a Vazirani a Toda
* dôkladné ošetrenie dokladu, že IP je totožné s PSPACE
Témy a funkcie:
* Stručné a zamerané materiály pokrývajú najzákladnejšie koncepty a výsledky v oblasti modernej teórie zložitosti vrátane teórie úplnosti NP, tvrdosti NP, hierarchie polynómov a úplných problémov pre ďalšie triedy zložitosti.
* Obsahuje informácie, ktoré inak existujú iba v literatúre a prezentujú ich jednotným a zjednodušeným spôsobom; napríklad o komplexoch tried zložitosti, problémoch vyhľadávania a prechodných úlohách v NP, nejednotnej a paralelnej teórii zložitosti, pravdepodobnostných triedach zložitosti, počítacích triedach a interaktívnych dôkazových systémoch.
* Poskytuje základné matematické základné informácie vrátane častí o logike a teórii čísel a algebre
* Podporené mnohými cvičeniami a ďalšími problémami pri posilňovaní a samoštúdiu
Vďaka dostupnosti a dobre navrhnutej organizácii je tento text/odkaz vynikajúcim zdrojom a sprievodcom pre tých, ktorí chcú vytvoriť pevný základ v počítačovej teórii. Absolventi začiatočníci, pokročilí študenti a odborníci zaoberajúci sa teóriou počítačov, teóriou zložitosti a výpočtami nájdu knihu ako základný a praktický učebný nástroj.