Insight.wz.cz

Co je to počítač

22. června 2023

Obsah článku:

  1. Předmluva
  2. Úvod
  3. Co je to počítač?
  4. Co je to komputace
  5. Lingvistická odbočka
  6. Počítače analogové a digitální
  7. Co je úkolem počítače?
  8. Počítačem může být i člověk
  9. Modely komputace
  10. Popis komputace - programy a algoritmy
  11. Programovací jazyky
  12. Počítače nejsou všemocné
  13. Turingův stroj
  14. Počítače univerzální a neuniverzální
  15. "Praktická" vs teoretická informatika
  16. Co vše lze považovat za počítač
  17. Závěr

Předmluva

V tomto článku se chci snažit dobrat k podstatě toho, co to vlastně počítač je. Jedná se o moje myšlenky, které se stále snažím utřiďovat. Rozhodně se nejedná o nějaký finální, 100% korektní učební text. Tudíž neručím za správnost textu a nejsem zodpovědný za jakékoli škody, které by mohly z (ne)pochopení tohoto textu vzniknout. Jedná se o můj osobní „vhled“.

Mým cílem je 100% intuitivní pochopení problematiky.

Ostatně „chápání“ či „porozumění“ může být podle mě pouze intuitivní. Chápání je subjektivní pocit. Buď máte pocit, že danou tematiku chápete, nebo ne. Samozřejmě, jako každý jiný pocit, i tento může být mylný. Můžete si myslet, že danou tematiku chápete, a pak např. u školního testu pohoříte. Ale i naopak. I když tematiku nechápete, můžete test napsat dobře (např. natipujete odpovědi). Vaše okolí si pak může myslet, že tomu rozumíte, i když tomu tak není.

Jak míru chápání ověřovat, popř. zlepšovat? Stále se ptát (i sám sebe) na různé otázky. Pokud danou problematiku opravdu chápete, pak byste měli být schopni okamžitě odpovědět na takřka libovolnou otázku, která se daného tématu týká. Pokud toho schopni nejste, pak musíte nad daným tématem dále přemýšlet.

Ano, vím, že s intuicí je problém. Intuice je do velké míry subjektivní, je těžko uchopitelná, je nepřesná. Intuice se těžko předává. Např. matematici nemají rádi předávání vědomostí intuitivním (neformálním) způsobem, protože při něm vznikají nepřesnosti. Matematika je zcela exaktní věda a pro její potřeby byl vyvinut jistý formální (=syntaktický?) jazyk, který má jakýmkoli nepřesnostem zamezit (i když pro praktické potřeby se čistě formální jazyk nepoužívá a stále je potřeba určitá míra intuice; zcela formální systémy však také existují).

Přesto je ale matematická intuice považována za veledůležitou věc. Typickou radou, jak tuto intuici nabýt, je ale „bojuj s tím, dokud to nepochopíš“. Matematici tedy dávají ruce pryč od intuitivního předávání vědomostí a nechávají na každém, aby si matematickou intuici vypěstoval sám, což vyžaduje spoustu práce a roky poctivého studia.

Problém je, že drtivá většina lidí do tohoto stádia nikdy nedospěje. Má jim být intuitivní porozumění navždy zapovězeno? Mně osobně by např. velice pomohlo, kdybych před studiem každého tématu dostal nějaký dobrý, vysokoúrovňový nadhled. Nevidím nic špatného na přístupu „napřed něco vyložit intuitivně a až pak to zpřesňovat (formalizovat)“.

Podle mě není rozdíl mezi „formalismem“ a „intuicí“ ani zdaleka dostatečně veřejně diskutován, přitom se podle mě jedná o věc zcela zásadní, na které stojí pochopení všeho kolem nás.

Často člověk slyší, že např. nějaký učitel nějakou látku vysvětluje „dobře“. Co to ale znamená? Lidé tím myslí to, že ji vysvětluje „intuitivně“, tedy „pochopitelně“. Všichni lidé chtějí „chápat“. To je podle mě univerzální touha. Naopak „tápat“ je frustrující. Řekl bych, že míra chápání i koreluje s tím, jak moc mají lidé rádi různé školní předměty. Řada lidí nemá ráda matematiku. Podle mě je to proto, že ji „nechápou“. Je to ale opravdu jejich vina, nebo je to vina učitele, resp. toho, jak se matematika vyučuje?

Intuice je jen omezená zkušenost. Aby lidé něco považovali za intuitivní, tak si pod tím potřebují „něco představit“. Něco, s čím už mají zkušenost. Typicky nějaký hmotný objekt, nebo nějaký fyzický děj či jev, se kterým jsou již obeznámeni. Intuice se ale dá i rozšířit, natrénovat. Na věci, které se zpočátku zdály neintuitivní, se dá po určité době „zvyknout“. A právě sem patří (vyšší) matematika nebo oblasti moderní fyziky jako je teorie relativity nebo zejm. kvantová mechanika (existuje známé rčení, že „kvantová mechanika se nedá pochopit, na tu si musíte zvyknout“).

O tématu intuice chci napsat samostatný článek.

Úvod

Tento článek má za úkol jít k samotné podstatě toho, co je to vlastně počítač a co počítač provádí. Někomu se možná bude zdát příliš teoretický.

Při psaní článku jsem si uvědomil, jak velká propast zeje mezi „reálnými“ fyzickými počítači a mezi teorií toho, co tyto počítače fundamentálně dělají.

„Běžný člověk“ (počítačový laik) tak nějak mlhavě tuší, co to asi počítač je, a ví, že lidé od počítačů (které kolektivně nazývá „ajťáky“) se zabývají hardwarem nebo softwarem.

Málokdo z běžné populace má ale nějaké povědomí o teoretické informatice (anglicky „computer science“), což je právě to, co se typicky vyučuje na vysokých školách, pokud půjdete studovat „informatiku“.

Jedná se v podstatě o aplikovanou matematiku a k provozování teoretické informatiky vám stejně jako v případě samotné matematiky stačí pouze tužka a papír.

Teoretická informatika se totiž nezabývá fyzickými počítači, ale zejm. tím, co počítače provádějí – tzv. komputacemi („výpočty“). Tím je mimochodem podle některých názorů i samotný název této disciplíny špatně a místo „computer science“ by se mělo říkat spíše „computing science“ (tedy věda zabývající se komputacemi, nikoli počítači).

Každý obor musí mít nějaké pevné teoretické základy. Bez teoretické informatiky bychom například ani nemohli přesně říci, co počítač vlastně dělá.

A tak i tento článek se z velké části zabývá koncepty z teoretické informatiky. Osobně si myslím, že mít základní teoretický přehled je pro nabírání dalších znalostí v daném oboru zcela nezbytné.

Tento článek by měl být jakýmsi úvodem a odrazovým můstkem k dalším článkům a úvahám na tomto webu. Již několikrát jsem ho přepsal, ale stále s ním nejsem spokojen. Budu se k němu vracet a dále ho upravovat a doplňovat. Člověk se při studiu daného tématu dozvídá stále nové a nové věci, které napřed musí do svých již stávajících vědomostí správě „zařadit“.

Co je to počítač?

Pod slovem „počítač“ si asi většina lidí nejčastěji představí klasický stolní počítač (tedy „desktop“ či „PC“, chcete-li), popř. „notebook“ (přesněji řečeno laptop). Počítači ale nejsou jen stolní počítače a notebooky, ale např. i mobilní zařízení jako jsou chytré telefony a tablety.

Odborníci v IT se dále běžně setkávají s celou řadou dalších druhů počítačů jako jsou servery, mikrokontroléry, sálové počítače či dokonce superpočítače.

Jenže tím to zdaleka nekončí.

Např. „hloupou“ kalkulačku by asi málokdo považoval za počítač, přesto to počítač je. Počítače tedy nejsou pouze na první pohled „chytrá a komplikovaná“ zařízení, ale patří sem i zařízení „hloupá a jednoduchá“. Svým způsobem se dá dokonce říci, že právě v tom tkví podstata počítače.

Co je tedy tou základní vlastností, která všechny počítače spojuje? Co dělá počítač počítačem? Existuje nějaká krátká definice, která by to jednoznačně vystihla? Trochu jsem nad tím přemýšlel a výsledkem je:

„Počítač je entita provádějící komputace.“

Co to ale znamená? Začněme napřed tím slovem komputace, protože to je v informatice naprosto fundamentální pojem.

Co je to komputace

Komputace je fyzický proces (děj), kdy dochází k transformaci nějakého fyzického systému z počátečního stavu do koncového stavu. Mezi počátečním a koncovým stavem můžou být a (typicky jsou) „mezistavy“. Fyzický stav je v podstatě konkrétní „uspořádání hmoty“. My těmto stavům přiřazujeme nějaký význam (jsme schopni tyto stavy smysluplně interpretovat).

Na počátku komputace je tedy nějaký stav daného fyzického systému. Tento systém pak přechází ze stavu do stavu, až (po 1 až n krocích) dojde do koncového stavu, kdy je komputace ukončena. Tento koncový stav je výsledkem komputace. My tento stav nějak interpretujeme (dodáme mu význam) – např. se na monitoru počítače rozsvítí pixely ve tvaru čísla 5. Skrze zrak se tento vjem dostane do našeho mozku, kde mu dodáme význam – „výsledkem této komputace je číslo pět“.

Entitě, která provádí komputaci, říkáme počítač. A opačně – pokud je někde komputace, musí tam být i počítač, protože komputace je děj prováděný počítačem. Jedno tedy nemůže existovat bez druhého.

Co se myslí pod konkrétním „fyzickým stavem“ záleží na tom, na jakém principu je daný počítač postaven. Počítače, které běžné používáme, jsou digitální – elektronické – tranzistorové – křemíkové. Nositelem stavu je zde elektrické napětí/náboj, u mechanických pevných disků je to pak magnetický stav určitého regionu na disku. Takovéto počítače používáme proto, že tato technologie se nám historicky nejvíce osvědčila, umíme ji efektivně vyrábět, kontrolovat atd. Teoreticky by ale mohly existovat i počítače jiné – např. mechanické, kde by nositelem stavu bylo např. pootočení ozubeného kola. Dále se mluví např. o hydraulických počítačích, kde je nositelem stavu tlak vody, popř. i o biologických počítačích, kde je nositelem stavu nějaké uspořádání biologického materiálu (např. DNA). Atd...

Samotná komputace je vždy fyzický (tedy „hmotný“) proces. Jedním ze základních požadavků na komputaci je, že tento proces se dá jednoznačně popsat (definovat).

Popisu komputace říkáme program. Program je vždy zapsán v nějakém programovacím jazyce.

Komputace je tedy fyzický, „mechanický“ proces, který se dá jednoznačně popsat. V komputaci neexistuje žádná „intuice“, žádné „domýšlení“ čehokoli. Vše je jednoznačně dané. Vždy jednoznačně víme, jak přejít z jednoho stavu do stavu následujícího. A právě proto se dá komputace svěřit počítači-stroji.

To, že počítače „myslí“, je pouze iluze. Počítač „neví“, co dělá. Počítač je neživý stroj. Počítač pouze manipuluje hmotou (podobně jako libovolný jiný stroj – např. bagr).

Samozřejmě, otázkou je, jak vlastně fundamentálně „myslí“ lidé a zda se vůbec „myšlení“ počítače liší od „myšlení“ člověka, ale to je předmětem jiné debaty.

Je každý fyzický děj komputací? Podle mě ne. Komputace je typicky záměrná, vytvořená „uměle“ člověkem (např. v procesoru počítače). Fyzické děje, které se „přirozeně“ nacházejí v přírodě bez přičinění člověka, se typicky za komputaci nepovažují. Přesto se dá podle mě některým jevům přiřadit určitý význam, a pak se dá říci, že se jedná o komputaci. Stále ale platí, že je potřeba nějakého vědomého pozorovatele (člověk, mimozemšťan...), který danému fyzickému jevu přiřadí význam, a až pak lze mluvit o komputaci. Otázka však je, k čemu by nám byla komputace, kterou nedokážeme řídit...

Lingvistická odbočka

Problém je, že v češtině se slovo komputace nepoužívá a místo toho říkáme jednoduše „výpočet“ (viz např. „výpočetní technika“). To je podle mě trochu matoucí, protože „komputace“ je velice specifický typ výpočtu – je to výpočet, který se dá krok po kroku jednoznačně popsat, zatímco samotné slovo „výpočet“ je podle mě obecnější a může zahrnovat i „intuici“, pro kterou v komputaci není žádné místo.

Když se zkrátka řekne „komputace“, tak si představím fyzický, mechanický, deterministický proces, který jde ze stavu do stavu, až dojde do svého koncového stavu. Když se řekne „výpočet“, tak si nic konkrétního nepředstavím, protože to je slovo velice vágní a obecné.

Např. v angličtině se slovo komputace (computation) používá, „to compute“ znamená „provádět komputaci“, a právě odtud pochází slovo computer – tedy doslova „ten, kdo provádí komputace“.

Podle mě by bylo lepší, kdyby se v češtině slovo komputace běžně používalo a byl by od něj i odvozen název stroje provádějícího komputace (např. komputer či komputátor / komputačka – po vzoru kalkulátor / kalkulačka).

Počítače analogové a digitální

Asi tím nejzákladnějším rozdělením počítačů vůbec je dělení na počítače analogové a digitální. V podstatě všechny počítače kolem nás jsou digitální. Analogové počítače jsou dnes tak okrajová záležitost, že je skoro nemá smysl zmiňovat. Přesto to ale pro pořádek udělám. Analogové počítače se relativně hojně používaly zhruba do poloviny 20. století, ale pak je téměř zcela vytlačily počítače digitální. (Někteří lidé by se možná dokonce hádali, že analogový počítač vůbec není počítač a že existují pouze počítače digitální.)

Čím se analogové a digitální počítače navzájem liší?

Analogové počítače na rozdíl od digitálních nepracují krok po kroku a zároveň pracují se spojitými hodnotami. Analogové počítače pracují na principu „napodobování“ reality. Analogové počítače svým chováním „napodobují“ jiné jevy ve vesmíru. „Analogický“ znamená doslova „podobný“, „analogový“ pak má v češtině význam „spojitého signálu“ – tedy jako protiklad ke slovu „digitální“.

Analogové počítače nejsou typicky univerzální a jsou uzpůsobeny jen pro jeden účel. Příkladem jednoduchého analogového počítače je logaritmické pravítko.

I zde podle mě platí koncept „fyzického stavu“. Analogový počítač jde ze stavu do stavu, ale neděje se tak v diskrétních krocích (mezi stavy existuje „plynulý přechod“) a zároveň jednotlivé stavy nejsou exaktní (resp. je nelze zcela exaktně změřit).

Je třeba si ale uvědomit, že i digitální počítače jsou fundamentálně „analogové“, tj. jsou postavené na fyzikálních jevech (jako je např. elektrické napětí), které se chovají „analogově“ (tedy spojitě). Jde ale o způsob, jakým jednotlivé stavy interpretujeme. Např. určitému rozpětí (intervalu) analogových hodnot přiřadíme jednu digitální hodnotu. V nejpoužívanější technologii CMOS např. napětí v rozmezí 0 až 1,5 voltu přiřazujeme logickou hodnotu „0“ a napětí v rozmezí 3,5 až 5 voltů přiřazujeme logickou hodnotu „1“. V podstatě nad „analogovou realitou“ stavíme další „vrstvu abstrakce“, a tím našim výpočtům dodáváme jistou robustnost. (Mohli bychom používat i více úrovní hodnot, ale typicky se používají pouze dvě, např. z důvodu odolnosti vůči chybám.)

Zároveň ale digitalizací i něco ztrácíme.

Např. sčítání reálných čísel lze analogově provést jednoduše sečtením hodnot elektrických proudů. Je to jednoduché, přímé, okamžité, navíc teoreticky s neomezenou přesností. Jakmile tento úkon převedeme do digitální podoby, ztrácíme přesnost, musíme čísla převést do nějaké (arbitrární) digitální reprezentace, a pak je na nějaké digitální sčítačce sečíst, na což je typicky potřeba více kroků (není to „okamžitě“).

Zcela zásadní devizou digitálních počítačů je však jejich univerzálnost (a s tím související programovatelnost), díky které nad analogovými historicky drtivě zvítězily.

Mimochodem, dnes je velice populárním slovem slovo „digitalizace“ (např. ve spojení „digitalizace státní správy“). Tento pojem je bez výhrady korektní v případě, kdy mluvíme o převodu analogových dat do digitální podoby. Data se tímto stávají „nesmrtelná“, protože se dají donekonečna bezeztrátově kopírovat (kopie diskrétní hodnoty je vždy ta samá diskrétní hodnota). Toto je ta již výše zmíněná robustnost digitálního přístupu. Samozřejmě, data mohou stále zaniknout, pokud dojde k poškození nebo zničení jejich nosiče, ale to se může stát i u analogové reprezentace. „Digitalizací“ se však také často myslí automatizace daného úkonu, což je zavádějící. Kdybychom používali analogové počítače, říkali bychom tomu „analogizace“? Řada lidí podle mě pod slovem „digitální“ stále vidí něco „supermoderního“, zatímco co je analogové, to je „zastaralé“. Tak to ale není. Jedná se pouze o zvolený přístup k interpretaci hodnot stavů.

Přes to všechno ale mají analogové počítače stále možná své místo a mohly by i do budoucna zastoupit tam, kde digitální počítače zaostávají – viz toto video. Dokonce jsou podle některých analogové počítače možnou cestou, jak překonat výpočetní limity digitálních počítačů.

Zbytek článku se bude týkat výhradně počítačů digitálních.

Co je úkolem počítače?

Úkolem (či účelem) počítače je (automatické) provádění komputací. Nic víc, nic míň. Počítače nic jiného dělat neumějí.

Pokud chceme, aby za nás počítač vykonal nějaký úkon, pak tento úkon musíme převést na komputaci – musíme vytvořit program (popis komputace), podle kterého počítač daný úkon provede. Procesu vytváření programu se také říká algoritmizace.

Komputaci ovšem může provádět i člověk – viz následující kapitola.

Počítačem může být i člověk

Proč jsem v úvodu uvedl, že počítač je „entita provádějící komputaci“ a ne „stroj provádějící komputaci“? Protože počítačem může být i člověk.

Slovo „computer“ původně dokonce označovalo právě „lidské počítače“ – byli to lidé provádějící různé „mechanické“ výpočty např. během světových válek, kdy bylo třeba předpočítat např. balistické křivky za nejrůznějších povětrnostních podmínek a z výsledků vytvořit přehledné tabulky. Toto vyžaduje velké množství elementárních, monotónních výpočtů, které navíc musely být několikrát přepočítány, aby neobsahovaly chyby. Moderní počítač by vám takovou tabulku vytvořil během zlomku sekundy (či ještě lépe – moderní počítač by dokázal výpočty provádět v reálném čase a navíc automaticky nastavovat děla). Tehdy však ještě vhodné počítače neexistovaly – počítače-stroje se začaly opravdu rozvíjet až po 2. sv. válce. Pointou je, že tito lidé nic nevymýšleli, ale prováděli zcela „mechanické“ výpočty (v podstatě „dosazování do vzorečku“).

A právě „dosazování do vzorečku“ je asi nejtypičtějším případem „lidské komputace“, se kterou se setkal každý z nás. Vezměme v úvahu např. známý vzorec pro výpočet kořenů kvadratické funkce:

Když hledáte kořeny kvadratické funkce podle tohoto vzorce, tak nemusíte nad ničím „hluboce“ přemýšlet, pouze „otrocky“ dosazujete konkrétní čísla podle „návodu“. Je to tedy zcela „mechanický“ proces, a právě proto se dá svěřit počítači.

Pokus o formalizaci toho, co je to vlastně „mechanický postup“, a jaké konkrétní kroky obsahuje, stál v podstatě u zrodu moderní teoretické informatiky. Britský matematik Alan Turing se v roce 1935 začal zamýšlet nad tím, jaké konkrétní elementární kroky obsahuje ona lidská „mechanická“ komputace.

Výsledkem tohoto bádání byl tzv. Turingův stroj, což je (matematický) model komputace.

Modely komputace

Komputace jako taková je hmotný proces, ale tento proces lze studovat i teoreticky. Studium komputací stojí u samotných základů disciplíny, které se říká computer science („teoretická informatika“).

Pokud chcete komputaci rigorózně studovat, pak ji potřebujete nějak formalizovat, k čemuž slouží tzv. model komputace (česky typicky říkáme „výpočetní model“). Nejznámějším příkladem modelu komputace je již zmíněný Turingův stroj. Model komputace je v podstatě vysokoúrovňový „teoretický počítač“. Model komputace nemá téměř nic společného s „reálnými“ fyzickými počítači a není určen k fyzické realizaci – jedná se pouze o matematický koncept. Je to nástroj, jak formalizovat pojem komputace.

Modelů komputace existuje celá řada. Některé jsou „čistě matematické“, jiné jsou více „mechanické“ a jsou svým způsobem bližší tomu, jak by „reálný počítač“ mohl fungovat. Zástupcem té první kategorie je např. tzv. Lambda kalkulus, zástupcem druhé kategorie je již zmiňovaný Turingův stroj, resp. stavové stroje (state machines) obecně.

Modely komputace mohou být zároveň různě mocné / silné (ve smyslu toho, jak „složitou“ komputaci umějí vykonat). Podle jejich síly je lze rozdělit do kategorií.

Turingův stroj a Lambda kalkulus patří do té nejsilnější známé kategorie. Turingův stroj umí vyřešit vše, co komputačně vyřešit lze (toto je jedním ze závěrů tzv. Church-Turingovy teze). Fyzický ekvivalent Turingova stroje není překvapivě vůbec obtížné sestrojit (pokud vím, potřebujete pouze součástku, která vám poskytne funkci „podmíněného skoku“ – např. tranzistor). Všechny běžné počítače okolo nás lze považovat za „Turingovy stroje“. (Občas se setkáte se slovíčkařením, že toto není pravda, protože matematická definice Turingova stroje vyžaduje nekonečnou paměť, což v „reálu“ samozřejmě není možné. Avšak pro praktické účely můžeme fyzickou paměť považovat za nekonečnou, protože ji lze lineárně („donekonečna“) dle potřeby přidávat.)

Výše jsem napsal, že komputace je fyzický proces. Tzn. že komputace musí být fyzicky realizovatelná. Tudíž i model komputace musí být „realistický“, nesmí být „odtržený od reality“. Musí modelovat nějaký proces, jehož význam (sémantika) může být převeden do fyzické podoby.

V teoretické rovině lze samozřejmě uvažovat takřka cokoli, a tak existují i modely tzv. „hyperkomputace“, které jsou mocnější než Turingův stroj. Ty však pravděpodobně nikdy nepůjdou fyzicky realizovat. Ani proslulé kvantové počítače nejsou mocnější než Turingův stroj, tzn. že kvantové počítače jsou stejně mocné jako běžné počítače, pouze umějí některé operace vykonat (mnohem) rychleji.

Mezi modely komputace se někdy nesprávě zařazuje i tzv. Von Neumannův model. To však není model komputace, ale vysokoúrovňový návrh konstrukce fyzického digitálního elektronického počítače. Tedy něco mnohem konkrétnějšího. Von Neumannův model má blíže k inženýrství než k čisté matematice. Takřka všechny běžné počítače kolem nás jsou postaveny dle Von Neumannova modelu. Sám Von Neumann řekl, že Turingův stroj považuje za „jednoduchý a hezký“ („simple and neat“), ale nedozvěděl se z něj nic o tom, jak postavit fyzický počítač. Zde je tedy opět vidět propast mezi teoretickou informatikou a fyzickým hardwarem.

Popis komputace – programy a algoritmy

Popisu komputace říkáme program. Občas také algoritmus, i když toto označení podle mě není přesné. Program je jakýkoli popis komputace, zatímco algoritmus je postup, jak obecně řešit nějaký (komputační) problém. Algoritmem je např. známý postup násobení dvou čísel „pod sebou“ (long multiplication), který se učí na základní škole. Algoritmus je vždy definován pro všechny instance (konkrétní případy) daného problému. Algoritmus násobení dvou čísel pod sebou je tedy definován obecně pro všechna čísla z daného číselného oboru (např. reálných čísel) – např. pro 3 × 2, ale i 3216584,321 × 98654,794689. Dalšími příklady algoritmů jsou např. postup dělení polynomu polynomem nebo najití nejkratší cesty mezi dvěma body v bludišti.

Oproti tomu např. známý program „Hello world“ podle mě žádný algoritmus neobsahuje, a přesto se jedná o program (posloupnost instrukcí v daném programovacím jazyce, která vede k vytištění textu „Hello world“).

Algoritmus je občas vykládán i neformálně (např. již zmíněný základoškolský algoritmus násobení dvou čísel pod sebou), zatímco počítačový program je vždy formální záležitost, protože musí být napsán v jazyce, který má jednoznačně definovanou sémantiku (aby mohl být svěřen počítači).

Pokud ale vím, tak v praxi se pojmy program a algoritmus zaměňují. Algoritmus je považován za jeden z klíčových pojmů teoretické informatiky. Lze-li něco převést na algoritmus, pak to znamená, že to lze svěřit počítači. Pro každý algoritmus existuje odpovídající Turingův stroj. Algoritmus je také znám jako „efektivní metoda“.

Procesu převádění řešení problému na algoritmus se říká „algoritmizace“. Automatizace řešení nějakého problému má obecně dva kroky – nejprve vytvoříme algoritmus a následně tento algoritmus převedeme do konkrétního programovacího jazyka. První krok je obvykle obtížnější, samotný přepis algoritmu do konkrétního programovacího jazyka zvládne, jak se říká, „cvičená opice“.

Ne všechny algoritmy jsou si rovny. Existují algoritmy méně a více efektivní. Efektivní algoritmus se vyznačuje tím, že stejný problém vyřeší v méně výpočetních krocích. Jinými slovy – na stejně výkonném hardwaru skončí dříve než algoritmus neefektivní, čímž šetří výpočetní čas počítače (procesoru), spotřebovává méně energie a tudíž je i ekologičtější. Hledání efektivních algoritmů je jedním za základních úkolů teoretické informatiky a každý zkušenější programátor by měl znát alespoň základní sadu efektivních algoritmů.

Algoritmus je obecný postup. V obecnosti algoritmů je jejich největší síla. Dá se říci, že algoritmy jsou základem veškeré automatizace. Když naprogramujete počítač tak, aby obecně a korektně řešil nějaký problém, tak máte autonomního pracovníka, který nedělá chyby, neunavuje se a typicky pracuje mnohem rychleji než libovolný člověk. Algoritmy jsou všude kolem nás a dá se říci, že na nich stojí moderní civilizace.

Lze všechny problémy řešit algoritmicky, tj. lze pro řešení všech problémů vymyslet algoritmus? Bohužel ne. Existují problémy, které algoritmicky vyřešit nelze – viz přespříští kapitola.

Programovací jazyky

Program je tedy posloupnost instrukcí popisující danou komputaci. Program je vždy zapsán v nějakém programovacím jazyce. Programovací jazyk je nástroj (formalismus) k popisu komputací.

Programovací jazyky mají mnoho společného s jazyky přirozenými jako je čeština, angličtina atd... Přirozené jazyky však slouží ke komunikaci mezi lidmi a obsahují řadu nepřesností, což je důsledkem toho, že se nějak organicky (spontánně) vyvíjely. V řadě případů to není problém, protože člověk si dokáže řadu věcí domyslet (např. z kontextu). Ovšem počítač si nic domyslet nedokáže. Počítač je „hloupý stroj“. Programovací jazyky tedy musí být na rozdíl od přirozených jazyků zcela exaktní.

Programovací jazyk může mít různé podoby. Programovací jazyk je typicky zapisován textově, ale mohou existovat i programovací jazyky např. grafické (vizuální), a v podstatě libovolné jiné.

Dvěma základními prvky programovacího jazyka jsou syntax a sémantika (význam). Syntax je to, co píšeme. Sémantika pak určuje význam jednotlivých syntaktických konstruktů. Např. znak „+“ mezi dvěma čísly ve zdrojovém kódu daného programovacího jazyka bude asi znamenat součet těchto čísel. Může to ale také znamenat zcela něco jiného (i zcela neintuitivního). Záleží na autorovi daného jazyka. Je třeba si uvědomit, že programovací jazyky jsou lidským vynálezem, že to není něco, co se „najde v přírodě“. A jako téměř každý lidský vynález, ani programovací jazyky nejsou dokonalé.

Definovat formálně syntax není obtížné, definovat formálně sémantiku je mnohem obtíženější a velice pracné. Některé (většina?) programovací jazyky ani nemají sémantiku formálně definovanou a míst toho mají např. tzv. referenční implementaci.

Formální sémantika má ale své výhody (programy napsané v jazyce s formální sémantikou lze např. tzv. formálně / automaticky verifikovat.) a existují snahy, které se snaží vytvořit formální sémantiku pro již existující jazyky – např. jazyk C.

Součástí každého programovacího jazyka je model komputace. (doplnit)

Program z jednoho jazyka do jiného jazyka převádí program zvaný překladač (translator). V praxi se často rozlišuje mezi kompilátorem a interpreterem, ale z hlediska programátora se jedná o jedno a to samé.

Program musí být vždy převeden do tzv. strojového kódu (machine code) dané cílové platformy.

Program (tedy posloupnost instrukcí) může existovat na různých úrovních abstrakce. Programovacími jazyky nejsou pouze klasické známé jazyky jako C, Java, Python..., ale i např. assembly („jazyk symbolických adres“) nebo machine code (strojový kód). Přímo ve strojovém kódu se programuje hodně špatně, ale teoreticky to jde.

Počítače nejsou všemocné

Umějí počítače vyřešit všechny problémy? Bohužel ne. Limity komputace existují. Existují takové problémy, pro jejichž vyřešení nelze sestavit program, tj. nelze je komputačně vyřešit. Říká se jim také nerozhodnutelné (undecidable) problémy – tento pojem pochází z matematické logiky, která je s teoretickou informatikou úzce provázána.

Asi nejznámějším případem takového problému je tzv. Halting problem, který se ptá, zda lze z popisu programu usoudit, zda tento program pro daný vstup skončí, nebo bude běžet nekonečně dlouho. Tento problém je nerozhodnutelný, tzn., že to obecně určit nejde. Důležité je slovo obecně, tzn. „pro všechny případy“. Existují určité případy (instance problému), pro které to vyřešit jde. Ale obecně (pro všechny případy) to nejde.

Je důležité si uvědomit, že limity komputace nejsou limity počítačů, ale limity samotné matematiky. Halting problem (a další nerozhodnutelné problémy) nemůže obecně vyřešit ani člověk. Lidský mozek tedy z tohoto hlediska není mocnější než univerzální počítač.

Lidský mozek je samozřejmě velice složitý a zdánlivě funguje jinak než počítač. Osobně si ale myslím, že to specifický druh počítače je.

Turingův stroj

BUDE DOPLNĚNO

Počítače univerzální a neuniverzální

BUDE DOPLNĚNO

„Praktická“ vs teoretická informatika

Problematika „reálných“, fyzických počítačů a problematika toho, co fundamentálně dělají, jsou překvapivě vzdálené disciplíny. Počítače existovaly dávno před vznikem teoretické informatiky, což je disciplína, která vznikla až ve 20. století. To, jak postavit fyzický počítač, je z velké části inženýrská záležitost, zatímco teoretická informatika (věda zabývající se komputacemi na teoretické úrovni) je čistě matematická. Teoretická informatika se nezabývá tím, jak postavit počítač, ale tím, jaké jsou teoretické limity počítačů.

Někde na pomezí mezi fyzickým hardwarem a teoretickou informatikou stojí podle mě vývoj („reálného“) softwaru. Psaní programů je v idealizovaném případě čistě matematická záležitost, kdy jste od „inženýrské“ reality zcela odstíněni. Praxe je ovšem jiná – ne vše se dá převést na čistou matematiku, resp. by to dalo takovou práci, že se to v praxi nedělá, navíc se musíte potýkat s omezeními reálného fyzického hardwaru.

Matematika je „dokonalá“. Pokud bychom vytvořili matematicky korektní program, pak by i tento program byl teoreticky dokonalý – např. by běžel nejrychlejším možným způsobem (na daném hardwaru) nebo by neobsahoval žádné chyby („bugy“) – korektnost programu totiž lze matematicky dokázat, pokud k tomu existuje vhodný formální aparát (již výše zmíněná formální sémantika programovacího jazyka). Vyžadovalo by to ale striktní axiomatizaci (formalizaci) všeho a zároveň by to po programátorech vyžadovalo vysoké znalosti matematiky. Řada (řekl bych že drtivá většina) programátorů v praxi programuje čistě intuitivně, což přináší klady i zápory. Na jednu stranu může programovat prakticky každý, na druhou stranu to může vést k neznalostem či nepochopení chování daného programovacího jazyka, což dále vede k chybám v programu, které jsou nejen otravné, ale můžou stát (velké) peníze a dokonce i životy. (Např. most byste také nenechali navrhovat někým, kdo nemá pokročilé znalosti statiky.)

Dá se říci, že čím lepší jsou vaše teoretické znalosti komputace (a to jak obecně, tak v daném konkrétním programovacím jazyce), tím jste lepším programátorem.

Propagátorem striktního, matematického přístupu k programování byl např. Edsger Dijkstra.

Co vše lze považovat za počítač

BUDE DOPLNĚNO

Závěr

Tento článek jen tak lehce poškrábal povrch toho, co to vlastně počítač je. Článek je bohužel mnohem chaotičtější než jsem zamýšlel, a budu se k němu postupně vracet a systematizovat ho.

V dalších článcích na něj zároveň chci navázat a témata zde nastíněná chci postupně dále rozvíjet.

© 2023 Jakub Felger