Test prvočíselnosti
Přihlásit se
Test prvočíselnosti (2/9) · 5:04

Co je to počítač? Dříve, než se začneme zabývat efektivitou algoritmu, musíme pochopit, jak definovat rychlost algoritmu (časovou náročnost) podle počtu primitivních kroků.

Navazuje na Moderní šifrování.
Nejdříve se ohlédneme zpět, a zamyslíme se nad tím, co znamená, když se řekne "vytvoříme efektivnější algoritmus" Musíme myslet abstraktně, neboli nezajímá nás, zda algoritmus na našem stroji stále běží -- a to ať už jsme ho napsali, aby běžel na tomto malém starém Nintendu, nebo na ENIACu, což je mnohem pomalejší. Na obou těchto počítačích je náš algoritmus schopen běžet. My už se ale daným strojem zabývat nechceme. Co chceme, je zaměřit se na dvě věci. Musíme pochopit, co máme na mysli, když se řekne "prostor", jaký je prostor, který náš algoritmus potřebuje, a čas, jak dlouho trvá vyřešit problém. Tyto dva koncepty musíme nutně pochopit. Takže nyní vás chci přesvědčit o tom, že počítač je ekvivalent k tomu, co dokážete pomocí tužky, velké zásoby papíru a velmi jednoduché kalkulačky. Moderní počítač je velmi podobný právě tomuto. Místo papíru ale využívá digitální paměť, a má centrální procesorovou jednotku (CPU), která obsahuje něco zvané "ALU", to vysvětlím dále, což je její kalkulačka. A řekněme, že tento kalkulačka provádí operace miliardu krát za sekundu a v podstatě běží ve velmi základních krocích. A to je celá záhada počítače. Žádné kouzlo. Pojďme teď probrat čas, nebo také rychlost, za kterou provedeme daný algoritmus. Pro tohle potřebujeme abstraktní jednotku, protože každý počítač běží jinak rychle, jak jistě víte. Pamatujte si, že počítač čte z nějakého seznamu velmi základních instrukcí. A současně má přístup k velice primitivní kalkulačce, kterou lze použít, a ta se nazývá ALU. ALU je uvnitř CPU. ALU je aritmetická a logická jednotka. Může vykonat velmi základní operace jako například sčítání, nebo odčítání, pokud to umí. Také může vykonat základní logické operace jako jsou "A" a "NEBO" (AND, OR). ALU je tedy maličká kalkulačka, ke které má počítač přístup, a která dává odpovědi na velmi jednoduché dotazy. To je vše, co tato kalkulačka dokáže. Tady je seznam sady instrukcí pro názornou ukázku, Jde o mikroprocesor, ale vztahuje se to k čemukoliv. V levém sloupci vidíme 'ADDWF', a popis nám říká, co operace dělá. Vezme to "f" a "d" a přidá to "W" do "f". A tady je "DECF", což dekrementuje "f", tedy odečte 1 od "f". Nebo "MOVF", který přesune 'f' do nového umístění. A nyní nejdůležitější sloupec "Cykly". Všimněte si, že všechny tyto primitivní operace zaberou 1 až 2 cykly. Jinak řečeno, všechny tyto operace zaberou stejné množství času, takže se nikdy nezastaví nebo se nebudou opakovat pořád dokola. Můžete poslat jakoukoliv z těchto instrukcí a dostanete odpověď v 1 cyklu. Takže "cyklus" není sekunda. "Cyklus" je relativní pojem. Kupříkladu: Cyklus v ENIACu udává schopnost vykonat 5000 operací za sekundu. A pamatujte si, že počítač je poháněn hodinami, což je v podstatě přepínač umožňující jít zpět a dopředu, zpět a dopředu, a to, jak rychle dokážou přepínat udává, na kolika cyklech naráz mohu pracovat. Moderní počítač to zvládne mnohem rychleji, Řekněme, že 10 na 10 za sekundu, nebo dokonce trilion cyklů za sekundu. Když to shrneme,pokud mluvíme o čase nebo rychlosti nějakého algoritmu, nemluvíme o sekundách, ale poukazujeme na "počet primitivních kroků". Nazýváme to "primitivními kroky" proto, jelikož předpokládáme, že každý tento krok vyžaduje konstantní množství času. Lze tedy říct, že základní výpočet odpovídá jednomu kroku. Ale když máme počítač, který zpracovává složité kroky, například náš napsaný algoritmus, zabere to více kroků, že? Na počítačovém čipu neexistuje operace "Test na prvočíselnost". Počítačový čip zvládá pouze jednoduché věci, které jdou udělat na papíře.
video