
EITC/IS/CCTF Computational Complexity Theory Fundamentals je evropský certifikační program IT zaměřený na teoretické aspekty základů informatiky, které jsou také základem klasické asymetrické kryptografie s veřejným klíčem hojně používané na internetu.
Učební plán EITC/IS/CCTF Základy teorie výpočetní složitosti pokrývá teoretické znalosti o základech informatiky a výpočetních modelů na základních pojmech, jako jsou deterministické a nedeterministické konečné automaty, regulární jazyky, bezkontextová gramatika a teorie jazyků, teorie automatů, Turing Stroje, rozhoditelnost problémů, rekurze, logika a složitost algoritmů pro základní bezpečnostní aplikace v rámci následující struktury, zahrnující komplexní a strukturované samovzdělávací materiály pro certifikaci EITCI podporované odkazovaným didaktickým videoobsahem s otevřeným přístupem jako základ pro přípravu na získání této certifikace EITC složením příslušné zkoušky.
Výpočetní složitost algoritmu je množství zdrojů potřebných k jeho provozu. Zvláštní pozornost je věnována zdrojům času a paměti. Složitost problému je definována jako složitost nejlepších algoritmů pro jeho řešení. Analýza algoritmů je studiem složitosti explicitně daných algoritmů, zatímco teorie výpočetní složitosti je studiem složitosti řešení problémů pomocí nejznámějších algoritmů. Obě domény se prolínají, protože složitost algoritmu je vždy horním omezením složitosti problému, který řeší. Navíc je často nutné porovnávat složitost určitého algoritmu se složitostí řešeného problému při konstrukci efektivních algoritmů. Ve většině případů je jedinou dostupnou informací o obtížnosti problému, že je menší než složitost nejúčinnějších známých technik. V důsledku toho dochází k velkému překrývání mezi analýzou algoritmů a teorií složitosti.
Teorie komplexity hraje důležitou roli nejen v základech výpočtových modelů jako základu pro informatiku, ale také v základech klasické asymetrické kryptografie (tzv. kryptografie veřejného klíče), která je široce rozšířena v moderních sítích, zejména v Internetu. Šifrování veřejným klíčem je založeno na výpočetní obtížnosti určitých asymetrických matematických problémů, jako je například faktorizace velkých čísel na prvočinitele (tato operace je těžkým problémem v klasifikaci teorie složitosti, protože nejsou známy účinné klasické algoritmy k řešení to se zdroji, které se polynomiálně škálují spíše než exponenciálně s nárůstem vstupní velikosti problému, což je v kontrastu s velmi jednoduchou zpětnou operací násobení známými prvočiniteli, aby se získal původní velký počet). Pomocí této asymetrie v architektuře kryptografie veřejného klíče (definováním výpočetně asymetrického vztahu mezi veřejným klíčem, který lze snadno vypočítat ze soukromého klíče, zatímco soukromý klíč nelze snadno počítačově z veřejného klíče, lze veřejně oznámit veřejný klíč a umožnit ostatním komunikačním stranám jeho použití pro asymetrické šifrování dat, která pak lze dešifrovat pouze spřaženým soukromým klíčem, který není výpočetně dostupný třetím stranám, čímž je komunikace bezpečná).
Teorie výpočetní složitosti byla vyvinuta hlavně na úspěších průkopníků počítačové vědy a algoritmů, jako je Alan Turing, jehož práce byla kritická pro prolomení šifry Enigma nacistického Německa, která hrála významnou roli ve vítězství spojenců ve druhé světové válce. Kryptoanalýza zaměřená na navržení a automatizaci výpočetních procesů analýzy dat (zejména šifrované komunikace) za účelem odhalení skrytých informací byla použita k prolomení kryptografických systémů a získání přístupu k obsahu šifrované komunikace, obvykle strategického vojenského významu. Byla to také kryptoanalýza, která katalyzovala vývoj prvních moderních počítačů (které byly zpočátku aplikovány na strategický cíl kódování). Britskému kolosu (považovanému za první moderní elektronický a programový počítač) předcházela polská „bomba“, elektronické výpočetní zařízení navržené Marianem Rejewskim na pomoc při prolamování šifer Enigmy a předané Velké Británii polskou rozvědkou spolu s ukořistěný německý šifrovací stroj Enigma po napadení Polska Německem v roce 1939. Na základě tohoto zařízení Alan Turing vyvinul jeho pokročilejší protějšek k úspěšnému prolomení německé šifrované komunikace, která byla později vyvinuta do moderních počítačů.
Protože množství zdrojů potřebných ke spuštění algoritmu se mění s velikostí vstupu, složitost se obvykle vyjadřuje jako funkce f(n), kde n je velikost vstupu a f(n) je buď nejhorší případ složitosti ( maximální množství zdrojů požadovaných napříč všemi vstupy velikosti n) nebo průměrná složitost případu (průměr množství zdrojů na všech vstupech velikosti n). Počet požadovaných elementárních operací na vstupu o velikosti n se běžně uvádí jako časová složitost, kde se předpokládá, že elementární operace zabírají na konkrétním počítači konstantní množství času a mění se pouze konstantním faktorem, když jsou spuštěny na jiném stroji. Množství paměti požadované algoritmem na vstupu o velikosti n je známé jako prostorová složitost.
Čas je nejčastěji považovaný za zdroj. Když je termín „složitost“ použit bez kvalifikátoru, obvykle se vztahuje na složitost času.
Tradiční jednotky času (sekundy, minuty atd.) se v teorii složitosti nepoužívají, protože jsou příliš závislé na zvoleném počítači a technologickém pokroku. Počítač dnes může například provádět algoritmus podstatně rychleji než počítač ze 1960. let, ale je to způsobeno spíše technologickými průlomy v počítačovém hardwaru než vlastní kvalitou algoritmu. Cílem teorie složitosti je kvantifikovat inherentní časové potřeby algoritmů nebo základní časová omezení, která by algoritmus uvalil na jakýkoli počítač. Toho je dosaženo počítáním, kolik základních operací bylo provedeno během výpočtu. Tyto procedury se běžně označují jako kroky, protože se má za to, že zabírají konstantní čas na konkrétním stroji (tj. nejsou ovlivněny množstvím vstupu).
Dalším důležitým zdrojem je množství paměti počítače potřebné k provádění algoritmů.
Dalším často používaným zdrojem je množství aritmetických operací. V tomto scénáři se používá termín „aritmetická složitost“. Časová složitost je obecně součinem aritmetické složitosti konstantním faktorem, pokud je známo horní omezení velikosti binární reprezentace čísel, která se vyskytují během výpočtu.
Velikost celých čísel používaných během výpočtu není u mnoha metod omezena a je nerealistické předpokládat, že aritmetické operace vyžadují pevné množství času. V důsledku toho může být časová složitost, známá také jako bitová složitost, výrazně vyšší než aritmetická složitost. Aritmetická obtížnost výpočtu determinantu celočíselné matice nn je například O(n^3) pro standardní techniky (Gaussova eliminace). Protože se velikost koeficientů může během výpočtu exponenciálně rozšiřovat, bitová složitost stejných metod je v n exponenciální. Pokud jsou tyto techniky použity ve spojení s multimodulární aritmetikou, lze bitovou složitost snížit na O(n^4).
Bitová složitost, ve formálních termínech, odkazuje na počet operací na bitech potřebných ke spuštění algoritmu. Ve většině výpočetních paradigmat se rovná časové složitosti až do konstantního faktoru. Počet operací na strojových slovech požadovaných počítači je úměrný bitové složitosti. Pro realistické modely výpočtu jsou tedy časová a bitová složitost totožné.
Zdroj, který je často zvažován při třídění a vyhledávání, je množství porovnávání záznamů. Pokud jsou data dobře uspořádána, je to dobrý ukazatel časové náročnosti.
Na všech potenciálních vstupech je nemožné počítat počet kroků v algoritmu. Protože složitost vstupu roste s jeho velikostí, je běžně reprezentován jako funkce velikosti vstupu n (v bitech), a tak je složitost funkcí n. Pro stejně velké vstupy se však složitost algoritmu může podstatně lišit. V důsledku toho se rutinně používá celá řada funkcí složitosti.
Složitost nejhoršího případu je součet veškeré složitosti pro všechny vstupy velikosti n, zatímco složitost průměrného případu je součtem veškeré složitosti všech vstupů velikosti n (to dává smysl, protože počet možných vstupů dané velikosti je konečný). Je-li použit termín „složitost“, aniž by byl dále definován, bere se v úvahu nejhorší případ časové složitosti.
Složitost nejhoršího a průměrného případu je notoricky obtížné správně vypočítat. Navíc tyto přesné hodnoty mají jen malou praktickou aplikaci, protože jakákoli změna ve strojovém nebo výpočetním paradigmatu by mírně změnila složitost. Navíc využití zdrojů není důležité pro malé hodnoty n, proto je snadnost implementace často přitažlivější než nízká složitost pro malé n.
Z těchto důvodů je největší pozornost věnována chování složitosti pro vysoké n, tedy jejímu asymptotickému chování, když se n blíží nekonečnu. V důsledku toho se k označení složitosti běžně používá velká notace O.
Výpočtové modely
Pro stanovení složitosti je důležitý výběr výpočetního modelu, který spočívá ve specifikaci podstatných operací, které se provádějí za jednotku času. To je někdy označováno jako multipáskový Turingův stroj, když není konkrétně popsáno výpočetní paradigma.
Deterministický model výpočtu je model, ve kterém jsou následující stavy stroje a operace, které mají být provedeny, zcela definovány předchozím stavem. Rekurzivní funkce, lambda počet a Turingovy stroje byly prvními deterministickými modely. Stroje s náhodným přístupem (také známé jako RAM-stroje) jsou oblíbeným vzorem pro simulaci reálných počítačů.
Když výpočetní model není definován, obvykle se předpokládá vícepáskový Turingův stroj. Na vícepáskových Turingových strojích je časová složitost stejná jako na strojích RAM pro většinu algoritmů, i když k dosažení této ekvivalence může být zapotřebí značná pozornost v tom, jak jsou data uložena v paměti.
V některých krocích výpočtu v nedeterministickém modelu práce na počítači, jako jsou nedeterministické Turingovy stroje, lze provést různé volby. V teorii složitosti jsou všechny proveditelné možnosti zvažovány současně a nedeterministická časová složitost je množství času potřebného, když jsou vždy učiněny nejlepší volby. Jinak řečeno, výpočet se provádí souběžně na tolika (identických) procesorech, kolik je potřeba, a nedeterministický výpočetní čas je čas, který první procesor potřebuje k dokončení výpočtu. Tento paralelismus lze použít v kvantovém počítání pomocí superponovaných zapletených stavů při spouštění specializovaných kvantových algoritmů, jako je například Shorova faktorizace malých celých čísel.
I když takový výpočetní model není v současné době proveditelný, má teoretický význam, zejména ve vztahu k problému P = NP, který se ptá, zda třídy složitosti vytvořené použitím „polynomiálního času“ a „nedeterministického polynomiálního času“ jsou nejméně horní. hranice jsou stejné. Na deterministickém počítači vyžaduje simulace NP-algoritmu „exponenciální čas“. Pokud lze úlohu vyřešit v polynomiálním čase na nedeterministickém systému, patří do třídy obtížnosti NP. Pokud je problém v NP a není jednodušší než jakýkoli jiný problém NP, říká se, že je NP-úplný. Problém batohu, problém cestujícího obchodníka a booleovský problém splnitelnosti jsou všechny NP-úplné kombinatorické problémy. Nejznámější algoritmus má exponenciální složitost pro všechny tyto problémy. Pokud by některý z těchto problémů mohl být vyřešen v polynomiálním čase na deterministickém stroji, pak by všechny NP problémy mohly být vyřešeny také v polynomiálním čase a bylo by stanoveno P = NP. Od roku 2017 se obecně předpokládá, že P NP, z čehož vyplývá, že nejhorší situace problémů NP se zásadně obtížně řeší, tj. trvají mnohem déle, než je jakékoli možné časové rozpětí (desítky let) při zajímavé délce vstupu.
Paralelní a distribuované výpočty
Paralelní a distribuované výpočty zahrnují rozdělení zpracování mezi více procesorů, které všechny pracují současně. Základním rozdílem mezi různými modely je způsob zasílání dat mezi procesory. Přenos dat mezi procesory je typicky velmi rychlý při paralelním počítání, zatímco přenos dat mezi procesory při distribuovaných počítáních probíhá po síti a je tedy podstatně pomalejší.
Výpočet na N procesorech zabere alespoň podíl N času, který zabere jeden procesor. Ve skutečnosti, protože některé dílčí úlohy nelze paralelizovat a některé procesory mohou muset čekat na výsledek od jiného procesoru, nebude této teoreticky ideální hranice nikdy dosaženo.
Klíčovým problémem složitosti je tedy vývoj algoritmů tak, aby součin výpočetního času počtem procesorů byl co nejblíže času potřebnému k provedení stejného výpočtu na jediném procesoru.
Kvantový výpočet
Kvantový počítač je počítač s výpočetním modelem založeným na kvantové mechanice. Churchova-Turingova teze platí pro kvantové počítače, z čehož vyplývá, že jakýkoli problém, který může kvantový počítač vyřešit, může být vyřešen také Turingovým strojem. Některé úlohy by však teoreticky mohly být řešeny spíše pomocí kvantového počítače než klasického počítače s výrazně nižší časovou složitostí. To je zatím přísně teoretické, protože nikdo neví, jak vyvinout praktický kvantový počítač.
Teorie kvantové složitosti byla vytvořena, aby prozkoumala různé typy problémů, které lze vyřešit pomocí kvantových počítačů. Využívá se v postkvantové kryptografii, což je proces vytváření kryptografických protokolů, které jsou odolné vůči útokům kvantových počítačů.
Složitost problému (spodní hranice)
Infimum složitosti algoritmů, které mohou problém vyřešit, včetně neobjevených technik, je složitost problému. V důsledku toho se složitost problému rovná složitosti jakéhokoli algoritmu, který jej řeší.
V důsledku toho jakákoli složitost uvedená ve velkém O znamená složitost jak algoritmu, tak doprovodného problému.
Na druhou stranu je často obtížné získat netriviální dolní meze složitosti problému a existuje jen málo strategií, jak toho dosáhnout.
Aby se vyřešila většina problémů, musí být načtena všechna vstupní data, což zabere čas úměrný velikosti dat. Výsledkem je, že takové problémy mají alespoň lineární složitost, nebo ve velké omega notaci složitost Ω(n).
Některé problémy, jako jsou problémy v počítačové algebře a výpočetní algebraické geometrii, mají velmi rozsáhlá řešení. Protože výstup musí být zapsán, je složitost omezena maximální velikostí výstupu.
Počet porovnání požadovaných pro třídicí algoritmus má nelineární dolní mez Ω(nlogn). V důsledku toho jsou nejlepší třídicí algoritmy nejúčinnější, protože jejich složitost je O(nlogn). Skutečnost, že existuje n! způsoby, jak organizovat n věcí, vedou k této spodní hranici. Protože každé srovnání rozděluje tuto sbírku n! objednávky na dva kusy, počet N porovnání potřebných k rozlišení všech objednávek musí být 2N > n!, což znamená O(nlogn) podle Stirlingova vzorce.
Snížení problému na jiný problém je běžnou strategií pro získání omezení složitosti.
Algoritmový vývoj
Vyhodnocení složitosti algoritmu je důležitým prvkem procesu návrhu, protože poskytuje užitečné informace o výkonu, který lze očekávat.
Je častým nedorozuměním, že v důsledku Moorova zákona, který předpovídá exponenciální růst výkonu moderního počítače, bude hodnocení složitosti algoritmů méně relevantní. To je nesprávné, protože zvýšený výkon umožňuje zpracování velkého množství dat (velká data). Například jakýkoli algoritmus by měl fungovat dobře za méně než sekundu při abecedním řazení seznamu několika stovek záznamů, jako je bibliografie knihy. Na druhou stranu, pro milion záznamů (například telefonní čísla velkého města) by základní algoritmy, které vyžadují porovnání O(n2), musely provést bilion porovnání, což by při rychlosti 10 zabralo tři hodiny. milionů srovnání za sekundu. Quicksort a merge sort na druhé straně vyžadují pouze porovnání nlogn (jako složitost průměrného případu pro první případ, jako složitost nejhoršího případu pro druhý). To vytváří přibližně 30,000,000 1,000,000 3 srovnání pro n = 10 XNUMX XNUMX, což by při XNUMX milionech srovnání za sekundu trvalo pouze XNUMX sekundy.
V důsledku toho může posouzení složitosti umožnit eliminaci mnoha neefektivních algoritmů před implementací. To lze také použít k doladění složitých algoritmů, aniž byste museli testovat všechny možné varianty. Studium složitosti umožňuje zaměřit úsilí na zvýšení efektivity implementace stanovením nejnákladnějších kroků složitého algoritmu.
Chcete-li se podrobně seznámit s certifikačním kurikulem, můžete rozšířit a analyzovat níže uvedenou tabulku.
Certifikační kurikulum EITC/IS/CCTF Základy teorie výpočetní složitosti odkazuje na didaktické materiály s otevřeným přístupem ve formě videa. Učební proces je rozdělen do struktury krok za krokem (programy -> lekce -> témata) pokrývající příslušné části kurikula. Účastníci mohou získat přístup k odpovědím a klást relevantnější otázky v sekci Otázky a odpovědi e-learningového rozhraní v rámci aktuálně probíhajícího tématu kurikula programu EITC. Přímé a neomezené poradenství s doménovými odborníky je také dostupné prostřednictvím integrovaného systému online zasílání zpráv platformy a také prostřednictvím kontaktního formuláře.
Podrobnosti o kontrole certifikačního postupu Jak to funguje.
Primární podpůrné studijní materiály ke čtení
S. Arora, B. Barak, Computational Complexity: A Modern Approach
https://theory.cs.princeton.edu/complexity/book.pdf
Sekundární podpůrné studijní materiály ke čtení
O. Goldreich, Úvod do teorie složitosti:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Podpůrné učební materiály ke čtení diskrétní matematiky
J. Aspnes, Poznámky k diskrétní matematice:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Podpůrné učební materiály ke čtení o teorii grafů
R. Diestel, Teorie grafů:
https://diestel-graph-theory.com/
Stáhněte si kompletní offline samoučící se přípravné materiály pro program EITC/IS/CCTF Computational Complexity Theory Fundamentals v souboru PDF
Přípravné materiály EITC/IS/CCTF – standardní verze
Přípravné materiály EITC/IS/CCTF – rozšířená verze o recenzní otázky