31 902: Architektúra počítačov

"There are 10 types of people;
those who understand binary
and those who do not..."

Prvý blok cvičení

Úlohy v tomto bloku sú zamerané na reprezentáciu čísel v počítači a prevody medzi sústavami. Úlohy by ste mali byť schopní vyriešiť znalosťami z predmetu Algoritmizácia a programovanie a doplňujúcimi informáciami uvedenými pod každou úlohou. Samozrejmosťou je ovládanie problematiky z prednášky.

Za úlohy prvého bloku môžete získať až 12 bodov. Úlohy odovzdávajte priebežne, najneskôr však vo štvrtom týždni semestra. Po tomto termíne už nebude možné odovzdať žiadnu z týchto úloh!

Nemusíte riešiť všetky, vyberte si tie, ktoré vás zaujmú tak, aby ste získali potrebný počet 12 bodov. Celkove je tu 7 úloh za 20 bodov. Viac ako 12 nemôžete mať. Na zápočet potrebujete aspoň 5 bodov.

Úloha 11 (2b)

Napíšte program, ktorý zobrazí nasledovné dva vstupy: číslo 29127 a ASCII kód znaku 'F', v dvojkovej, desiatkovej a šestnástkovej sústave.

Tip: Použite čo najmenší počet premenných a využite možnosti pretypovania a formátovacieho reťazca funkcie printf.

Zdroj:

Úloha 12 (2b)

Napíšte program, ktorý dokáže zapísať zadené číslo (stačí rozsah 1-100) rímskymi číslicami.

Zdroj:

Úloha 13 (3b)

Napíšte program, ktorý zistí a vypíše na obrazovku strojové epsilon pre typy float a double. Zároveň vypíšte aj hodnoty __FLT_EPSILON__ a __DBL_EPSILON__) zadefinovanými vo float.h.

Definícia:
Strojové epsilon je najmenšie také číslo, ktoré po pripočítaní k jednotke dá niečo iné ako jednotku.

Iná definícia:
Strojové epsilon je vzdialenosť medzi číslom 1 a jeho bezprostredným pravým susedom.

Vysvetlenie: Reálne čísla sú v počítači implementované tak, že ich samozrejme nie je nekonečné množstvo. Ako uvidíte aj v úlohe 14, medzi jednotlivými číslami v počítači sú diery. Takže keď začneme počítať

    1 + 0,1   = 1,1
    1 + 0,01  = 1,01
    1 + 0,001 = 1,001 

potom kvôli obmedzenej presnosti počítača pri istom počte desatinných miest nastane situácia, že 1 + 0,0...001 = 1 (namiesto správneho 1,0...001). Potom to predošlé číslo 0,0...01 sa nazýva strojové epsilon. Je zrejmé, že na rôznych počítačoch môže byť jeho hodnota rôzna. Strojové epsilon však nie je najmenšie číslo v danej reprezentácii.

Tip 1:
Nedelíme desiatimi, ale dvoma, pretože pracujeme v dvojkovej sústave!

Tip 2:
Porovnajte si výsledok s konštantami FLT_EPSILON a DBL_EPSILON, (alebo __FLT_EPSILON__ a __DBL_EPSILON__) zadefinovanými v limits.h float.h
Ak vám vypočítané hodnoty nesedia, skúste vypnúť všetky optimalizácie. Ak máte možnosť, vyskúšajte program aj na inej platforme ako Win32/Intel.

Tip 3:
Ak vám to stále nevychádza, možno nájdete vysvetlenie tu.

Zdroj: "Machine epsilon." Wikipedia, The Free Encyclopedia. wikipedia.org

Úloha 14 (3b)

Napíšte program, ktorý na obrazovku vypíše všetky prvky počítačovej množiny s pohyblivou rádovou čiarkou F(2,2,-4,3). Vypočítané čísla vyneste na číselnú os (napr. na papier, graf v Exceli, Matlabe, gnuplote,...). Nakreslite celú množinu a potom ešte zvlášť interval <-1,1>. V tejto úlohe neodovzdávate program, ale dva obrázky!

Definícia: F(2,n,Emin,Emax) znamená, že čísla sú v dvojkovej sústave, mantisa má dĺžku n bitov a rozsah exponentov je od Emin po Emax. Mantisa je normalizovaná s jednotkou pred desatinnou čiarkou.

Zdroj:

Úloha 15 (2b)

Napíšte program, ktorý pre zadané n vypíše pekne formátovaný Pascalov trojuholník s n riadkami. Naviac bude každé párne číslo nahradené znakom *

Príklad: Pre n = 5 bude výstup programu vyzerať takto:

            1
           1 1
          1 * 1
         1 3 3 1     
        1 * * * 1
   

Zdroj:

Úloha 16 (4b)

Napíšte program na výpočet funkcie \( sin(x) \) alebo \( cos(x) \) pomocou rozvoja do Taylorovho radu v okolí bodu 0. Funkcia bude mať dva argumenty:
float sinus(float radians,float epsilon);
Koľko členov radu potrebujete na dosiahnutie zastavovacej podmienky? Aby ste získali plný počet bodov, funkcia musí fungovať správne pre akýkoľvek vstupný uhol (pozri Tip 3.)

Definícia: \[ sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \dots = \sum_{n=0}^\infty \frac{(-1)^n x^{2n+1}}{(2n+1)!} \qquad (1) \] \[ cos x = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \dots = \sum_{n=0}^\infty \frac{(-1)^n x^{2n}}{(2n)!} \qquad (2) \]

Tip 1: Samozrejme, že nemôžete počítať súčet nekonečného radu. Vidíte (ak nie, tak si pozrite v programe), že členy sa stále zmenšujú, takže isto raz nastane taká situácia, že keď pripočítate ďalší člen, výsledok to už nijako nezmení (viď úloha 1.3 - strojové epsilon).

Výpočet však môžete výpočet skončiť ešte skôr - keď sa výsledok v dvoch po sebe idúcich iteráciach zmení o menej ako epsilon (vopred zadané, dostatočne malé číslo).

Tip 2: Je dôležité uvedomiť si, že epsilon nevyjadruje presnosť vypočítanej aproximácie.

Tip 3: Uvedomte si, že uvedené rady aproximujú dobre len v okolí nuly (na obrázku vpravo vidíte priebeh funkcie sin a jej aproximácie troma členmi radu). Použite preto výpočet podľa (1), resp. (2) len na intervale \( < -\frac{\pi}{2}, \frac{\pi}{2} > \) alebo ešte lepšie \( < -\frac{\pi}{4}, \frac{\pi}{4} > \). Pre ostatné argumenty využite teoretické vzťahy medzi sin, cos a periodicitou týchto funkcií.
Uhly treba zadávať v radiánoch. Ak chcete mať argument v stupňoch, zapíšte ho takto (napr. pre vypočet \( \sin(30°) \): sinus(30 * pi/180, 0.01);

Zdroj: "Trigonometric functions -- series definition." Wikipedia, The Free Encyclopedia. wikipedia.org

Úloha 17 (4b)

Napíšte program na výpočet kontrolnej sumy (checksum) pre zadaný riadok tzv. IntelHex súboru.

Definícia: Kontrolný súčet sa vypočíta ako dvojkový doplnok súčtu jednotlivých bajtov od začiatku riadku až po kontrolný súčet.

Príklad:
Ak zadáte tento reťazec:

     :10010000214601360121470136007EFE09D21901XX

Musí vám vyjsť namiesto XX kontrolný súčet 40.

Splnenie úlohy demonštrujte výpočtom kontrolných súm napr. pre tieto reťazce:

     :100010000C9445000C9445000C9445000C944500xx
     :100020000C9445000C9445000C9445000C944500xx
     :100030000C9445000C9445000C9445000C944500xx
     :100040000C9445000C9445000C9445000C944500xx

Zdroje:


Valid HTML 4.01 Transitional Valid CSS!