A Pravidla a organizace
    Tento dokument je sbírkou cvičení a komentovaných příkladů zdrojového kódu. Každá kapitola odpovídá jednomu týdnu semestru a tedy jednomu cvičení. Cvičení v prvním týdnu semestru („nulté“) je určeno k seznámení se s výukovým prostředím, studijními materiály a základními nástroji ekosystému.
    Každá část sbírky (zejména tedy všechny ukázky a příklady) jsou také k dispozici jako samostatné soubory, které můžete upravovat a spouštět. Této rozdělené verzi sbírky říkáme zdrojový balík. Aktuální verzi1 (ve všech variantách) můžete získat dvěma způsoby:
    1. Ve studijních materiálech předmětu v ISu – soubory PDF ve složce text, zdrojový balík ve složkách 00 (organizační informace), 01 až 12 (jednotlivé kapitoly = týdny semestru), dále s1 až s3 (sady úloh) a konečně ve složce sol vzorová řešení. Doporučujeme soubory stahovat dávkově pomocí volby „stáhnout jako ZIP“.
    2. Po přihlášení na studentský server aisa (buď za pomoci ssh nebo putty) zadáním příkazu pb111 update. Všechny výše uvedené složky pak naleznete ve složce ~/pb111.
    Tato kapitola (složka) dále obsahuje závazná pravidla a organizační pokyny. Než budete pokračovat, pozorně si je prosím přečtěte.
    Pro komunikaci s organizátory kurzu slouží diskusní fórum v ISu (více informací naleznete v části T.1). Nepište prosím organizátorům ani cvičícím maily ohledně předmětu, nejste-li k tomu specificky vyzváni. S žádostmi o výjimky ze studijních povinností, omluvenkami, atp., se obracejte vždy na studijní oddělení.
    1
    Studijní materiály budeme tento semestr doplňovat průběžně. Než začnete pracovat na přípravách nebo příkladech ze sady, vždy se prosím ujistěte, že máte jejich aktuální verzi. Zadání příprav lze považovat za finální počínaje půlnocí na pondělí odpovídajícího týdne, sady podobně půlnocí na první pondělí odpovídajícího bloku. Pro první týden tedy 17.2.2025 00:00 a první sadu 24.2.2025 00:00.

    A.1 Přehled

    Tento předmět sestává z cvičení, sad domácích úloh a závěrečného praktického testu (zkoušky). Protože se jedná o „programovací“ předmět, většina práce v předmětu – a tedy i jeho hodnocení – se bude zaměřovat na praktické programování. Je důležité, abyste programovali co možná nejvíce, ideálně každý den, ale minimálně několikrát každý týden. K tomu Vám budou sloužit příklady v této sbírce a domácí úlohy, kterých budou za semestr 3 sady, a budou znatelně většího rozsahu (maximálně malé stovky řádků). V obou případech bude v průběhu semestru stoupat náročnost – je tedy důležité, abyste drželi krok a práci neodkládali na poslední chvíli.
    Protože programování je těžké, bude i tento kurz těžký – je zcela nezbytné vložit do něj odpovídající úsilí. Doufáme, že kurz úspěšně absolvujete, a co je důležitější, že se v něm toho naučíte co nejvíce. Je ale nutno podotknout, že i přes svou náročnost je tento kurz jen malým krokem na dlouhé cestě.

    A.1.1 Probíraná témata
    Předmět je rozdělen do 4 bloků (čtvrtý blok patří do zkouškového období). Do každého bloku v semestru patří 4 kapitoly (témata) a jim odpovídající 4 cvičení.
    bl. téma
    1 1. výpočetní stroj
    2. lokální proměnné, řízení toku
    3. podprogram
    4. adresa, ukazatel
    2 5. pole, index, ukazatel do pole
    6. struktura, zřetězený seznam
    7. základy alokace paměti
    8. TBD
    3 9. dynamické pole
    10. slovník a množina
    11. správa paměti
    12. TBD

    A.1.2 Organizace sbírky
    V následujících sekcích naleznete detailnější informace a závazná pravidla kurzu: doporučujeme Vám, abyste se s nimi důkladně seznámili.2 Zbytek sbírky je pak rozdělen na části, které odpovídají jednotlivým týdnům semestru. Důležité: během prvního týdne semestru už budete řešit přípravy z první kapitoly, přestože první cvičení je ve až v týdnu druhém. Nulté cvičení je volitelné a není nijak hodnoceno.
    Kapitoly jsou číslovány podle témat z předchozí tabulky: ve druhém týdnu semestru se tedy ve cvičení budeme zabývat tématy, ke kterým jste v prvním týdnu vypracovali a odevzdali přípravy.
    2
    Pravidla jsou velmi podobná těm v kurzu IB111, ale přesto si je pozorně přečtěte.

    A.1.3 Plán semestru
    Tento kurz vyžaduje značnou aktivitu během semestru. V této sekci naleznete přehled důležitých událostí formou kalendáře. Jednotlivé události jsou značeny takto (bližší informace ke každé naleznete v následujících odstavcích tohoto úvodu):
    Nejdůležitější události jsou zvýrazněny: termíny odevzdání příprav a poslední termín odevzdání úloh ze sad (obojí vždy o 23:59 uvedeného dne).
    únor
              Po      Út      St      Čt      Pá      So      Ne  
    #1 17 18 19 20 21 22 23
    cv 0       01/v   01/p  
    #2 24 25 26 27 28    
    cv 1 s1/1   s1/2 02/v s1/3    
    březen
              Po      Út      St      Čt      Pá      So      Ne  
    #2           1 2
              02/p  
    #3 3 4 5 6 7 8 9
    cv 2 s1/4   s1/5 03/v s1/6 03/p  
    #4 10 11 12 13 14 15 16
    cv 3 s1/7   s1/8 04/v s1/9 04/p  
    #5 17 18 19 20 21 22 23
    cv 4 s1/10   s1/11 05/v s1/12 05/p  
    #6 24 25 26 27 28 29 30
    cv 5 s2/1   s2/2 06/v s2/3 06/p  
    #7 31            
    cv 6 s2/4            
    duben
              Po      Út      St      Čt      Pá      So      Ne  
    #7   1 2 3 4 5 6
        s2/5 07/v s2/6 07/p  
    #8 7 8 9 10 11 12 13
    cv 7 s2/7   s2/8 08/v s2/9 08/p  
    #9 14 15 16 17 18 19 20
    cv 8 s2/10   s2/11 09/v s2/12 09/p  
    #10 21 22 23 24 25 26 27
    cv 9 s3/1   s3/2 10/v s3/3 10/p  
    #11 28 29 30        
    cv10 s3/4   s3/5        
    květen
              Po      Út      St      Čt      Pá      So      Ne  
    #11       1 sv 2 3 4
          11/v s3/6 11/p  
    #12 5 6 7 8 sv 9 10 11
    cv11 s3/7   s3/8 12/v s3/9 12/p  
    #13 12 13 14 15 16 17 18
    cv12 s3/10   s3/11   s3/12    
    19 20 21 22 23 24 25
                 
    26 27 28 29 30 31  
                 

    A.2 Hodnocení

    Abyste předmět úspěšně ukončili, musíte v každém bloku3 získat 50 bodů. Žádné další požadavky nemáme.
    Výsledná známka závisí na celkovém součtu bodů (splníte-li potřebných 4×50 bodů, automaticky získáte známku alespoň E). Hodnota ve sloupci „předběžné minimum“ danou známku zaručuje – na konci semestru se hranice ještě mohou posunout směrem dolů tak, aby výsledná stupnice přibližně odpovídala očekávané distribuci dle ECTS.4
    známka předběžné minimum po vyhodnocení semestru
    A 360 90. percentil + 60
    B 320 65. percentil + 60
    C 280 35. percentil + 60
    D 240 10. percentil + 60
    E 200 200
    Body lze získat mnoha různými způsoby (přesnější podmínky naleznete v následujících sekcích této kapitoly). V blocích 1-3 (probíhají během semestru) jsou to:
    Za přípravy a cvičení lze tedy získat teoretické maximum 72 bodů. Dále můžete získat:
    Konečně blok 4, který patří do zkouškového období, nemá ani cvičení ani sadu domácích úloh. Body získáte účastí na programovacím testu:
    3
    Máte-li předmět ukončen zápočtem, čtvrtý blok a tedy ani závěrečný test pro Vás není relevantní. Platí požadavek na 3×50 bodů z bloků v semestru.
    4
    Percentil budeme počítat z bodů v semestru (první tři bloky) a bude brát do úvahy všechny studenty, bez ohledu na ukončení, kteří splnili tyto tři bloky (tzn. mají potřebné minimum 3×50 bodů).
    5
    V případě, že jste řádně omluveni v ISu, nebo Vaše cvičení odpadlo (např. padlo na státní svátek), můžete body za účast získat buď náhradou v jiné skupině (pro státní svátky dostanete instrukce mailem, individuální případy si domluvte s cvičícími obou dotčených skupin). Nemůžete-li účast nahradit takto, domluvte se se svým cvičícím (v tomto případě lze i mailem) na vypracování 3 rozšířených příkladů ze sbírky (přesné detaily Vám sdělí cvičící podle konkrétní situace). Neomluvenou neúčast lze nahrazovat pouze v jiné skupině a to max. 1–2× za semestr.

    A.3 Přípravy

    Jak již bylo zmíněno, chcete-li se naučit programovat, musíte programování věnovat nemalé množství času, a navíc musí být tento čas rozložen do delších období – semestr nelze v žádném případě doběhnout tím, že budete týden programovat 12 hodin denně, i když to možná pokryje potřebný počet hodin. Proto od Vás budeme chtít, abyste každý týden odevzdali několik vyřešených příkladů z této sbírky. Tento požadavek má ještě jeden důvod: chceme, abyste vždy v době cvičení už měli látku každý samostatně nastudovanou, abychom mohli řešit zajímavé problémy, nikoliv opakovat základní pojmy.
    Také Vás prosíme, abyste příklady, které plánujete odevzdat, řešili vždy samostatně: případnou zakázanou spolupráci budeme trestat (viz také konec této kapitoly).

    A.3.1 Odevzdání

    Každý příklad obsahuje základní sadu testů. To, že Vám tyto testy prochází, je jediné kritérium pro zisk základních bodů za odevzdání příprav. Poté, co příklady odevzdáte, budou tytéž testy na Vašem řešení automaticky spuštěny, a jejich výsledek Vám bude zapsán do poznámkového bloku. Smyslem tohoto opatření je zamezit případům, kdy omylem odevzdáte nesprávné, nebo jinak nevyhovující řešení, aniž byste o tom věděli. Velmi silně Vám proto doporučujeme odevzdávat s určitým předstihem, abyste případné nesrovnalosti měli ještě čas vyřešit. Krom základních („sanity“) testů pak ve čtvrtek o 23:59 a znovu v sobotu o 23:59 (těsně po konci odevzdávání) spustíme rozšířenou sadu testů („verity“).
    Za každý odevzdaný příklad, který splnil základní („sanity“) testy získáváte jeden bod. Za příklad, který navíc splnil rozšířené testy získáte další bod (tzn. celkem 2 body). Výsledky testů naleznete v poznámkovém bloku v informačním systému.
    Příklady můžete odevzdávat:
    1. do odevzdávárny s názvem NN v ISu (např. 01),
    2. příkazem pb111 submit ve složce ~/pb111/NN.
    Podrobnější instrukce naleznete v kapitole T (technické informace, soubory 00/t*).
    Termíny pro odevzdání příprav k jednotlivým kapitolám jsou shrnuty v přehledovém kalendáři v části A.1 takto:

    A.4 Cvičení

    Těžiště tohoto předmětu je jednoznačně v samostatné domácí práci – učit se programovat znamená zejména hodně programovat. Společná cvičení sice nemohou tuto práci nahradit, mohou Vám ale přesto v lecčem pomoct. Smyslem cvičení je:
    1. analyzovat problémy, na které jste při samostatné domácí práci narazili, a zejména prodiskutovat, jak je vyřešit,
    2. řešit programátorské problémy společně (s cvičícím, ve dvojici, ve skupině) – nahlédnout jak o programech a programování uvažují ostatní a užitečné prvky si osvojit.
    Cvičení je rozděleno na dva podobně dlouhé segmenty, které odpovídají těmto bodům. První část probíhá přibližně takto:
    Druhá část cvičení je variabilnější, ale bude se vždy točit kolem bodů za aktivitu (každý týden můžete za aktivitu získat maximálně 3 body).
    Ve čtvrtém, osmém a dvanáctém týdnu proběhnou „vnitrosemestrálky“ kde budete řešit samostatně dva příklady ze sbírky, bez možnosti hledat na internetu – tak, jak to bude na závěrečném testu; každé úspěšné řešení (tzn. takové, které splní verity testy) získá 3 body za aktivitu pro daný týden (celkem tedy lze za příklady získat 6 bodů). Navíc dostanete 3 teoretické otázky, po jednom bodu, celkově lze tedy během vnitrosemestrálky získat až 9 bodů (počítají se jako aktivita, tzn. platí celkový limit 12/blok).
    V ostatních týdnech budete ve druhém segmentu kombinovat různé aktivity, které budou postavené na příkladech typu r z aktuální kapitoly (které konkrétní příklady budete ve cvičení řešit vybere cvičící, může ale samozřejmě vzít v potaz Vaše preference):
    1. Můžete se přihlásit k řešení příkladu na plátně, kdy primárně vymýšlíte řešení Vy, ale zbytek třídy Vám bude podle potřeby radit, nebo se ptát co/jak/proč se v řešení děje. U jednodušších příkladů se od Vás bude také očekávat, že jako součást řešení doplníte testy.
    2. Cvičící Vám může zadat práci ve dvojicích – první dvojice, která se dopracuje k funkčnímu řešení získá možnost své řešení předvést zbytku třídy – vysvětlit jak a proč funguje, odpovědět na případné dotazy, opravit chyby, které v řešení publikum najde, atp. – a získat tak body za aktivitu. Získané 3 body budou rozděleny rovným dílem mezi vítězné řešitele.
    3. příklad můžete také řešit společně jako skupina – takto vymyšlený kód bude zapisovat cvičící (body za aktivitu se v tomto případě neudělují).

    A.5 Sady domácích úloh
    Ke každému bloku patří sada 4–6 domácích úloh. Na úspěšné odevzdání každé domácí úlohy budete mít 12 pokusů rozložených do 4 týdnů odpovídajícího bloku cvičení. Odevzdávání bude otevřeno vždy v 0:00 prvního dne bloku (tzn. 24h před prvním spuštěním verity testů).
    Termíny odevzdání (vyhodnocení verity testů) jsou vždy v pondělí, středu a pátek v 23:59 – vyznačeno jako s1/1–12, s2/1–12 a s3/1–12 v přehledovém kalendáři v části A.1.

    A.5.1 Odevzdávání

    Součástí každého zadání je jeden zdrojový soubor (kostra), do kterého své řešení vepíšete. Vypracované příklady lze pak odevzdávat stejně jako přípravy:
    1. do odevzdávárny s názvem sN_úkol v ISu (např. s1_a_queens),
    2. příkazem pb111 submit sN_úkol ve složce ~/pb111/sN, např. pb111 submit s1_a_queens.
    Podrobnější instrukce naleznete opět v kapitole T.

    A.5.2 Vyhodnocení

    Vyhodnocení Vašich řešení probíhá ve třech fázích, a s každou z nich je spjata sada automatických testů. Tyto sady jsou:
    Fáze na sebe navazují v tom smyslu, že nesplníte-li testy v některé fázi, žádná další se už (pro dané odevzdání) nespustí. Pro splnění domácí úlohy je klíčová fáze „verity“, za kterou jsou Vám uděleny body. Časový plán vyhodnocení fází je následovný:
    Vyhodnoceno je vždy pouze nejnovější odevzdání, a každé odevzdání je vyhodnoceno v každé fázi nejvýše jednou. Výsledky naleznete v poznámkových blocích v ISu (každá úloha v samostatném bloku), případně je získáte příkazem pb111 status.
    Za každý domácí úkol, ve kterém Vaše odevzdání v příslušném termínu splní testy „verity“, získáte 7 bodů (strop bodů za úkoly je 28 za blok, počítají se tedy maximálně čtyři úspěšně vyřešené úkoly).

    A.5.3 Neúspěšná řešení
    Příklady, které se Vám nepodaří vyřešit kompletně (tzn. tak, aby na nich uspěla kontrola „verity“) nebudeme hodnotit. Nicméně může nastat situace, kdy byste potřebovali na „téměř hotové“ řešení zpětnou vazbu, např. proto, že se Vám nepodařilo zjistit, proč nefunguje.
    Taková řešení můžou být předmětem společné analýzy ve cvičení, v podobném duchu jako probíhá rozprava kolem odevzdaných příprav (samozřejmě až poté, co pro danou sadu skončí odevzdávání). Máte-li zájem takto rozebrat své řešení, domluvte se, ideálně s předstihem, se svým cvičícím. To, že jste autorem, zůstává mezi cvičícím a Vámi – Vaši spolužáci to nemusí vědět (ke kódu se samozřejmě můžete v rámci debaty přihlásit, uznáte-li to za vhodné). Stejná pravidla platí také pro nedořešené přípravy (musíte je ale odevzdat).
    Tento mechanismus je omezen prostorem ve cvičení – nemůžeme zaručit, že v případě velkého zájmu dojde na všechny (v takovém případě cvičící vybere ta řešení, která bude považovat za přínosnější pro skupinu – je tedy možné, že i když se na Vaše konkrétní řešení nedostane, budete ve cvičení analyzovat podobný problém v řešení někoho jiného).

    A.6 Závěrečný programovací test
    Zkouškové období tvoří pomyslný 4. blok a platí zde stejné kritérium jako pro všechny ostatní bloky: musíte získat alespoň 50 bodů. Závěrečný test:
    Na vypracování praktické části budete mít 4 hodiny čistého času, a bude sestávat z pěti příkladů, které budou hodnoceny automatickými testy, s maximálním ziskem 100 bodů. Příklady jsou hodnoceny binárně (tzn. příklad je uznán za plný počet bodů, nebo uznán není). Příklady budou na stejné úrovni obtížnosti jako příklady typu p/r/v ze sbírky.
    Během zkoušky můžete kdykoliv odevzdat (na počet odevzdání není žádný konkrétní limit) a vždy dostanete zpět výsledek testů syntaxe a sanity. Součástí zadání bude navíc soubor tokens.txt, kde naleznete 3 kódy. Každý z nich lze použít nejvýše jednou (vložením do komentáře do jednoho z příkladů), a každé použití kódu odhalí výsledek verity testu pro ten soubor, do kterého byl vložen. Toto se projeví pouze při prvním odevzdání s vloženým kódem, v dalších odevzdáních bude tento kód ignorován (bez ohledu na soubor, do kterého bude vložen).

    A.6.1 Vnitrosemestrálky

    V posledním týdnu každého bloku, tedy
    proběhne v rámci cvičení programovací test na 60 minut. Tyto testy budou probíhat za stejných podmínek, jako výše popsaný závěrečný test (slouží tedy mimo jiné jako příprava na něj). Řešit budete vždy ale pouze dva příklady, přitom za každý můžete získat 3 body, které se počítají jako body za aktivitu v tomto cvičení. Navíc dostanete 3 teoretické otázky, každou za 1 bod. Konečně dostanete také 1 token pro odhalení verity testu.
    6 Může se stát, že termíny budeme z technických nebo organizačních důvodů posunout na jiný den nebo hodinu. V takovém případě Vám samozřejmě změnu s dostatečným předstihem oznámíme.
    6
    Žádné jiné v kurzu nebudou k dispozici, máte tedy zaručeno, že dokážete přečíst každý program, který k dané kapitole patří – ať už z přednášky, z této sbírky, nebo kód svých spolužáků, který uvidíte ve cvičení.

    A.7 Opisování

    Na všech zadaných problémech pracujte prosím zcela samostatně – toto se týká jak příkladů ze sbírky, které budete odevzdávat, tak domácích úloh ze sad. To samozřejmě neznamená, že Vám zakazujeme společně studovat a vzájemně si pomáhat látku pochopit: k tomuto účelu můžete využít všechny zbývající příklady ve sbírce (tedy ty, které nebude ani jeden z Vás odevzdávat), a samozřejmě nepřeberné množství příkladů a cvičení, které jsou k dispozici online.
    Příklady, které odevzdáváte, slouží ke kontrole, že látce skutečně rozumíte, a že dokážete nastudované principy prakticky aplikovat. Tato kontrola je pro Váš pokrok naprosto klíčová – je velice snadné získat pasivním studiem (čtením, posloucháním přednášek, studiem již vypracovaných příkladů) pocit, že něčemu rozumíte. Dokud ale sami nenapíšete na dané téma několik programů, jedná se pravděpodobně skutečně pouze o pocit.
    Abyste nebyli ve zbytečném pokušení kontroly obcházet, nedovolenou spolupráci budeme relativně přísně trestat. Za každý prohřešek Vám bude strženo v každé instanci (jeden týden příprav se počítá jako jedna instance, příklady ze sad se počítají každý samostatně):
    Opíšete-li tedy například 2 přípravy ve druhém týdnu a:
    jste automaticky hodnoceni známkou X (60 - 2,25 - 10 je méně než potřebných 50 bodů). Podobně s příkladem z první sady (60 - 5 - 10), atd. Máte-li v bloku bodů dostatek (např. 80 - 5 - 10 ≥ 50), ve studiu předmětu pokračujete, ale započte se Vám ještě navíc penalizace 10 bodů do celkové známky. Přestává pro Vás proto platit pravidlo, že 4 splněné bloky jsou automaticky E nebo lepší.
    V situaci, kdy:
    budete penalizováni:
    To, jestli jste příklad řešili společně, nebo jej někdo vyřešil samostatně, a poté poskytl své řešení někomu dalšímu, není pro účely kontroly opisování důležité. Všechny „verze“ řešení odvozené ze společného základu budou penalizovány stejně. Taktéž zveřejnění řešení budeme chápat jako pokus o podvod, a budeme jej trestat, bez ohledu na to, jestli někdo stejné řešení odevzdá, nebo nikoliv.
    Podotýkáme ještě, že kontrola opisování nespadá do desetidenní lhůty pro hodnocení průběžných kontrol. Budeme se sice snažit opisování kontrolovat co nejdříve, ale odevzdáte-li opsaný příklad, můžete být bodově penalizováni kdykoliv (tedy i dodatečně, a to až do konce zkouškového období).

    B Úvod
    Účelem tohoto kurzu je seznámit Vás s tím, jak probíhá výpočet na úrovni procesoru, a jaký je vztah mezi tímto nízkoúrovňovým výpočetním modelem a tzv. jazyky vyšší úrovně. Abychom mohli tento vztah zkoumat, musíme porozumět jak
    1. onomu vyššímu jazyku (v tomto kurzu to bude ten nejnižší z nich – jazyk C – abychom co nejvíce zmenšili vzdálenost, kterou musíme překlenout) tak
    2. výpočetnímu stroji (který odpovídá procesoru a paměti), který bude výpočty našich programů realizovat.
    Z předchozího již znáte jiný vyšší programovací jazyk, Python – ten použijeme jako odrazový bod. Potřebovat budete samozřejmě pouze ty části jazyka, které znáte z kurzu IB111.

    B.1 Programovací jazyk
    Podobně jako v kurzu IB111, budeme používat omezenou podmnožinu „skutečného“ (prakticky běžně používaného) programovacího jazyka – v tomto kurzu to bude podmnožina jazyka C. Každá kapitola, počínaje tou druhou, bude obsahovat popis všech prvků jazyka C, které musíte v dané kapitole zvládnout.7
    V nulté a první kapitole se budeme zabývat pouze strojovým kódem a jazykem symbolických adres – budeme tedy programovat přímo výpočetní stroj, se zcela minimální abstrakcí. (Omezený) jazyk C se objeví teprve ve 2. kapitole.
    7
    Striktně vzato se v takové chvíli nejedná o zápis instrukce, pouze o předpis, jak konkrétní instrukci dopočítat – protože je to ale výpočet velmi jednoduchý, nebudeme obvykle tyto případy rozlišovat (tzn. návěstí budeme přímo interpretovat jako adresu, kterou reprezentuje v daném programu).

    B.2 Výpočetní stroj
    Stav výpočetního stroje, se kterým budeme v tomto předmětu pracovat, je velmi jednoduchý. Skládá se z:
    1. šestnácti registrů, každý o šířce 16 bitů:
      • registr rv (return value),
      • registry l1 až l7 (local),
      • registry t1 až t6 (temporary),
      • registry bp a sp,
    2. speciálního 16bitového registru pc (program counter),
    3. 64 KiB paměti adresované po slabikách (bajtech) – adresa je tedy 16bitové celé číslo (bez znaménka), které přesně určuje právě jednu paměťovou buňku, přitom každá taková buňka obsahuje celé číslo v rozsahu 0 až 255.
    Sémanticky speciální jsou pouze registry pc a sp – všechny ostatní jsou z pohledu stroje ekvivalentní a jejich jména nemají pro samotný výpočet žádný speciální význam – jedná se pouze o konvenci, která nám usnadní čtení (a psaní) programů.
    Výpočet stroje probíhá takto:
    1. z adresy uložené v registru pc se načtou dvě šestnáctibitová slova – hi z adresy pc a lo z adresy pc + 2 – která kódují jednu instrukci,
    2. instrukce je strojem dekódována a provedena:
      • slovo hi kóduje operaci (vyšší slabika), cílový registr a první registrový operand,
      • slovo lo kóduje přímý (immediate) operand, nebo druhý registrový operand (v nejvyšší půlslabice),
      • provede se efekt instrukce (tento efekt samozřejmě závisí jak na operaci, tak na operandech) – obvykle je součástí tohoto efektu změna hodnoty uložené v registru pc,
    3. nebyl-li výpočet zastaven, pokračuje bodem 1.
    Registry jsou očíslovány v pořadí uvedeném výše, totiž rv je registr číslo 0 a sp je registr číslo 15. Je vidět, že číslo registru lze zakódovat do jedné půlslabiky (registr pc operandem být nemůže).
    Následuje výčet všech operací, které umí stroj provést. Nebudeme všechny operace potřebovat hned, a nebudeme se tedy zatím ani podrobněji zabývat jejich sémantikou – tu si rozebereme vždy na začátku kapitoly, v níž začnou být tyto operace relevantní.
    1. speciální operace:
      • práce se zásobníkem (push, pop),
      • nastavení registru na konstantu (put),
      • nastavení registru na hodnotu z jiného registru (copy),
      • znaménkové rozšíření bajtu (sext),
    2. operace pro práci s pamětí:
      • kopírování dat z paměti do registru (ld, ldb),
      • kopírování z registru do paměti (st, stb),
    3. aritmetické operace:
      • aditivní – bez rozlišení znaménkovosti (add, sub),
      • násobení mul,
      • dělení se znaménkem (sdiv, smod),
      • dělení bez znaménka (udiv a umod),
    4. operace pro srovnání dvou hodnot:
      • rovnost (eq, ne),
      • znaménkové ostré nerovnosti (slt, sgt),
      • znaménkové neostré nerovnosti (sle, sge),
      • bezznaménkové ostré (ult, ugt), a konečně
      • bezznaménkové neostré (ule, uge),
    5. bitové operace:
      • logické operace and, or a xor aplikované po bitech,
      • bitové posuvy shl (levý), shr (pravý) a aritmetický sar,
    6. řízení toku:
      • nepodmíněný skok jmp,
      • podmíněné skoky jz (jump if zero) a jnz (if not zero),
      • volání a návrat z podprogramu (call, ret),
    7. ovládaní stroje:
      • halt zastaví výpočet,
      • asrt zastaví výpočet s chybou, je-li operand nulový.

    B.3 Jazyk symbolických adres
    Stroj jako takový pracuje pouze s číselnými adresami – instrukce, která obsahuje adresu, ji vždy obsahuje jako číslo. To při programování představuje značný problém, protože adresy jednotlivých částí programu závisí na tom, kolik instrukcí se nachází v části předchozí. Uvažme třeba tento program (uložený v paměti od adresy nula): 
        put  0     → rv ; vynuluj registr rv
    add  1, rv → rv ; do registru rv přičti 1
    jnz  rv, 0x0004 ; je-li rv nenulové, skoč na adresu 4
    Protože každá instrukce je kódována do 4 bajtů, adresa druhé instrukce (operace add) je 4 (její kódování je uloženo na adresách 4, 5, 6 a 7). Program jak je napsaný provede prázdný cyklus 65535× (v poslední iteraci je v registru rv hodnota ffff, přičtením jedničky se změní na nulu, podmíněný skok „není-li rv nula“ se neprovede a cyklus tak skončí).
    Uvažme nyní situaci, kdy do programu potřebujeme (na začátek) zařadit další instrukci, např. nastavení registru l1: 
        put  0     → l1 ; vynuluj registr l1
    put  0     → rv ; vynuluj registr rv
    add  1, rv → rv ; do registru rv přičti 1
    jnz  rv, 0x0004 ; je-li rv nenulové, skoč na adresu 4
    Tím se ale posunuly všechny další instrukce v programu na jiné adresy – proto adresa skoku předaná operaci jnz neodpovídá původnímu programu – tento nový program bude cyklit donekonečna (rozmyslete si proč).
    Je asi zřejmé, že kdyby měla každá změna programu (přidání nebo odebrání instrukce) znamenat, že musíme opravit všechny adresy ve všech ostatních instrukcích, moc dobře by se nám neprogramovalo. Proto pro zápis strojového kódu používáme tzv. jazyk symbolických adres. Ten nám umožňuje místa v programu – adresy – pojmenovat symbolem – textovým názvem, podobně jako nazýváme třeba proměnné v jazyce Python. Symbol zavedeme tzv. návěstím a použijeme v zápisu instrukce8 na místě adresy: 
        put  0     → rv ; vynuluj registr rv
loop:               ; návěstí pro první instrukci cyklu
    add  1, rv → rv ; do registru rv přičti 1
    jnz  rv, loop   ; je-li rv nenulové, skoč na začátek cyklu
    Když nyní přidáme na začátek programu instrukci, nic špatného se nestane – při sestavení (angl. assembly) programu se pak do podmíněného skoku místo adresy 4 doplní adresa 8 – totiž adresa instrukce, která bezprostředně následuje za návěstím.
    8
    Pro typy int a unsigned je konkrétní rozsah přípustných hodnot daný implementací – na mnoha systémech jsou tyto typy 32bitové.

    B.d Demonstrace (ukázky)

    B.d.1 [tinyvm]
    Tento program implementuje kompletní sémantiku výpočetního stroje, který budeme v tomto kurzu používat. Je naprogramován v jazyce z 11. týdne kurzu IB111, měli byste tedy samotnému zápisu programu bez problémů rozumět. V komentářích je pak vysvětlena sémantika (jak stroj pracuje).
    Protože se jedná o spustitelný program, popisuje sémantiku výpočetního stroje velmi přesně – můžete jej tedy použít jako referenční příručku strojového kódu, který budeme používat.
    Doporučujeme Vám program si pozorně přečíst už nyní, na začátku semestru, ale je zcela v pořádku, pokud neporozumíte ihned všemu. Očekáváme, že se budete k programu minimálně několik následujících týdnů pravidelně vracet. Studium sémantiky nových operací na začátku několika příštích kapitol je k tomu ideální příležitostí.
    Jádro celého stroje tvoří procedura step, která načte, dekóduje a provede jednu instrukci. Vstupními parametry jsou:
    1. pc je aktuální hodnota programového čítače,
    2. regs je seznam 16 celých čísel, každé v rozsahu 0 až 65535, jenž reprezentují hodnoty uložené v registrech,
    3. mem je seznam 65536 celých čísel, každé v rozsahu 0 až 255, přitom číslo uložené na indexu i reprezentuje paměťovou buňku s adresou i.
    Návratovou hodnotou je dvojice celých čísel (nová hodnota programového čítače, příznak má-li výpočet pokračovat). 
    def step( pc: int, regs: list[ int ], 
          mem: list[ int ] ) -> tuple[ int, int ]:
    Následující tvrzení popisují základní vstupní podmínky. 
        assert 0 <= pc < 65536 
    assert len( regs ) == 16
    assert len( mem ) == 65536
    Abychom mohli instrukci co nejsnadněji provést, dekódujeme ji na několik pojmenovaných hodnot. Hodnota opcode je číslo operace, složené ze dvou půlslabik – kategorie cat a konkrétní operace z dané kategorie op. V šestnáctkovém zápisu tedy opcode = 0x12 značí operaci 2 z kategorie 1. 
        opcode  = mem[pc] 
    cat     = opcode // 16
    op      = opcode % 16
    Druhá slabika popisuje vstupní a výstupní registr – tyto se uplatní u většiny operací (výjimky tvoří zejména operace z kategorie 0 – speciální instrukce, a kategorie 15 – řízení toku). Je-li šestnáctkový zápis druhé slabiky 0x82, je výstupním registrem ten s číslem 8 (t1) a (prvním) vstupním registrem je registr číslo 2, totiž l2. 
        r_out   = mem[ pc + 1 ] // 16 
    r_1     = mem[ pc + 1 ] %  16
    Třetí a čtvrtá slabika pak popisují buď tzv. přímý (immediate) operand (číselnou hodnotu, která je přímo součástí instrukce) nebo druhý vstupní registr (pro binární operace nad registry, např. ty dobře známé aritmetické). Nemá-li instrukce přímý operand, je poslední slabika nevyužitá. 
        imm     = mem[ pc + 3 ] + mem[ pc + 2 ] * 256 
    r_2     = mem[ pc + 2 ] // 16
    addr    = imm
    Než instrukci vykonáme, vypíšeme dekódovanou instrukci a aktuální stav stroje – procedura print_state nemá na výpočet stroje žádný vliv, není tedy nutné ji blíže zkoumat. Můžete si ji ale přizpůsobit dle vlastního vkusu nebo potřeby. 
        print_state( pc, regs, cat, op, imm, r_out, r_1, r_2 )
    Nyní již následuje samotné vykonání instrukce. První dvě operace jsou z kategorie 14 – řízení stroje. Instrukce asrt ukončí výpočet s chybou, je-li ve vstupním registru hodnota nula, jinak pokračuje ve výpočtu další instrukcí. Instrukce halt výpočet zastaví vždy (nikoliv ale chybou). 
        if opcode == 0xee and regs[ r_1 ] == 0: # asrt 
        return pc, ERROR
    if opcode == 0xef: # halt
        return pc, HALT
    Následují speciální operace z kategorie 0. Operace copy uloží do výstupního registru hodnotu registru vstupního, operace put uloží přímý operand do výstupního registru a konečně sext provede znaménkové rozšíření spodní slabiky vstupního registru a výsledek uloží do toho výstupního. 
        if opcode == 0x0c: # copy 
        regs[ r_out ] = regs[ r_1 ]
    if opcode == 0x0d: # put
        regs[ r_out ] = imm
    if opcode == 0x0e: # sext
        regs[ r_out ] = as_signed( regs[ r_1 ], 8 ) % 65536
    Dále do kategorie 0 patří operace pro obecnou práci s pamětí.
    Operace st (store):
    Varianta stb zapíše pouze spodní slabiku vstupního registru a přepíše tedy jedinou buňku paměti. 
        if opcode in [ 0x03, 0x04 ]: # st, stb 
        addr = ( addr + regs[ r_out ] ) % 65536

        if opcode == 0x03: # stb 
        mem[ addr ] = regs[ r_1 ]  % 256

        if opcode == 0x04: # st 
        mem[ addr + 0 ] = regs[ r_1 ] // 256
        mem[ addr + 1 ] = regs[ r_1 ]  % 256
    Operace ld analogicky:
    Varianta ldb přečte z paměti pouze jednu slabiku a na celé slovo ji doplní levostrannými nulami. 
        if opcode in [ 0x01, 0x02 ]: # ld, ldb 
        addr = ( addr + regs[ r_1 ] ) % 65536

        if opcode == 0x01: # ldb 
        regs[ r_out ] = mem[ addr ]

        if opcode == 0x02: # ld 
        regs[ r_out ] = mem[ addr ] * 256 + mem[ addr + 1 ]
    Konečně jsou v kategorii 0 operace push a pop pro práci se zásobníkem. Jejich efekt je implementován pomocnými procedurami push a pop níže, protože stejný efekt budeme potřebovat i při implementaci některých dalších operací.
    Operace push sníží hodnotu uloženou v registru sp o dvě a na výslednou adresu uloží slovo ze vstupního registru.
    Operace pop analogicky nejprve přečte slovo uložené na adrese dané registrem sp, uloží ho do výstupního registru a konečně hodnotu registru sp o dvě zvýší. 
        if opcode == 0x0a: # push 
        push( regs, mem, regs[ r_1 ] )
    if opcode == 0x0b: # pop
        regs[ r_out ] = pop( regs, mem )
    Tím je kategorie 0 vyřešena. Dále pokračujeme kategorií 15, která obsahuje operace pro řízení toku. Operace call uloží hodnotu programového čítače na zásobník (podobně jako operace push) – jedná se o tzv. návratovou adresu. Dále nastaví pc na hodnotu přímého operandu, čím předá řízení podprogramu na této adrese uloženému. 
        if opcode == 0xfe: # call 
        push( regs, mem, pc )
        return imm, CONT
    Operace ret ukončí vykonávání podprogramu a řízení vrátí volajícímu – návratovou adresu načte ze zásobníku podobně jako operace pop. Tuto adresu nezapomeneme zvýšit, protože adresa na uložená zásobníku ukazuje na instrukci call, která volání způsobila. 
        if opcode == 0xff: # ret 
        return pop( regs, mem ) + 4, CONT
    Konečně operace skoků – nepodmíněné jmp a podmíněné jz a jnz – pouze nastaví programový čítač na hodnotu přímého operandu. Podmíněný skok se provede v případě, že je hodnota vstupního registru nulová (jz) nebo naopak nenulová (jnz). Není-li podmínka splněna, tyto operace nemají žádný efekt a výpočet pokračuje další instrukcí. 
        if cat == 0xf and ( op == 0 or # jmp 
                        op == 1 and regs[ r_1 ] == 0 or # jz
                        op == 2 and regs[ r_1 ] != 0 ): # jnz
        return imm, CONT
    Kategorie 1 až 3 obsahují binární aritmetické operace v několika variantách:
    Implementace aritmetických operací naleznete v čisté funkci arith definované níže. 
        if cat == 1: 
        regs[ r_out ] = arith( op, imm, regs[ r_1 ] )
    if cat == 2:
        regs[ r_out ] = arith( op, regs[ r_1 ], imm )
    if cat == 3:
        regs[ r_out ] = arith( op, regs[ r_1 ], regs[ r_2 ] )
    Konečně kategorie 10 a 11 provádí aritmetické srovnání dvou hodnot – buď ve variantě se dvěma registry, nebo srovnání vstupního registru s přímým operandem. 
        if cat == 0xa: 
        regs[ r_out ] = compare( op, regs[ r_1 ], regs[ r_2 ] )
    if cat == 0xb:
        regs[ r_out ] = compare( op, regs[ r_1 ], imm )
    Tím je implementace kompletní. S výjimkou několika málo operací pokračuje výpočet další instrukcí, tzn. té, která je uložena na adrese o 4 vyšší, než byla ta aktuální (každá instrukce je kódována čtyřmi slabikami). 
        return pc + 4, CONT
    Následující dva podprogramy realizují operace se zásobníkem – adresa vrcholu zásobníku je uložena v registru sp (registr číslo 15). 
    def push( regs: list[ int ], mem: list[ int ], val: int ) -> None: 
    regs[ 15 ] = ( regs[ 15 ] - 2 ) % 65536
    mem[ regs[ 15 ] ] = val

    def pop( regs: list[ int ], mem: list[ int ] ) -> int: 
    rv = mem[ regs[ 15 ] ]
    regs[ 15 ] = ( regs[ 15 ] + 2 ) % 65536
    return rv
    Čistá funkce as_signed bijektivně zobrazí celé číslo z rozsahu na číslo v rozsahu , metodou známou jako dvojkový doplňkový kód. Opačné zobrazení lze v Pythonu provést velmi jednoduše, jako m % 2 ** b. Protože stejný výraz popisuje zkrácení výsledku, které se používá při bezznaménkové aritmetice s pevnou šířkou slova, budeme jej níže zapisovat přímo, bez použití pomocné funkce. Zobrazení realizované funkcí as_signed budeme níže značit . 
    def as_signed( num: int, bits: int ) -> int: 
    mod = 2 ** bits
    num = num % mod
    return num if num < mod // 2 else num - mod
    Čistá funkce arith realizuje základní aritmetické a logické operace – sčítání, odečítání, násobení a dělení se zbytkem, bitové logické operace a bitové posuvy. Vstupem jsou dvě celá čísla op_1 a op_2 v rozsahu , výsledek je v témže rozsahu. 
    def arith( op: int, op_1: int, op_2: int ) -> int:
    Užitečnou vlastností dvojkového doplňkového kódu je, že operace sčítání (odečítání) a násobení se provádí zcela stejně, jako jejich bezznaménkové verze – platí:
    Pro dělení podobná rovnost žel neplatí, proto musíme rozlišovat operace sdiv/udiv a smod/umod. 
        if op == 0x1: return ( op_1 + op_2 ) % 65536 
    if op == 0x2: return ( op_1 - op_2 ) % 65536
    if op == 0x3: return ( op_1 * op_2 ) % 65536
    if op == 0x4: return op_1 // op_2
    if op == 0x6: return op_1 %  op_2
    Pro jednoduchost budeme při dělení dodržovat znaménkovou konvenci, která se používá v jazyce C, a která je žel odlišná od té, která se používá v jazyce Python. 
        if op == 0x5 or op == 0x7: # signed div/rem 
        dividend = as_signed( op_1, 16 )
        divisor = as_signed( op_2, 16 )
        quot, rem = divmod( dividend, divisor )

            if ( dividend > 0 ) != ( divisor > 0 ) and rem != 0: 
            rem -= divisor
        if quot < 0 and rem != 0:
            quot += 1

            return ( quot if op == 0x5 else rem ) % 65536
    Bitové logické operace se provádí po jednotlivých bitech (číslicích ve dvojkovém zápisu). Každá operace provede na odpovídajících bitech v operandech příslušnou logickou operaci (and, or nebo xor), čím získá odpovídající bit výsledku. Operandy jsou vždy 16bitové. 
        if op in [ 0xa, 0xb, 0xc ]: 
        result = 0
        for idx in range(16):
            bit_1 = op_1 // 2 ** idx % 2
            bit_2 = op_2 // 2 ** idx % 2

                if op == 0xa: 
                bit_r = bit_1 == 1 and bit_2 == 1
            if op == 0xb:
                bit_r = bit_1 == 1 or  bit_2 == 1
            if op == 0xc:
                bit_r = ( bit_1 == 1 ) != ( bit_2 == 1 )

                result += bit_r * 2 ** idx 

            return result
    Bitové posuvy jsou jednoduché – posuv doleva odpovídá násobení a posuv doprava dělení příslušnou mocninou dvojky. Při pravých posuvech (dělení) musíme opět rozlišit bezznaménkovou (shr) a znaménkovou (sar) verzi. Znaménkový (tzv. aritmetický) posuv pak lze chápat i jako operaci, která posouvá jednotlivé bity doprava, ale zleva doplňuje místo nul kopie znaménkového bitu. 
        if op == 0xd: 
        return ( op_1 * 2 ** op_2 ) % 65536
    if op == 0xe:
        return ( op_1 // 2 ** op_2 ) % 65536
    if op == 0xf:
        return ( as_signed( op_1, 16 ) // 2 ** op_2 ) % 65536

        assert False
    Čistá funkce compare realizuje aritmetická srovnání. Krom rovnosti ( ) jsou všechny operace závislé na tom, pracujeme-li se znaménkovou reprezentací – v dvojkovém doplňkovém kódu jsou kódy záporných čísel větší, než kódy čísel kladných, např. 16bitové kódování -1 je 0xffff, přitom 16bitové kódování +1 je 0x0001, výsledek 0xffff < 0x0001 ale jistě v tomto kontextu nedává smysl. 
    def compare( op: int, arg_1: int, arg_2: int ) -> int: 

        sig_1 = as_signed( arg_1, 16 ) 
    sig_2 = as_signed( arg_2, 16 )

        if op == 0x0: result = arg_1 == arg_2 
    if op == 0xf: result = arg_1 != arg_2

        if op == 0x1: result = arg_1 <  arg_2 
    if op == 0x2: result = arg_1 <= arg_2
    if op == 0x3: result = arg_1 >  arg_2
    if op == 0x4: result = arg_1 >= arg_2

        if op == 0xa: result = sig_1 <  sig_2 
    if op == 0xb: result = sig_1 <= sig_2
    if op == 0xc: result = sig_1 >  sig_2
    if op == 0xd: result = sig_1 >= sig_2

        return 1 if result else 0
    Tím je implementace step a jejích pomocných funkcí hotova. Za pomoci step je již velmi jednoduché implementovat podprogram run, který provede celý výpočet. Program je uložen od adresy 0. 
    CONT = 0 
HALT = 1
ERROR = 2

    def run( regs: list[ int ], mem: list[ int ] ) -> bool: 
    print( "  pc inst op_1 op_2  out │ " +
           "  rv   l1   l2   l3   l4   l5   l6   l7 " +
           "  t1   t2   t3   t4   t5   t6   sp   bp" )
    status = CONT
    pc = 0

        while status == CONT: 
        pc, status = step( pc, regs, mem )

        return status == HALT
    Další částí je podprogram read_program, který ze vstupního souboru přečte počáteční stav paměti (kterému můžeme také říkat program). 
    def write_nibble( mem: list[ int ], index: int, nibble: int ) -> None: 
    mem[ index // 2 ] += nibble * 16 if index % 2 == 0 else nibble

    def read_program( filename: str ) -> list[ int ]: 
    mem = [ 0 for i in range( 65536 ) ]
    index = 0

        with open( filename, 'r' ) as file: 
        for line in file.readlines():
            if line[ 0 ] == ';':
                break
            for word in line.rstrip().replace( "'", '' ).split( ' ' ):
                for hex_nibble in word:
                    write_nibble( mem, index, FROM_HEX[ hex_nibble ] )
                    index += 1

        return mem
    Zbývá vstupní bod (podprogram main) a procedury pro výpis aktuálního stavu výpočetního stroje. Zbývající kód není pro pochopení funkčnosti výpočetního stroje tiny nijak podstatný.

    1 Výpočetní stroj
    Předmětem této kapitoly je přímé programování výpočetního stroje tiny (v jazyce symbolických adres).
    Ukázky:
    1. triangle – trojúhelníková nerovnost,
    2. factorial – iterativní výpočet faktoriálu.
    Přípravy:
    1. fib – -té Fibonacciho číslo (mod ),
    2. adder – dvouslovná sčítačka (32b),
    3. gcd – Euklidův algoritmus,
    4. prime – rozhodování prvočíselnosti,
    5. popcnt – počítání jedniček ve slově,
    6. perfect – součet dělitelů.
    Řešené příklady:
    1. reverse – otočení bitů ve slově,
    2. hamming – Hammingova vzdálenost slov,
    3. packed – sečtení dvou dvojic po složkách,
    4. bitswap – prohození dvou bitů ve slově,
    5. collatz – počítání kroků iterovaného výpočtu,
    6. shift – bitový posuv na části slova.

    1.1 Strojový kód
    V této kapitole budeme potřebovat 2 typy instrukcí – výpočetní (aritmetické, logické, atp.) a instrukce pro řízení toku (nepodmíněné a podmíněné skoky). Zejména prozatím nebudeme potřebovat pracovat s adresami, pamětí obecně, ani zásobníkem.

    1.1.1 Kopírování hodnot
    Nejzákladnější operací, kterou můžeme v programu potřebovat, je nastavení registru, a to buď na předem známou konstantu, nebo na hodnotu aktuálně uloženou v některém jiném registru.
    K nastavení registru na konstantu můžeme použít operaci put, která nastaví výstupní registr na hodnotu přímého operandu. Zápis této instrukce bude vypadat např. takto: 
    put 13   → rv                                  
put 0x70 → l1
halt
    Tento program nastaví registr rv na hodnotu 13 a registr l1 na hodnotu 112.
    Pro kopírování hodnot mezi registry použijeme operaci copy – ta nastaví výstupní registr na tutéž hodnotu, jakou má registr vstupní. Například: 
    put  13 → rv                                   
put  17 → l1
copy rv → l2 ; sets l2 = 13
copy l1 → rv ; sets rv = 17
halt
    Po provedení tohoto programu budou hodnoty registrů rv = 17, l1 = 17 a l2 = 13.

    1.1.2 Aritmetika

    Další důležitou kategorií jsou aritmetické instrukce. Následující tabulka shrnuje operace, které máte k dispozici. Registr l1 odpovídá proměnné a, registr l2 proměnné b, registr rv pak proměnné x.
    název python tiny
    sčítání x = a + b add l1, l2 → rv
    odečítání x = a - b sub l1, l2 → rv
    násobení x = a * b mul l1, l2 → rv
    dělení x = a // b sdiv l1, l2 → rv
    udiv l1, l2 → rv
    zbytek x = a % b smod l1, l2 → rv
    umod l1, l2 → rv
    Všimněte si, že operaci celočíselného dělení a zbytku po dělení odpovídají dvě různé instrukce. Je to proto, že fyzicky jsou registry realizované jako sekvence binárních přepínačů – každý přepínač reprezentuje jeden bit. Tyto binární sekvence lze interpretovat různými způsoby, nicméně -bitový registr obvykle chápeme jako:
    1. celé číslo bez znaménka v rozsahu – pak sekvence bitů přímo odpovídá binárnímu zápisu tohoto čísla,
    2. jako celé číslo se znaménkem v rozsahu , a to tak, že:
      1. je-li nejvyšší bit nastaven na 1, ,
      2. jinak 
    Podmínku z bodu (a) můžeme také chápat jako ⟦n ≥ 2ᵇ⁻¹⟧.
    Pro 16bitová čísla, která budeme v tomto předmětu používat zdaleka nejčastěji, to jsou tyto rozsahy:
    Tato reprezentace má tu vlastnost, že sčítání, odečítání a násobení používá na úrovni bitů stejný algoritmus v obou případech – proto operace add funguje stejně dobře bez ohledu na to, chápeme-li operandy jako znaménkové nebo bezznaménkové.
    To ale neplatí pro dělení (a nebude to platit ani pro srovnání, jak uvidíme za chvíli) – výsledek se bude lišit v závislosti na tom, je-li operace znaménková (sdiv, smod) nebo nikoliv (udiv, umod).

    1.1.3 Srovnání

    Prakticky každý vyšší programovací jazyk má nějakou formu podmíněného příkazu. Aby byla tato konstrukce užitečná, potřebujeme mít k dispozici predikáty – operace, kterých výsledkem je pravdivostní hodnota. Ty nejběžnější již dobře znáte – jsou to celočíselné srovnávací operátory. V Pythonu je zapisujeme jako a == b, a < b, atp.
    Náš výpočetní stroj má pro tento účel sadu operací – jsou shrnuty v tabulce níže. Jak již bylo výše naznačeno, s výjimkou rovnosti musíme rozlišovat znaménkovou a bezznaménkovou verzi. Na rozdíl od Pythonu (nebo jazyka C) nemá strojový kód složené výrazy, proto musíme výsledek srovnání vždy uložit do registru (analogem v Pythonu je booleovská proměnná – budeme ji zde opět značit x).
    python tiny
    x = a == b eq l1, l2 → rv 𝐞𝐪ual
    x = a != b ne l1, l2 → rv 𝐧ot 𝐞qual
    x = a < b slt l1, l2 → rv 𝐬igned 𝐥ess 𝐭han
    ult l1, l2 → rv 𝐮nsigned 𝐥ess 𝐭han
    x = a > b sgt l1, l2 → rv 𝐬igned 𝐠reater 𝐭han
    ugt l1, l2 → rv 𝐮nsigned 𝐠reater 𝐭han
    x = a <= b sle l1, l2 → rv 𝐬igned 𝐥ess or 𝐞qual
    ule l1, l2 → rv 𝐮nsigned 𝐥ess or 𝐞qual
    x = a >= b sge l1, l2 → rv 𝐬igned 𝐠reater or 𝐞qual
    uge l1, l2 → rv 𝐮nsigned 𝐠reater or 𝐞qual
    Výsledek uložený do výstupního registru (v příkladech výše rv) je u instrukcí z této rodiny vždy 1 (pravda) nebo 0 (nepravda). To zejména znamená, že je možné tyto výsledky kombinovat operacemi and, or a xor a výsledek bude vždy opět 0 nebo 1, v souladu s definicí příslušné logické operace (k těmto se vrátíme níže).

    1.1.4 Řízení toku
    Abychom mohli realizovat podmíněné příkazy a cykly, budeme k tomu potřebovat speciální operace – podobně jako příslušným příkazům ve vyšším jazyce jim budeme říkat řízení toku.
    Výpočetní stroj tiny obsahuje 3 operace tohoto typu:
    V kombinaci s aritmetickými a srovnávacími operacemi popsanými výše dokážeme zapsat jednoduchou podmínku např. takto (odpovídající program v Python-u je uveden v komentářích): 
        put 1     → l1 ; a = 1
    slt l1, 3 → t1 ; t = a < 3
    jz  t1, else   ; if t:
then:
    put 2     → l2 ;     b = 2
    jmp endif      ; else:
else:
    put 3     → l2 ;     b = 3
endif:
    halt
    Zkuste si program spustit pomocí tinyvm.py z kapitoly B, a také upravit první instrukci na put 5 → l1 a srovnejte výsledek. Podobně můžeme zapsat také while cyklus (cykly for do strojového kódu přímo přepsat nemůžeme, ale jak jistě víte, je vždy možné nejprve je přepsat na cykly while). Uvažme tento velmi jednoduchý program v Pythonu: 
    a = 1
while a < 3:
    a += 1
    Přepis do strojového kódu bude opět vyžadovat určitou kreativitu, protože máme pouze instrukce skoku, nikoliv instrukce cyklu. Stačí si ale uvědomit, že while True se realizuje snadno: pomocí nepodmíněného skoku zpět (na nižší adresu). 
        put 1     → l1   ; a = 1
loop:                ; while True:
    slt l1, 3 → t1   ;     t = a < 3
    jz  t1, end      ;     if not t: break
    add l1, 1 → l1   ;     a += 1
    jmp loop
end:
    halt
    Cyklus while podmínka jsme přepsali na while True a podmíněný break – ekvivalenci těchto dvou zápisů si rozmyslete.

    1.1.5 Bitové logické operace
    XXX

    1.1.6 Bitové posuvy
    XXX

    1.2 Programovací jazyk
    Tato kapitola jazyk C nepoužívá.

    1.d Demonstrace (ukázky)

    1.d.1 [triangle]
    V této ukázce napíšeme jednoduchý program, který rozhodne zadává-li trojice vstupních čísel trojúhelník (tzn. určí, zda vstup splňuje potřebné trojúhelníkové nerovnosti).
    V Pythonu tento problém řeší výraz: 
    (a + b > c) and (b + c > a) and (c + a > b)
    Nejprve si nachystáme testovací kód a testovací data (tuto část můžete při čtení přeskočit – to bude platit i v dalších ukázkách). Testovací kód načte testovací data z paměti – jak tyto instrukce fungují si blíže ukážeme v dalších kapitolách.
    Vstup budeme očekávat v registrech l1, l2 a l3 a výsledek (0 nebo 1) zapíšeme do registru rv. 
    test: ; driver 
    ld   l7, 0x24   → l1
    add  l7, 2      → l7
    ld   l7, 0x24   → l2
    add  l7, 2      → l7
    ld   l7, 0x24   → l3
    add  l7, 2      → l7
    eq   l1, 0xffff → t1 ; test-end marker
    jz   t1, solution
    halt

    data:   ;  l1  l2  l3  →  rv 
    .word  3,  4,  5,     1
    .word  1,  1,  1,     1
    .word  1,  1,  3,     0
    .word  2,  3,  1,     0
    .word -1,  0

    check: 
    ld   l7, 0x24   → t1
    eq   rv, t1     → t1
    asrt t1
    add  l7, 2      → l7
    jmp  test

    .trigger set _tc_expect_ 4 
.trigger inc _tc_

    solution: ; zde začíná řešení
    Protože potřebujeme implementovat konjunkci, nastavíme do registru rv její neutrální hodnotu – true, tzn. 1. Každý ze tří testů pak bude implementovaný stejně – sečte dvě strany, srovná tento součet se stranou třetí a výsledek tohoto srovnání přidá do registru rv bitovou operací and. 
        put 1      → rv
    Každý z následovných tří bloků realizuje jednu nerovnost. Mezivýsledky ukládáme do registrů t1 (součet stran) a t2 (výsledek srovnání součtu se zbývající stranou). 
        add l1, l2 → t1 
    sgt t1, l3 → t2
    and rv, t2 → rv

        add l1, l3 → t1 
    sgt t1, l2 → t2
    and rv, t2 → rv

        add l2, l3 → t1 
    sgt t1, l1 → t2
    and rv, t2 → rv
    Tím je výpočet ukončen a protože je již výsledek uložen ve správném registru, nezbývá než předat řízení zpátky do testovacího kódu. 
        jmp check

    1.d.2 [factorial]
    V této ukázce naprogramujeme jeden z nejjednodušších číselných algoritmů vůbec – iterativní výpočet faktoriálu celého kladného čísla. Novým prvkem bude tedy cyklus – opakované spuštění stejného segmentu kódu.
    Testovací kód můžete opět přeskočit, řešení začíná návěstím solution. Vstupní hodnota bude v registru l6, výsledek pak v registru rv. 
    test: ; driver 
    ld   l7, 0x10   → l6
    eq   l6, 0xffff → t1 ; test-end marker
    jz   t1, solution
    halt

    data:   ; input, expect 
    .word     1,      1
    .word     2,      2
    .word     3,      6
    .word     4,     24
    .word    -1,      0

    check: 
    add  l7, 2      → l7
    ld   l7, 0x10   → t1
    eq   rv, t1     → t1
    asrt t1
    add  l7, 2      → l7
    jmp  test

    .trigger set _tc_expect_ 4 
.trigger inc _tc_

    solution: ; zde začíná řešení
    Registr rv budeme používat jako střadač (akumulátor) – před vstupem do cyklu jej nastavíme na neutrální hodnotu 1 a v každé iteraci jej vynásobíme počítadlem iterací.
    Jako řídící proměnnou použijeme přímo l6 – protože na pořadí násobení nezáleží, můžeme hodnoty násobit sestupně v pořadí . Jakmile řídící proměnná dosáhne hodnoty nula, cyklus ukončíme (musíme si pouze dát pozor, abychom nulou již nenásobili). 
        put 1 → rv 
loop:
    mul rv, l6 → rv
    sub l6, 1  → l6
    jnz l6, loop

        jmp check

    1.p Přípravy

    1.p.1 [fib]
    Vaším úkolem je naprogramovat iterativní výpočet -tého Fibonacciho čísla. Vstupní hodnotu naleznete v registru l6, výsledek uložte do registru rv. Po skončení výpočtu proveďte skok na návěstí check. Hodnotu registru l7 zachovejte.

    1.p.2 [adder]
    Vaším úkolem je tentokrát naprogramovat 32bitovou sčítačku. Vstupem jsou 4 16bitové hodnoty uložené v registrech l1 až l4, kde l1 a l3 jsou nižší a l2 a l4 jsou vyšší slova sčítanců. Nižší slovo výsledku uložte do rv, to vyšší pak do l6. Hodnotu v registru l7 neměňte.

    1.p.3 [gcd]
    Vaším úkolem je naprogramovat Euklidův algoritmus pro nalezení největšího společného dělitele hodnot uložených v registrech l1 a l2 – obě hodnoty interpretujte jako 16bitová celá čísla bez znaménka.
    Výsledek uložte do registru rv. Po ukončení výpočtu skočte na návěstí check. Hodnotu registru l7 neměňte.

    1.p.4 [prime]
    Napište program, který rozhodne, je-li hodnota uložená v registru l6 prvočíslem (hodnotu interpretujte jako číslo bez znaménka). Výsledek (1 pokud prvočíslem je, 0 jinak) uložte do registru rv a proveďte skok na návěstí check. Hodnotu registru l7 nijak neměňte.

    1.p.5 [popcnt]
    Napište program, který určí, kolik je jedniček v binárním zápisu čísla uloženého v registru l6. Výsledek uložte do registru rv a poté proveďte skok na návěstí check. Hodnotu registru l7 nijak neměňte.

    1.p.6 [abundant]
    Napište program, který rozhodne, je-li hodnota uložená v registru l6 abundantním číslem (číslo je abundantní, je-li součet všech jeho dělitelů ). Vstup interpretujte jako číslo bez znaménka.
    Výsledek (1 pokud abundantní je, 0 jinak) uložte do registru rv a proveďte skok na návěstí check. Hodnotu registru l7 nijak neměňte.

    1.r Řešené úlohy

    1.r.1 [reverse]
    Vaším úkolem bude otočit pořadí bitů ve slově. Vstupní slovo bude uloženo v registru l1, výsledek uložte do rv a skočte na návěstí check. Hodnotu v registru l7 neměňte.

    1.r.2 [hamming]
    Spočtěte Hammingovu vzdálenost slov uložených v l1 a l2. Hammingovou vzdáleností je počet pozic, v nichž se vstupní slova liší hodnotou bitu. Výsledek uložte do rv a skočte na návěstí check. Hodnotu v registru l7 neměňte.

    1.r.3 [packed]
    Mnohé procesory nabízí tzv. vektorové instrukce, které se k jednomu velkému registru chovají, jako by obsahoval několik menších čísel uložených vedle sebe. Vaším úkolem bude emulovat jednu z těchto instrukcí; konkrétně sčítání, které 16bitové registry považuje za dvojice dvou osmibitových čísel a dvě takové dvojice sečte po složkách. Vstup je v registrech l1 a l2, výsledek uložte do rv a skočte na návěstí check. Hodnotu v registru l7 neměňte.

    1.r.4 [bitswap]
    Prohoďte dva zadané bity ve slově v registru l1. Indexy bitů jsou v l2 a l3. Můžete předpokládat, že budou v rozsahu 0–15, nula označuje nejméně významný bit slova. Výsledek uložte do rv a skočte na návěstí check. Hodnotu v registru l7 neměňte.

    1.r.5 [collatz]
    Uvažme následující funkci f na kladných celých číslech: 
      f(n) = n / 2     je-li n sudé
  f(n) = 3n +1     je-li n liché
    Collatzova domněnka říká, že budeme-li na libovolné kladné celé číslo tuto funkci opakovaně aplikovat, dostaneme se nakonec k výsledku 1.
    Vaším úkolem je tento výpočet provést a
    1. spočítat, po kolika aplikacích funkce f na vstup je poprvé výsledkem jednička a
    2. zjistit nejvyšší mezivýsledek, který při výpočtu vznikl.
    Můžete předpokládat, že pro číslo na vstupu domněnka skutečně platí a že v průběhu výpočtu nevznikne mezivýsledek, který by se nevlezl do šestnáctibitového registru.
    Počáteční číslo naleznete v registru l1. Počet aplikací funkce uložte do rv, nalezené maximum do l6 a skočte na návěstí check. Hodnotu v registru l7 neměňte.

    1.r.6 [shift]
    Proveďte levý bitový posuv:
    Rotaci provádějte na místě (v registru rv), poté skočte na návěstí check. Hodnotu v registru l7 neměňte.

    2 Lokální proměnné, řízení toku
    Ukázky:
    1. fib – lokální proměnné, cyklus
    2. prime – aritmetika a rozsah číselných hodnot
    Přípravy:
    1. gcd – euklid podruhé
    2. rand – generování pseudonáhodných čísel
    3. collatz – počítání kroků iterovaného výpočtu
    4. packed – součet n-tic po složkách
    5. popcnt – počet nenulových cifer při daném základu
    6. hamming – hammingova vzdálenost při daném základu
    Řešené příklady:
    1. palindrome – binární palindrom
    2. largest – nejvyšší číslice při daném základu
    3. factors – rozklad na prvočinitele
    4. primes – rozklad na prvočinitele podruhé
    5. transpose – překlopení bitové matice
    6. balanced – vyvážená trojková soustava
    Volitelné příklady:
    1. digits – ciferný součet při daném základu
    2. rotate – bitová rotace slova

    2.1 Strojový kód
    V této kapitole žádné nové operace potřebovat nebudeme – budeme se soustředit na jazyk C a jak se jeho základní konstrukce přeloží na operace, které známe z předchozí kapitoly.

    2.2 Programovací jazyk
    Počínaje touto kapitolou budeme většinu programů psát ve zjednodušené verzi jazyka C. V tomto kurzu budeme psát programy do jednoho souboru, který bude sestávat z definic typů (uvidíme později) a podprogramů. Na diskusi o sémantice podprogramů zatím nejsme připraveni, proto je budeme chápat jako syntaktickou obálku pro kód, který budeme psát.
    Program bude typicky vypadat takto: 
    int podprogram( int parametr₁, int parametr₂ )      
{
    …
}

int main()
{
    assert( podprogram( 1, 2 ) == 3 );
    …
}
    Podprogram s názvem main bude v tomto kurzu vždy obsahovat testy, které ověřují základní funkcionalitu ostatních podprogramů. Můžete si do něj vždy přidat svoje vlastní testy. Zápis podprogram( 1, 2 ) je volání (použití) podprogramu – prozatím jej nebudeme mimo testy potřebovat, protože jediné podprogramy, které budeme moct v tomto předmětu použít, jsou ty, které si sami napíšeme.

    2.2.1 Hodnoty, objekty a proměnné
    Proměnné znáte již z kurzu IB111 – proměnné v jazyce C mají s těmi v Pythonu mnoho společného, ale mají také důležité odlišnosti. Prvním, v zásadě syntaktickým, rozdílem je, že v jazyce C musíme každou proměnnou deklarovat – to provedeme zápisem typ jméno; případně typ jméno = výraz;. První forma proměnnou pouze deklaruje, ale její počáteční hodnotu ponechá neurčenu – tuto hodnotu není dovoleno použít.
    Typ proměnné určuje, jakých hodnot může nabývat – k dispozici máme prozatím tyto zabudované typy:
    Proměnná je v jazyce C pevně svázaná10 s objektem. Objekt je abstrakce paměti – reprezentuje entitu, která je schopna pamatovat si hodnotu, již můžeme z objektu přečíst nebo do objektu uložit novou (a tím tu předchozí přepsat). Objekt tak můžeme chápat jako dvojí zobecnění paměťové buňky:
    Realizace objektů je důležitým prvkem implementace programovacího jazyka a může se případ od případu lišit. Zejména není pravda, že by byl objekt pevně svázán s nějakou adresou nebo registrem – překladač může objekt transparentně přesouvat dle potřeby výpočtu.11
    9
    Starší standardy jazyka C neurčují, jaké kódování se použije pro znaménkové typy, novější již požadují dvojkový doplňkový kód (viz také předchozí kapitola).
    10
    Na rozdíl od jazyka Python, kde je možné vazbu proměnné na objekt změnit přiřazením. To v jazyce C možné není.
    11
    Překladače jazyka C například běžně přesouvají objekty mezi registry a zásobníkem podle aktuální situace. Tentýž objekt může být tedy v různých fázích výpočtu fyzicky uložen na různých místech.

    2.2.2 Živost a rozsah platnosti
    Objekt, který je s proměnnou svázaný, vznikne právě deklarací, a zanikne opuštěním rozsahu platnosti této proměnné. Čtení objektu je implicitní – provede se kdykoliv proměnnou použijeme jako hodnotu ve výrazu, zápis do objektu pak provedeme operátorem přiřazení (viz také další sekce).
    Podobně jméno proměnné je platné počínaje deklarací, a konče pravou složenou závorkou, která ukončuje nejbližší uzavírající blok (složený příkaz nebo tělo funkce – podrobněji rozebereme dále). Například: 
    {
    // zde x ještě není deklarováno
    int x;
    {
        int y;
        … // zde můžeme použít jak x tak y
    } // zde končí rozsah platnosti y
    … // zde již y není lze použít
} // zde končí rozsah platnosti x
    U proměnných je tak syntakticky zaručeno, že jsou svázány s živým objektem – kdykoliv můžeme jméno proměnné použít, objekt, který tato proměnná pojmenovává, existuje.

    2.2.3 Výrazy

    Na úrovni jazyka C je základní jednotkou výpočtu výraz – podobně jako v jazyce Python můžeme výrazy tvořit induktivně. Jsou-li:
    existují také výrazy tvaru:12
    1. lit (konstanta) je výraz,
    2. var (jméno proměnné) je výraz,
    3. použití aritmetického operátoru (binární v infixovém zápisu, unární v prefixovém):
      • e₁ + e₂, e₁ - e₂,
      • e₁ * e₂, e₁ / e₂, e₁ % e₂ (modulo)
      • unární mínus -e₁,
    4. relační operátory:
      • e₁ == e₂ (rovnost), e₁ != e₂ (nerovnost)
      • e₁ <= e₂, e₁ >= e₂, e₁ < e₂, e₁ > e₂
    5. bitové logické operace a posuvy:
      • binární e₁ & e₂ (and), e₁ | e₂ (or), e₁ ^ e₂ (xor),
      • unární ~e₁ – bitová negace,
      • bitové posuvy zapisujeme e₁ >> e₂, e₁ << e₂,
    6. operátory přiřazení (pozor na změnu oproti jazyku Python – v jazyce C je přiřazení výraz, nikoliv příkaz):
      • jednoduché var = e₁,
      • složené var += e₁, var -= e₁,
      • dále var *= e₁, var /= e₁, var %= e₁,
      • s bitovým posuvem var <<= e₁, var >>= e₂,
      • s bitovou operací var &= e₁, var ^= e₁, var |= e₁,
    7. operátory zvýšení a snížení proměnné o jedničku:
      • prefixové ++var, --var,
      • postfixové var++, var--,
    8. operátor čárka, e₁, e₂,
    9. booleovské logické operace:
      • binární e₁ && e₂ (and), e₁ || e₂ (or),
      • unární !e₁,
      • ternární e₁ ? e₂ : e₃,
    12
    S dalšími operátory se setkáme v pozdějších kapitolách.

    2.2.4 Vyhodnocení výrazu
    Nyní víme, jak výrazy vypadají (jakou mají syntaxi), můžeme tedy přistoupit k otázce, co takové výrazy znamenají (jakou mají sémantiku). Všechny zde uvedené výrazy13 popisují nějakou hodnotu a výraz samotný je návodem, jak tuto hodnotu získat.
    Vyhodnocení výrazu (provedení výpočtu tímto výrazem popsaného) budeme samozřejmě realizovat pomocí již zavedeného výpočetního stroje tiny. Abychom mohli výpočet skutečně provést, musíme určit registr, do kterého má být výsledek zapsán – budeme mluvit o vyhodnocení výrazu E do registru R.14
    1. Výraz lit se vyhodnotí přímo na číselnou hodnotu zapsanou ve zdrojovém kódu. Například vyhodnocení výrazu 7 do registru rv se realizuje instrukcí put 7 → rv.
    2. Výraz var se vyhodnotí na hodnotu, která je v momentě vyhodnocení tohoto výrazu uložena v objektu svázaném s proměnnou var. Prozatím uvažujeme pouze situace, kdy je objekt svázaný s var uložen přímo v registru. Je-li např. var uloženo v l1, vyhodnocení výrazu var do registru rv realizujeme instrukcí copy l1 → rv.
    3. Uvažme nyní výraz tvaru e₁ + e₂. Víme, že e₁ a e₂ popisují nějaké hodnoty. Abychom mohli vyčíslit hodnotu e₁ + e₂, budeme nejprve potřebovat tyto hodnoty. Na to použijeme dočasné registry – vyhodnocení e₁ + e₂ do rv bude vypadat takto:
      1. vyhodnoť e₁ do registru t₁,
      2. vyhodnoť e₂ do registru t₂,
      3. proveď add t₁, t₂ → rv.
      Musíme samozřejmě zabezpečit, že výpočet e₂ nepřepíše registr t₁ – jak přesně se toho dosáhne budeme zkoumat později.15 Analogicky se vypočtou ostatní aritmetické, bitové, atd. operátory (k hodnotám s/bez znaménka a operacím dělení se ještě vrátíme).
    4. Výrazy tvaru var = e₁ mají krom hodnoty také vedlejší efekt – zápis do objektu svázaného s proměnnou var. Jejich realizace vypadá takto – vyhodnocujeme do registru rv, objekt svázaný s var nechť žije v l1:
      1. vyhodnoť e₁ do registru rv
      2. proveď copy rv → l1.
      Všimněte si, že hodnota e₁ je zároveň hodnotou celého výrazu, a zůstává uložená v registru rv, jak bylo požadováno.
    5. Složené přiřazení var += e₁ je analogické, pouze je operaci copy předřazena příslušná aritmetická nebo logická operace:16
      1. vyhodnoť e₁ do registru t₁
      2. proveď add t1, l1 → rv,
      3. proveď copy rv → l1.
      Výrazy zvýšení a snížení o jedničku jsou analogické, liší se pouze ve výsledné hodnotě. Prefixové verze, ++var, --var jsou pouze syntaktické zkratky pro var += 1 resp. var -= 1, ale postfixové se liší – vyhodnocení var++ do rv proběhne takto (var je svázáno s l1):
      1. proveď copy l1 → rv,
      2. proveď add l1, 1 → l1.
      Hodnota výrazu var++ je tedy původní hodnota var, předtím, než bylo provedeno zvýšení proměnné o jedničku.
    6. Výraz e₁, e₂ představuje „zapomenutí hodnoty“ výrazu e₁ – výraz e₁ je proveden pouze pro svoje vedlejší efekty (např. výše uvedené přiřazení). Vyhodnocení e₁, e₂ do registru rv lze realizovat např. takto:
      1. vyhodnoť e₁ do rv,
      2. vyhodnoť e₂ do rv.
    7. Zbývá zatím nejsložitější typ výrazů, a to jsou booleovské logické operace. XXX
    Uvažme nyní několik konkrétních příkladů:
    1. var + 1 se vypočte XXX
    13
    Toto tvrzení v jazyce C neplatí obecně pro všechny výrazy – existují i takové, které hodnotu nemají.
    14
    Tato konstrukce skutečně tvoří základ překladu výrazů v překladači jazyka C. Rozdílem je, že překladač pracuje s dočasnými registry mnohem hospodárněji, než naivní překlad zde popsaný – tím šetří nejen volné registry, ale i instrukce, které by hodnoty mezi registry zbytečně přesouvaly. Toto platí i pro velmi jednoduché překladače (např. také tinycc).
    15
    Prozatím si vystačíme s představou, že při překladu udržujeme množinu volných dočasných registrů (takových, které jsme zatím nepoužili, nebo kterých hodnotu už jsme upotřebili, a nebudeme ji v dalším výpočtu potřebovat). Je asi jasné, že ať začneme s jakkoliv velkou konečnou množinou dočasných registrů, při výpočtu dostatečně složitého výrazu nám musí dojít – jak se s tímto problémem vypořádat si ukážeme v příští kapitole.
    16
    Pro výrazy tvarů, které jsme zatím zavedli, je var += e₁ ekvivalentní výrazu var = var + e₁. V obecném případě, kdy je na levé straně složeného přiřazení složitější výraz (a nikoliv pouze název proměnné), to už ale neplatí!

    2.2.5 Příkazy

    2.d Demonstrace (ukázky)

    2.d.1 [fib]
    Toto je první ukázka v jazyce C. Struktura souboru se bude od programů v jazyce symbolických adres poněkud lišit. Přesto, že zatím nevíme jak podprogramy pracují, budou součástí kostry a řešení tedy budeme vkládat do nachystaného podprogramu.
    Práci s lokálními proměnnými a základní konstrukce řízení toku – podmíněný příkaz a cyklus – si demonstrujeme na klasickém iterativním algoritmu pro výpočet -tého Fibonacciho čísla. 
    int fib( int n ) 
{
    První dvě Fibonacciho čísla jsou 1, 1 – uložíme je do proměnných a, b. V jazyce C jsou proměnné pevně svázány s objekty – jakmile proměnná (jméno) vznikne, její vazbu na objekt již není možné změnit. Operátor přiřazení způsobí změnu hodnoty objektu. Více o proměnných a přiřazení naleznete v sekci 2.2.
    Zejména si dejte pozor na to, že sémantika proměnných v jazyce C se výrazně liší od té, kterou znáte z jazyka Python!
    Deklarace lokálních proměnných zapisujeme takto:
    1. jména typu, v tomto případě znaménkového celočíselného typu int,
    2. neprázdného seznamu deklarovaných jmen (oddělených čárkou), které mohou být doplněny tzv. deklarátory (označují např. ukazatele: uvidíme je v pozdější ukázce),
    3. volitelného inicializátoru, který popisuje počáteční hodnotu proměnné. 
        int a = 1, b = 1;
    Jazyk C má 3 typy cyklů. Cyklus for používáme zejména v situaci, kdy předem známe potřebný počet iterací. Má následující strukturu:
    1. klíčové slovo for,
    2. hlavička cyklu, uzavřená v kulatých závorkách,
      1. inicializační příkaz (výraz, deklarace proměnné, nebo prázdný příkaz) je vždy ukončen středníkem a provede se jednou před začátkem cyklu; deklaruje-li proměnné, tyto jsou platné právě po dobu vykonávání cyklu,
      2. podmínka cyklu (výraz nebo prázdný příkaz) je opět vždy ukončena středníkem a určuje, zda se má provést další iterace cyklu (vyhodnotí-li se na true),
      3. výraz iterace (výraz, který není ukončen středníkem), který je vyhodnocen vždy na konci těla (před dalším vyhodnocením podmínky cyklu),
    3. tělo cyklu (libovolný příkaz, často složený).
    Všimněte si také, že podmínka cyklu i < n - 2 je složený výraz – jedná se o použití operátoru < (menší než), přitom pravý operand – n - 2 je opět použití operátoru (-, odečítání). Je velmi důležité si uvědomit, že náš výpočetní stroj takové výrazy neumí přímo zpracovat – dekomponovat takovéto výrazy na sekvence instrukcí je jednou z hlavních úloh překladače jazyka C.
    Strojový kód k této ukázce si zobrazíte příkazem 
    $ tinycc -S d1_fib.c
    Realizaci podmínky cyklu naleznete ve strojovém kódu pod návěstím .cond.1 – jedná se o instrukce sub l1, 2 → t1 a slt l4, t1 → t1. Překladač zde použil registr t1 pro uložení mezivýsledku, který je na úrovni jazyka C implicitní a nemá žádné jméno. 
        for ( int i = 0; i < n - 2; ++i ) 
    {
    Platnost proměnných má v jazyce C, opět na rozdíl od jazyka Python, blokovou strukturu – složené příkazy (bloky) zároveň tvoří rozsah platnosti jmen. Proměnná, která je deklarovaná uvnitř bloku, existuje pouze během vykonávání tohoto bloku. Po ukončení bloku (uzavírací složenou závorkou) tato proměnná, příslušný objekt a tedy i uložená hodnota přestanou existovat.
    Cyklus v tomto ohledu není nijak speciální – před další iterací cyklu je blok ukončen. Je-li tedy v těle cyklu deklarovaná proměnná, jedná se v každé iteraci o zcela novou proměnnou. Srovnejte situaci s řídící proměnnou (v tomto případě i). 
            int c = a + b;
    Posun výpočetního „okna“ realizujeme přiřazením. Počet existujících objektů (a tedy využitá paměť nebo registry) se přiřazením nemění, pouze se provede kopie hodnoty z jedné strany na druhou. 
            a = b; 
        b = c;
    }
    Podprogramy jsme se zatím nezabývali, nicméně příkaz return ukončí vykonáváni podprogramu a volajícímu předá návratovou hodnotu, podobně jako v jazyce Python. 
        return b; 
}

    int main() /* demo */ 
{
    Na tomto místě opět trochu předběhneme látku – použití (volání) podprogramu je výraz a jeho vyhodnocení odpovídá naší intuitivní představě: skutečné parametry (uvedené v kulatých závorkách za jménem) se použijí jako pomyslné inicializátory formálních parametrů a s takto inicializovanými parametry se vykoná tělo podprogramu. Po jeho ukončení se výraz volání podprogramu vyhodnotí na návratovou hodnotu. Jak se tento mechanismus realizuje na úrovni výpočetního stroje si povíme v příští kapitole.
    Speciální výraz assert (tvrzení) vyhodnotí svůj parametr a je-li výsledek false, program ukončí s chybou. 
        assert( fib( 1 ) == 1 ); 
    assert( fib( 2 ) == 1 );
    assert( fib( 7 ) == 13 );
    assert( fib( 20 ) == 6765 );

        return 0; 
}

    2.d.2 [prime]
    V této ukázce vyřešíme klasický úkol rozhodování prvočíselnosti, a to metodou pokusného dělení. Hlavička podprogramu deklaruje number jako hodnotu typu unsigned – celé číslo bez znaménka. Protože náš cílový stroj – tiny – má slova velikosti 16 bitů, bude i typ unsigned 16bitový.17 
    bool is_prime( unsigned number ) 
{
    Protože nejmenší prvočíslo je 2, a protože zbytek algoritmu pro hodnoty 1 ani 0 nebude pracovat správně, tyto hodnoty rovnou zamítneme. 
        if ( number < 2 ) 
        return false;
    V lokální proměnné divisor budeme udržovat aktuální pokusný dělitel. 
        unsigned divisor = 2;
    Nejjednodušší podmínka cyklu, která by zde fungovala, je divisor < number. To je ale relativně neefektivní, protože je-li prvočíslo, provedeme mnoho zbytečných iterací.
    Je-li totiž dělitelem , existuje nějaké takové, že . Je-li , potom a tedy (je-li , platí analogicky ).
    Proto existuje-li libovolný dělitel v intervalu , existuje i takový, pro který . Tuto podmínku umíme jednoduše zapsat s použitím základní aritmetiky a srovnání (operace, které jsou k dispozici tak v stroji tiny, tak v jazyce C). Přesto ale narazíme na problém: nepracujeme totiž se skutečnými celými čísly, ale s 16bitovými slovy.
    A zde potřebné nerovnosti mohou selhat, je-li výsledek násobení mimo rozsah daného typu – v našem případě mimo rozsah . Konkrétně např. , šestnáctkově 0x10a19 – pokusíme-li se toto číslo zapsat do 16 bitů, dostaneme 0x0a19, desítkově 2585.
    Jaké má tento jev důsledky pro náš výpočet? Uvažme např. test prvočíselnosti 65521. Pro divisor = 255 se divisor * divisor vyhodnotí na 65025, což je méně než 65521 a proto se vykoná tělo cyklu. V další iteraci dostaneme divisor = 256, ale divisor * divisor se na 16 bitech vyhodnotí na nulu a do cyklu tedy opět vstoupíme – a to i přesto, že při standardním celočíselném násobení bychom dostali výsledek . Tento problém bude pokračovat po mnoho iterací – takto zapsaný cyklus se zastaví až pro hodnotu divisor = 16203, kdy dostáváme:
    To ale jistě není počet iterací, který jsme očekávali – náš plán byl, že se cyklus provede pouze 256krát. 
        unsigned sqrt_uint_max = 1 << sizeof( unsigned ) * 4; 

        while ( divisor <= sqrt_uint_max && 
            divisor * divisor <= number )
    {
    Zjistíme-li, že divisor dělí hodnotu number beze zbytku, jistě to znamená, že number není prvočíslo (divisor nemůže být ani 1 ani rovný number). 
            if ( number % divisor == 0 ) 
            return false;

            ++ divisor; 
    }

        return true; 
}

    int main() /* demo */ 
{
    assert( is_prime( 2 ) );
    assert( is_prime( 3 ) );
    assert( is_prime( 5 ) );
    assert( is_prime( 13 ) );
    assert( is_prime( 29 ) );
    assert( is_prime( 97 ) );
    assert( is_prime( 619 ) );

        assert( !is_prime( 1 ) ); 
    assert( !is_prime( 4 ) );
    assert( !is_prime( 6 ) );
    assert( !is_prime( 8 ) );
    assert( !is_prime( 68 ) );
    assert( !is_prime( 77 ) );
    assert( !is_prime( 81 ) );
    assert( !is_prime( 323 ) );
    assert( !is_prime( 36863u ) );

        assert( is_prime( 65521u ) ); 
}
    17
    Standard jazyka C neurčuje přesné velikosti základních typů. Na většině současných systémů je typ unsigned 32bitový (a to i na 64bitových architekturách), ale není to nijak zaručeno.

    2.p Přípravy

    2.p.1 [gcd]
    Implementujte podprogram gcd, který Euklidovým algoritmem spočte největší společný dělitel dvou přirozených čísel, která obdrží jako argumenty. 
    unsigned gcd( unsigned x, unsigned y ) 
{
    Řešení pište sem. x a y jsou proměnné obsahující vstupní čísla. Výsledek vraťte příkazem return. 
        return x; 
}

    2.p.2 [rand]
    V této přípravě budete generovat pseudonáhodná 32bitová čísla. Protože náš stroj ani jazyk 32bitovou aritmetiku nepodporuje, budeme každé takové číslo representovat dvěma 16bitovými hodnotami hi (horních 16 bitů) a lo (spodních 16 bitů). Protože zatím neumíme z podprogramu vrátit dvě hodnoty zároveň, napíšete podprogramy dva, každý vracející jednu polovinu 32bitového čísla.
    Vzorec pro generování dalšího čísla v řadě na základě předchozího vypadá takto: 
    rand( prev ) = prev · 1103515245 + 12345
    Nápověda: Vynásobte si na papír pod sebe dvě čtyřciferná čísla. Každá cifra je jeden bajt. Vynásobení dvou bajtů a přičtení třetího se do jednoho slova vejde: 0xff · 0xff + 0xff = 0xff00
    rand_hi vrací horních 16 bitů výsledku. 
    unsigned rand_hi( unsigned hi, unsigned lo ) 
{
    return 0;
}
    rand_lo vrací spodních 16 bitů výsledku. 
    unsigned rand_lo( unsigned hi, unsigned lo ) 
{
    return 0;
}

    2.p.3 [collatz]
    Uvažme následující funkci18 f na kladných celých číslech: 
      f(n) = n / 2     je-li n sudé
  f(n) = 3n +1     je-li n liché
    Collatzova domněnka říká, že budeme-li na libovolné kladné celé číslo tuto funkci opakovaně aplikovat, dostaneme se nakonec k výsledku 1.
    Implementujte podprogram collatz_lds, který na svůj vstup bude opakovaně aplikovat funkci f než dojde k jedničce. Výsledkem podprogramu bude délka nejdelší klesající posloupnosti mezivýsledků, tj. kolikrát nejvíce po sobě prováděl půlení čísla.
    Můžete předpokládat, že pro číslo na vstupu domněnka skutečně platí a že v průběhu výpočtu nevznikne mezivýsledek, který by se nevlezl do šestnáctibitového registru. 
    unsigned collatz_lds( unsigned n ) 
{
    return 0;
}
    18
    Ač mluvíme o matematické funkci f, neočekáváme, že tato bude implementována samostatným podprogramem (tzv. funkcí) jazyka C. O těch zatím v kurzu řeč nebyla.

    2.p.4 [packed]
    Uvažme slovo, které nereprezentuje jedno šestnáctibitové číslo, ale -tici několika kratších čísel uložených vedle sebe (například 2 osmibitová nebo 4 čtyřbitová). Vaším úkolem bude čísla ve dvou takovýchto -ticích sečíst po složkách a výsledek opět vrátit jako -tici stejného tvaru.
    Implementujte podprogram packed_add, který toto sčítání provede. Jeho první dva argumenty jsou slova reprezentující -tice, třetím je šířka čísla v -tici. V případě, že tato šířka nedělí šířku slova, je číslo uložené v nejvyšších bitech kratší. Můžete předpokládat, že šířka nebude nulová. 
    unsigned packed_add( unsigned v1, unsigned v2, unsigned width ) 
{
    Řešení pište sem. v1 a v2 jsou proměnné obsahující vstupní n-tice, width obsahuje šířku čísla v n-tici. Výsledek vraťte příkazem return 
        return 0; 
}

    2.p.5 [popcnt]
    Implementujte podprogram popcnt, který spočítá počet nenulových číslic representace zadaného čísla při zadaném základu. Můžete předpokládat, že základ je alespoň dva. 
    unsigned popcnt( unsigned n, unsigned base ) 
{
    Řešení pište sem. n je proměnná obsahující vstupní číslo, base obsahuje základ. Výsledek vraťte příkazem return 
        return 0; 
}

    2.p.6 [hamming]
    Implementujte podprogram hamming, který spočítá Hammmingovu vzdálenost mezi reprezentacemi dvou zadaných čísel při daném číselném základu, tj. počet pozic, v nichž se reprezentace čísel liší cifrou. Je-li jedna z reprezentací kratší, doplňte ji zleva nulami do délky delší reprezentace. Můžete předpokládat, že základ je alespoň dva. 
    unsigned hamming( unsigned x, unsigned y, unsigned base ) 
{
    Řešení pište sem. x a y jsou proměnné obsahující vstupní čísla, base obsahuje základ. Výsledek vraťte příkazem return 
        return 0; 
}

    2.r Řešené úlohy

    2.r.1 [palindrome]
    Implementujte predikát is_binary_palindrome, který o zadaném čísle rozhodne, zda je jeho binární reprezentace palindromem. 
    bool is_binary_palindrome( unsigned n ) 
{
    Řešení pište sem. 
        return false; 
}

    2.r.2 [largest]
    Implementujte podprogram largest_digit, který pro zadané číslo n vrátí jeho nejvyšší číslici při základu base. 
    unsigned largest_digit( unsigned n, unsigned base ) 
{
    Řešení pište sem. 
        return 0; 
}

    2.r.3 [factors]
    Implementujte podprogram factor_count, který vrátí počet všech činitelů v prvočíselném rozkladu zadaného kladného čísla. Opakující se prvočinitele započítejte opakovaně. 
    unsigned factor_count( unsigned n ) 
{
    assert( n > 0 );
    Řešení pište sem. 
        return 0; 
}

    2.r.4 [primes]
    Implementujte podprogram prime_count, který vrátí počet unikátních činitelů v prvočíselném rozkladu zadaného kladného čísla. Opakující se prvočinitele započítejte pouze jednou. 
    unsigned prime_count( unsigned n ) 
{
    assert( n > 0 );
    Řešení pište sem. 
        return 0; 
}

    2.r.5 [transpose]
    Označíme-li postupně bity ve slově tak, že nejméně významný je 0 a nejvýznamnější je F, pak slovo reprezentuje následující bitové čtvercové matice o velikostech 4×4 až 1×1: 
     F E D C    8 7 6    3 2    0
 B A 9 8    5 4 3    1 0
 7 6 5 4    2 1 0
 3 2 1 0
    Implementujte podprogram transpose, který zadanou matici transponuje, tj. vrátí slovo reprezentující jednu z matic: 
     F B 7 3    8 5 2    3 1    0
 E A 6 2    7 4 1    2 0
 D 9 5 1    6 3 0
 C 8 4 0
    Velikost jedné strany matice je také argumentem podprogramu. Můžete předpokládat, že se bude jednat o číslo mezi 1 a 4. Pro velikosti menší než 4 nevyužité bity na vstupu ignorujte a ve výsledku nechť jsou nulové. 
    unsigned transpose( unsigned m, int size ) 
{
    Řešení pište sem. 
        return 0; 
}

    2.r.6 [balanced]
    Vyvážená trojková soustava nepoužívá číslice s hodnotami 0, 1 a 2, nýbrž 0, 1 a -1 (zapisované zde 0, + a -). Například číslo dvě se v ní representuje jako +-: .
    Implementujte podprogram balanced_digits, který vrátí dvě 8bitová čísla zabalená (jako v p4_packed) do jednoho slova: spodní slabika bude obsahovat počet číslic + a horní počet číslic - ve vyváženětrojkovém zápisu zadaného celého čísla. 
    unsigned balanced_digits( int n ) 
{
    Řešení pište sem. 
        return 0; 
}

    2.v Volitelné úlohy

    2.v.1 [digits]
    Implementujte podprogram digit_sum, který spočítá ciferný součet čísla při zadaném základu. Můžete předpokládat, že základ je alespoň dva. 
    unsigned digit_sum( unsigned n, unsigned base ) 
{
    Řešení pište sem. 
        return 0; 
}

    2.v.2 [rotate]
    Implementujte podprogram rotate, který provede bitovou rotaci zadaného slova o zadaný počet pozic. Kladný počet provádí rotaci vlevo, záporný vpravo. 
    unsigned rotate( unsigned word, int amount ) 
{
    Řešení pište sem. 
        return 0; 
}

    K Vzorová řešení

    K.1 Týden 1

    K.1.01.1 [reverse]

     
        put  0x0001 → t1    ; maska zdrojového bitu 
    put  0x8000 → t2    ; maska cílového bitu
    put  0      → rv
loop:
    and  l1, t1 → t3    ; zjištění zdrojového bitu
    jz   t3, zero
    or   rv, t2 → rv    ; nastavení cílového bitu
zero:
    shl  t1, 1  → t1    ; posuv obou masek
    shr  t2, 1  → t2
    jz   t2, check      ; skončit, když cílový bit vypadl z registru
    jmp  loop
    \blank

    K.1.01.2 [hamming]

     
        put       0 → rv 
    put  0x8000 → t3    ; maska srovnávaného bitu
loop:
    and  t3, l1 → t1    ; hodnoty srovnávaných bitů
    and  t3, l2 → t2
    ne   t1, t2 → t4    ; zvýšit čítač, pokud se bity nerovnají
    add  rv, t4 → rv
    shr  t3,  1 → t3    ; posunout masku srovnávaného bitu
    jz   t3, check      ; konec, pokud maskovaný bit vypadl z registru
    jmp  loop
    \blank

    K.1.01.3 [packed]

     
        add  l1, l2     → rv ; součet spodní slabiky 
    and  rv, 0x00ff → rv
    and  l1, 0xff00 → l1 ; vynulovat spodní slabiky vstupů
    and  l2, 0xff00 → l2
    add  l1, l2     → t1 ; součet horních slabik
    or   t1, rv     → rv ; promítnout horní součet do výsledku
    jmp  check
    \blank

    K.1.01.4 [bitswap]

     
        put  0x0000 → rv 
    shl   1, l2 → t2 ; masky zadaných bitů
    shl   1, l3 → t3
    and  l1, t2 → t4 ; extrakce zadaných bitů
    and  l1, t3 → t5
    xor  t2, -1 → t6 ; vynulování zadaných bitů
    and  l1, t6 → rv
    xor  t3, -1 → t6
    and  rv, t6 → rv
    jz   t4, zero    ; nastavení bitů
    or   rv, t3 → rv
zero:
    jz   t5, check
    or   rv, t2 → rv
    jmp  check
    \blank

    K.1.01.5 [collatz]

     
        put   0 → rv        ; vynulovat výstupní registry 
    put   0 → l6
check_max:
    ugt  l1, l6 → t1    ; ověřit a nastavit nové maximum
    jz   t1, loop
    copy l1 → l6
loop:
    eq   l1,  1 → t1    ; ukončit při jedničce
    jnz  t1, check
    add  rv,  1 → rv    ; jinak zvýšit čítač
    and  l1,  1 → t1    ; test sudosti
    jz   t1, even
    mul  l1,  3 → l1    ; n = 3n + 1
    add  l1,  1 → l1
    jmp  check_max      ; možná jsme našli nové maximum
even:
    udiv l1,  2 → l1    ; n = n / 2
    jmp  loop           ; při dělení jsme jistě maximum nenašli
    \blank

    K.1.01.6 [shift]

     
        put  0xffff → t2 ; do t2 nachystáme masku 
    sub  15, l3 → t3 ; počet horních nulových bitů

        shl  t2, t3 → t2 ; vynulujeme horní bity 
    shr  t2, t3 → t2

        shr  t2, l2 → t2 ; vynulujeme spodní bity 
    shl  t2, l2 → t2

        xor  t2, -1 → t3 ; inverzní maska 

        and  rv, t2 → t4 
    shl  t4,  1 → t4
    and  t4, t2 → t4

        and  rv, t3 → rv 
    or   rv, t4 → rv

        jmp  check

    T Technické informace
    Tato kapitola obsahuje informace o technické realizaci předmětu, a to zejména:

    T.1 Informační systém
    Informační systém tvoří primární „rozhraní“ pro stahování studijních materiálů, odevzdávání řešení, získání výsledků vyhodnocení a čtení recenzí. Zároveň slouží jako hlavní komunikační kanál mezi studenty a učiteli, prostřednictvím diskusního fóra.

    T.1.1 Diskusní fórum
    Máte-li dotazy k úlohám, organizaci, atp., využijte k jejich položení prosím vždy přednostně diskusní fórum.19 Ke každé kapitole a ke každému příkladu ze sady vytvoříme samostatné vlákno, kam patří dotazy specifické pro tuto kapitolu nebo tento příklad. Pro řešení obecných organizačních záležitostí a technických problémů jsou podobně v diskusním fóru nachystaná vlákna.
    Než položíte libovolný dotaz, přečtěte si relevantní část dosavadní diskuse – je možné, že na stejný problém už někdo narazil. Máte-li ve fóru dotaz, na který se Vám nedostalo do druhého pracovního dne reakce, připomeňte se prosím tím, že na tento svůj příspěvek odpovíte.
    Máte-li dotaz k výsledku testu, nikdy tento výsledek nevkládejte do příspěvku (podobně nikdy nevkládejte části řešení příkladu). Učitelé mají přístup k obsahu Vašich poznámkových bloků, i k Vámi odevzdaným souborům. Je-li to pro pochopení kontextu ostatními čtenáři potřeba, odpovídající učitel chybějící informace doplní dle uvážení.
    19
    Nebojte se do fóra napsat – když si s něčím nevíte rady a/nebo nemůžete najít v materiálech, rádi Vám pomůžeme nebo Vás nasměrujeme na místo, kde odpověď naleznete.

    T.1.2 Stažení koster
    Kostry naleznete ve studijních materiálech v ISu: Student → PB111 → Studijní materály → Učební materiály. Každá kapitola má vlastní složku, pojmenovanou 00 (tento úvod a materiály k nultému cvičení), 01 (první běžná kapitola), 02, …, 12. Veškeré soubory stáhnete jednoduše tak, že na složku kliknete pravým tlačítkem a vyberete možnost Stáhnout jako ZIP. Stažený soubor rozbalte a můžete řešit.

    T.1.3 Odevzdání řešení
    Vypracované příklady můžete odevzdat do odevzdávárny v ISu: Student → PB111 → Odevzdávárny. Pro přípravy používejte odpovídající složky s názvy 01, …, 12. Pro příklady ze sad pak s1_a_csv, atp. (složky začínající s1 pro první, s2 pro druhou a s3 pro třetí sadu).
    Soubor vložíte výběrem možnosti Soubor – nahrát (první ikonka na liště nad seznamem souborů). Tímto způsobem můžete najednou nahrát souborů několik (například všechny přípravy z dané kapitoly). Vždy se ujistěte, že vkládáte správnou verzi souboru (a že nemáte v textovém editoru neuložené změny). Pozor! Všechny vložené soubory se musí jmenovat stejně jako v kostrách, jinak nebudou rozeznány (IS při vkládání automaticky předřadí Vaše UČO – to je v pořádku, název souboru po vložení do ISu neměňte) .
    O každém odevzdaném souboru (i nerozeznaném) se Vám v poznámkovém bloku log objeví záznam. Tento záznam i výsledky testu syntaxe by se měl objevit do několika minut od odevzdání (nemáte-li ani po 15 minutách výsledky, napište prosím do diskusního fóra).
    Archiv všech souborů, které jste úspěšně odevzdali, naleznete ve složce Private ve studijních materiálech (Student → PB111 → Studijní materiály → Private).

    T.1.4 Výsledky automatických testů
    Automatickou zpětnou vazbu k odevzdaným úlohám budete dostávat prostřednictvím tzv. poznámkových bloků v ISu. Ke každé odevzdávárně existuje odpovídající poznámkový blok, ve kterém naleznete aktuální výsledky testů. Pro přípravy bude blok vypadat přibližně takto: 
    testing verity of submission from 2025-09-17 22:43 CEST
subtest p1_foo passed    [  1]
subtest p2_bar failed
subtest p3_baz failed
subtest p4_quux passed   [  1]
subtest p5_wibble passed [  1]
subtest p6_xyzzy failed
   {bližší popis chyby}
verity test failed

testing syntax of submission from 2025-09-17 22:43 CEST
subtest p1_foo passed
subtest p2_bar failed
  {bližší popis chyby}
subtest p3_baz failed
  {bližší popis chyby}
subtest p4_quux passed
subtest p5_wibble passed
subtest p6_xyzzy passed
syntax test failed

testing sanity of submission from 2025-09-17 22:43 CEST
subtest p1_foo passed    [  1]
subtest p2_bar failed
subtest p3_baz failed
subtest p4_quux passed   [  1]
subtest p5_wibble passed [  1]
subtest p6_xyzzy passed  [  1]
sanity test failed

best submission: 2025-09-17 22:43 CEST worth *7 point(s)
    Jednak si všimněte, že každý odstavec má vlastní časové razítko, které určuje, ke kterému odevzdání daný výstup patří. Tato časová razítka nemusí být stejná. V hranatých závorkách jsou uvedeny dílčí body, za hvězdičkou na posledním řádku pak celkový bodový zisk za tuto kapitolu.
    Také si všimněte, že best submission se vztahuje na jedno konkrétní odevzdání jako celek: v situaci, kdy odstavec „verity“ a odstavec „sanity“ nemají stejné časové razítko, nemusí být celkový bodový zisk součtem všech dílčích bodů. O konečném zisku rozhoduje vždy poslední odevzdání před příslušným termínem (opět jako jeden celek).20
    Výstup pro příklady ze sad je podobný, uvažme například: 
    testing verity of submission from 2025-10-11 21:14 CEST
subtest foo-small passed
subtest foo-large passed
verity test passed          [  7]

testing syntax of submission from 2025-10-14 23:54 CEST
subtest build passed
syntax test passed

testing sanity of submission from 2025-10-14 23:54 CEST
subtest foo passed
sanity test passed

best submission: 2025-10-11 21:14 CEST worth *7 point(s)
    Opět si všimněte, že časová razítka se mohou lišit (a v případě příkladů ze sady bude k této situaci docházet poměrně často, vždy tedy nejprve ověřte, ke kterému odevzdání se který odstavec vztahuje a pak až jej dále interpretujte).
    20
    Můžete si tak odevzdáním nefunkčních řešení na poslední chvíli snížit výsledný bodový zisk. Uvažte situaci, kdy máte v pátek 4 body za sanity příkladů p1, p2, p3, p6 a 1 bod za verity p1, p2. V sobotu odevzdáte řešení, kde p1 neprochází sanity testem, ale p4 ano a navíc projdou verity testy příklady p4 a p6. Váš výsledný zisk bude 5.5 bodu. Tento mechanismus Vám nikdy nesníží výsledný bodový zisk pod již jednou dosaženou hranici „best submission“.

    T.1.5 Další poznámkové bloky
    Blok corr obsahuje záznamy o manuálních bodových korekcích (např. v situaci, kdy byl Váš bodový zisk ovlivněn chybou v testech). Podobně se zde objeví záznamy o penalizaci za opisování.
    Blok log obsahuje záznam o všech odevzdaných souborech, včetně těch, které nebyly rozeznány. Nedostanete-li po odevzdání příkladu výsledek testů, ověřte si v tomto poznámkovém bloku, že soubor byl správně rozeznán.
    Blok misc obsahuje záznamy o Vaší aktivitě ve cvičení (netýká se bodů za vzájemné recenze ani vnitrosemestrální testy). Nemáte-li před koncem cvičení, ve kterém jste řešili příklad u tabule, záznam v tomto bloku, připomeňte se svému cvičícímu.
    Konečně blok sum obsahuje souhrn bodů, které jste dosud získali, a které ještě získat můžete. Dostanete-li se do situace, kdy Vám ani zisk všech zbývajících bodů nebude stačit pro splnění podmínek předmětu, tento blok Vás o tom bude informovat. Tento blok má navíc přístupnou statistiku bodů – můžete tak srovnat svůj dosavadní bodový zisk se svými spolužáky.
    Je-li blok sum v rozporu s pravidly uvedenými v tomto dokumentu, přednost mají pravidla zde uvedená. Podobně mají v případě nesrovnalosti přednost dílčí poznámkové bloky. Dojde-li k takovéto neshodě, informujte nás o tom prosím v diskusním fóru. Případná známka uvedená v poznámkovém bloku sum je podobně pouze informativní – rozhoduje vždy známka zapsaná v hodnocení předmětu.

    T.2 Studentský server aisa
    Použití serveru aisa pro odevzdávání příkladů je zcela volitelné a vše potřebné můžete vždy udělat i prostřednictvím ISu. Nevíte-li si s něčím z níže uvedeného rady, použijte IS.
    Na server aisa se přihlásíte programem ssh, který je k dispozici v prakticky každém moderním operačním systému (v OS Windows skrze WSL21 – Windows Subsystem for Linux). Konkrétní příkaz (za xlogin doplňte ten svůj): 
    $ ssh xlogin@aisa.fi.muni.cz
    Program se zeptá na heslo: použijte to fakultní (to stejné, které používáte k přihlášení na ostatní fakultní počítače, nebo např. ve fadmin-u nebo fakultním gitlab-u).
    21
    Jako alternativu, nechcete-li z nějakého důvodu WSL instalovat, lze použít program putty.

    T.2.1 Pracovní stanice
    Veškeré instrukce, které zde uvádíme pro použití na stroji aisa platí beze změn také na libovolné školní UNIX-ové pracovní stanici (tzn. z fakultních počítačů není potřeba se hlásit na stroj aisa, navíc mají sdílený domovský adresář, takže svoje soubory z tohoto serveru přímo vidíte, jako by byly uloženy na pracovní stanici).

    T.2.2 Stažení koster
    Aktuální zdrojový balík stáhnete příkazem: 
    $ pb111 update
    Stažené soubory pak naleznete ve složce ~/pb111. Je bezpečné tento příkaz použít i v případě, že ve své kopii již máte rozpracovaná řešení – systém je při aktualizaci nepřepisuje. Došlo-li ke změně kostry u příkladu, který máte lokálně modifikovaný, aktualizovanou kostru naleznete v souboru s dodatečnou příponou .pristine, např. 01/e2_concat.cpp.pristine. V takovém případě si můžete obě verze srovnat příkazem diff: 
    $ diff -u e2_concat.cpp e2_concat.cpp.pristine
    Případné relevantní změny si pak již lehce přenesete do svého řešení.
    Krom samotného zdrojového balíku Vám příkaz pb111 update stáhne i veškeré recenze (jak od učitelů, tak od spolužáků). To, že máte k dispozici nové recenze, uvidíte ve výpisu. Recenze najdete ve složce ~/pb111/reviews.

    T.2.3 Odevzdání řešení
    Odevzdat vypracované (nebo i rozpracované) řešení můžete ze složky s relevantními soubory takto: 
    $ cd ~/pb111/01
$ pb111 submit
    Přidáte-li přepínač --wait, příkaz vyčká na vyhodnocení testů fáze „syntax“ a jakmile je výsledek k dispozici, vypíše obsah příslušného poznámkového bloku. Chcete-li si ověřit co a kdy jste odevzdali, můžete použít příkaz 
    $ pb111 status
    nebo se podívat do informačního systému (blíže popsáno v sekci T.1).
    Pozor! Odevzdáváte-li stejnou sadu příprav jak v ISu tak prostřednictvím příkazu pb111, ujistěte se, že odevzdáváte vždy všechny příklady.

    T.2.4 Sdílení terminálu
    Řešíte-li příklad typu r ve cvičení, bude se Vám pravděpodobně hodit režim sdílení terminálu s cvičícím (který tak bude moct promítat Váš zdrojový kód na plátno, případně do něj jednoduše zasáhnout).
    Protože se sdílí pouze terminál, budete se muset spokojit s negrafickým textovým editorem (doporučujeme použít micro, případně vim umíte-li ho ovládat). Spojení navážete příkazem: 
    $ pb111 beamer
    Protože příkaz vytvoří nové sezení, nezapomeňte se přesunout do správné složky příkazem cd ~/pb111/NN.

    T.3 Kostry úloh
    Pracujete-li na studentském serveru aisa, můžete pro překlad jednotlivých příkladů použít přiložený soubor makefile, a to zadáním příkazu 
    $ make příklad.bin
    kde příklad je název souboru bez přípony (např. tedy make p1_fib.bin). Tento příkaz přeloží program překladačem tinycc a rovnou jej také spustí, tzn. selže-li nějaký test, tuto informaci rovnou uvidíte na obrazovce.
    Selže-li některý krok, další už se provádět nebude. Povede-li se překlad v prvním kroku, v pracovním adresáři naleznete spustitelný soubor s názvem příklad.bin, se kterým můžete dále pracovat (např. jej načíst do virtuálního stroje tinyvm.py z kapitoly B).
    Existující přeložené soubory můžete smazat příkazem make clean (vynutíte tak jejich opětovný překlad a spuštění všech kontrol).

    T.3.1 Textový editor
    Na stroji aisa je k dispozici jednoduchý editor micro, který má podobné ovládání jako klasické textové editory, které pracují v grafickém režimu, a který má slušnou podporu pro práci se zdrojovým kódem. Doporučujeme zejména méně pokročilým. Další možností jsou samozřejmě pokročilé editory vim a emacs.
    Mimo lokálně dostupné editory si můžete ve svém oblíbeném editoru, který máte nainstalovaný u sebe, nastavit režim vzdálené editace (použitím protokolu ssh). Minimálně ve VS Code je takový režim k dispozici a je uspokojivě funkční.

    T.3.2 Vlastní prostředí
    Prozatím je překladač tinycc k dispozici pouze na stroji aisa. Jakmile to bude možné, zveřejníme zdrojové kódy a/nebo již přeložené binárky tak, abyste si je mohli spustit i lokálně.

    U Doporučení k zápisu kódu
    Tato sekce rozvádí obecné principy zápisu kódu s důrazem na čitelnost a korektnost. Samozřejmě žádná sada pravidel nemůže zaručit, že napíšete dobrý (korektní a čitelný) program, o nic více, než může zaručit, že napíšete dobrou povídku nebo namalujete dobrý obraz. Přesto ve všech těchto případech pravidla existují a jejich dodržování má obvykle na výsledek pozitivní dopad.
    Každé pravidlo má samozřejmě nějaké výjimky. Tyto jsou ale výjimkami proto, že nastávají výjimečně. Některá pravidla připouští výjimky častěji než jiná:

    U.0.1 Dekompozice
    Vůbec nejdůležitější úlohou programátora je rozdělit problém tak, aby byl schopen každou část správně vyřešit a dílčí výsledky pak poskládat do korektního celku.
    1. Kód musí být rozdělen do ucelených jednotek (kde jednotkou rozumíme funkci, typ, modul, atd.) přiměřené velikosti, které lze studovat a používat nezávisle na sobě.
    2. Jednotky musí být od sebe odděleny jasným rozhraním, které by mělo být jednodušší a uchopitelnější, než kdybychom použití jednotky nahradili její definicí.
    3. Každá jednotka by měla mít jeden dobře definovaný účel, který je zachycený především v jejím pojmenování a případně rozvedený v komentáři.
    4. Máte-li problém jednotku dobře pojmenovat, může to být známka toho, že dělá příliš mnoho věcí.
    5. Jednotka by měla realizovat vhodnou abstrakci, tzn. měla by být obecná – zkuste si představit, že dostanete k řešení nějaký jiný (ale dostatečně příbuzný) problém: bude Vám tato konkrétní jednotka k něčemu dobrá, aniž byste ji museli (výrazně) upravovat?
    6. Má-li jednotka parametr, který fakticky identifikuje místo ve kterém ji používáte (bez ohledu na to, je-li to z jeho názvu patrné), je to často známka špatně zvolené abstrakce. Máte-li parametr, který by bylo lze pojmenovat called_from_bar, je to jasná známka tohoto problému.
    7. Daný podproblém by měl být vyřešen v programu pouze jednou – nedaří-li se Vám sjednotit různé varianty stejného nebo velmi podobného kódu (aniž byste se uchýlili k taktice z bodu d), může to být známka nesprávně zvolené dekompozice. Zkuste se zamyslet, není-li možné problém rozložit na podproblémy jinak.

    U.0.2 Jména
    Dobře zvolená jména velmi ulehčují čtení kódu, ale jsou i dobrým vodítkem při dekompozici a výstavbě abstrakcí.
    1. Všechny entity ve zdrojovém kódu nesou anglická jména. Angličtina je univerzální jazyk programátorů.
    2. Jméno musí být výstižné a popisné: v místě použití je obvykle jméno náš hlavní (a často jediný) zdroj informací o jmenované entitě. Nutnost hledat deklaraci nebo definici (protože ze jména není jasné, co volaná funkce dělá, nebo jaký má použitá proměnná význam) čtenáře nesmírně zdržuje.22
    3. Jména lokálního významu mohou být méně informativní: je mnohem větší šance, že význam jmenované entity si pamatujeme, protože byla definována před chvílí (např. lokální proměnná v krátké funkci).
    4. Obecněji, informační obsah jména by měl být přímo úměrný jeho rozsahu platnosti a nepřímo úměrný frekvenci použití: globální jméno musí být informativní, protože jeho definice je „daleko“ (takže si ji už nepamatujeme) a zároveň se nepoužívá příliš často (takže si nepamatujeme ani to, co jsme se dozvěděli, když jsme ho potkali naposled).
    5. Jméno parametru má dvojí funkci: krom toho, že ho používáme v těle funkce (kde se z pohledu pojmenování chová podobně jako lokální proměnná), slouží jako dokumentace funkce jako celku. Pro parametry volíme popisnější jména, než by zaručovalo jejich použití ve funkci samotné – mají totiž dodatečný globální význam.
    6. Některé entity mají ustálené názvy – je rozumné se jich držet, protože čtenář automaticky rozumí jejich významu, i přes obvyklou stručnost. Zároveň je potřeba se vyvarovat použití takovýchto ustálených jmen pro nesouvisející entity. Typickým příkladem jsou iterační proměnné i a j.
    7. Jména s velkým rozsahem platnosti by měla být také zapamatovatelná. Je vždy lepší si přímo vzpomenout na jméno funkce, kterou právě potřebuji, než ho vyhledávat (podobně jako je lepší znát slovo, než ho jít hledat ve slovníku).
    8. Použitý slovní druh by měl odpovídat druhu entity, kterou pojmenovává. Proměnné a typy pojmenováváme přednostně podstatnými jmény, funkce přednostně slovesy.
    9. Rodiny příbuzných nebo souvisejících entit pojmenováváme podle společného schématu (table_name, table_size, table_items – nikoliv např. items_in_table; list_parser, string_parser, set_parser; find_min, find_max, erase_max – nikoliv např. erase_maximum nebo erase_greatest nebo max_remove).
    10. Jména by měla brát do úvahy kontext, ve kterém jsou platná. Neopakujte typ proměnné v jejím názvu (cars, nikoliv list_of_cars ani set_of_cars) nemá-li tento typ speciální význam. Podobně jméno nadřazeného typu nepatří do jmen jeho metod (třída list by měla mít metodu length, nikoliv list_length).
    11. Dávejte si pozor na překlepy a pravopisné chyby. Zbytečně znesnadňují pochopení a (zejména v kombinaci s našeptávačem) lehce vedou na skutečné chyby způsobené záměnou podobných ale jinak napsaných jmen. Navíc kód s překlepy v názvech působí značně neprofesionálně.
    22
    Nejde zde pouze o samotný fakt, že je potřeba něco vyhledat. Mohlo by se zdát, že tento problém řeší IDE, které nás umí „poslat“ na příslušnou definici samo. Hlavní zdržení ve skutečnosti spočívá v tom, že musíme přerušit čtení předchozího celku. Na rozdíl od počítače je pro člověka „zanořování“ a zejména pak „vynořování“ na pomyslném zásobníku docela drahou operací.

    U.0.3 Stav a data
    Udržet si přehled o tom, co se v programu děje, jaké jsou vztahy mezi různými stavovými proměnnými, co může a co nemůže nastat, je jedna z nejtěžších částí programování.
    TBD: Vstupní podmínky, invarianty, …

    U.0.4 Řízení toku
    Přehledný, logický a co nejvíce lineární sled kroků nám ulehčuje pochopení algoritmu. Časté, komplikované větvení je naopak těžké sledovat a odvádí pozornost od pochopení důležitých myšlenek.
    TBD.

    U.0.5 Volba algoritmů a datových struktur
    TBD.

    U.0.6 Komentáře
    Nejde-li myšlenku předat jinak, vysvětlíme ji doprovodným komentářem. Čím těžší myšlenka, tím větší je potřeba komentovat.
    1. Podobně jako jména entit, komentáře které jsou součástí kódu píšeme anglicky.23
    2. Případný komentář jednotky kódu by měl vysvětlit především „co“ a „proč“ (tzn. jaký plní tato jednotka účel a za jakých okolností ji lze použít).
    3. Komentář by také neměl zbytečně duplikovat informace, které jsou k nalezení v hlavičce nebo jiné „nekomentářové“ části kódu – jestli máte například potřebu komentovat parametr funkce, zvažte, jestli by nešlo tento parametr lépe pojmenovat nebo otypovat.
    4. Komentář by neměl zbytečně duplikovat samotný spustitelný kód (tzn. neměl by se zdlouhavě zabývat tím „jak“ jednotka vnitřně pracuje). Zejména jsou nevhodné komentáře typu „zvýšíme proměnnou i o jedna“ – komentář lze použít k vysvětlení proč je tato operace potřebná – co daná operace dělá si může kažďý přečíst v samotném kódu.
    23
    Tato sbírka samotná představuje ústupek z tohoto pravidla: smyslem našich komentářů je naučit Vás poměrně těžké a často nové koncepty, a její cirkulace je omezená. Zkušenost z dřívějších let ukazuje, že pro studenty je anglický výklad značnou bariérou pochopení. Přesto se snažte vlastní kód komentovat anglicky – výjimku lze udělat pouze pro rozsáhlejší komentáře, které byste jinak nedokázali srozumitelně formulovat. V praxi je angličtina zcela běžně bezpodmínečně vyžadovaná.

    U.0.7 Formální úprava
    TBD.