Cvičenie č.1

Ciele
  1. Oboznámiť sa s organizáciu cvičení z predmetu Údajové štruktúry a algoritmy.
  2. Zvládnuť prácu v prostredí emulátora stroja RAM.
  3. Navrhnúť algoritmy a odladiť programy pre zadané úlohy s využitím emulátora stroja RAM.
Úvod
    Organizácia cvičení z predmetu Údajové štruktúry a algoritmy, podmienky získania zápočtu.
Postup
  1. Podmienky získania zápočtu z predmetu Údajové štruktúry a algoritmy stanovené v súlade so študijným poriadkom TU.
    Maximálne bodové hodnotenie aktivít počas semestra:
    • Praktická previerka - 8b
    • Písomná kontrola - 17b
    • Priebežné previerky - 5b
    Celkovo je možné počas semestra získať maximálne 30 bodov. Na udelenie zápočtu je tak nevyhnutné získať aspoň 16 bodov.

    Orientačný časový plán obsahovej náplne cvičení:

    1. Spôsob práce na cvičeniach, spôsob hodnotenia, návrh algoritmov a programovanie stroja RAM.
    2. Programovanie stroja RAM, určovanie zložitosti RAM programov.
    3. Vývojové prostredie Code::Blocks, ADT List (zoznam).
    4. ADT Stack (zásobník) a ADT Queue (front).
    5. ADT Tree (strom) a ADT Graph (graf).
    6. Prechádzanie stromov, rekurzia.
    7. Praktická previerka.
    8. Metódy návrhu efektívnych algoritmov.
    9. Triedenie.
    10. Triedenie.
    11. Implementácia ADT Set (množina) - hašovanie, stromové štruktúry údajov.
    12. Písomná kontrola.
    13. Vyhodnotenie.
    Poznámka: Dôraz je kladený na samostatnú prácu študenta na cvičení. Cieľom nie je opakovanie odprednášaných teoretických poznatkov cvičiacim, ich znalosť sa predpokladá. Úlohou cvičiaceho je poskytnutie konzultácií k riešeným úlohám.

    a) Praktická previerka - praktické programové riešenie zadanej úlohy na cvičení. Úloha tematicky nadväzuje na samostatne riešené úlohy na predošlých cvičeniach.

    b) Písomná kontrola - všeobecná kontrola nadobudnutých poznatkov (prednášky i cvičenia) a schopnosti ich aplikácie. Písomná forma.

    c) Priebežné previerky v bližšie neurčenom počte a termíne môže cvičiaci v rámci semestra zaradiť podľa vlastného uváženia, pre zvýšenie motivácie študentov k priebežnej príprave na cvičenia.

    Ak študent nezíska dostatočný počet bodov na udelenie zápočtu (súčet položiek a,b,c), má nárok zúčastniť sa opravnej kontroly. V rámci opravy, po splnení podmienok stanovených cvičiacim, je možný zisk zápočtu s minimálnym počtom bodov (t.j. 16b), v opačnom prípade študent stráca nárok na udelenie zápočtu.

    Poznámka: Podľa § 16 Študijného poriadku TU: (20) Preukázateľne zistené odpisovanie, použitie nedovolených pomôcok a pod. pri priebežnej alebo záverečnej kontrole štúdia rieši dozerajúci učiteľ na mieste návrhom skúšajúcemu na udelenie 0 %-ného výsledku za príslušnú kontrolu. Ak preukázateľne zisteným odpisovaním poruší študent právne predpisy fakulty, dopustí sa disciplinárneho priestupku podľa § 72 zákona.
  2. Oboznámte sa s emulátorom stroja RAM.
    Úloha: Preštudujte priloženú dokumentáciu. Zopakujte si jazyk stroja RAM.
    Poznámka: Venujte pozornosť zápisu programu pre emulátor. Aký je formát operandu skokových inštrukcií?

    Príklad: Navrhnite algoritmus a odlaďte program pre stroj RAM.

    Opis: Výpočet faktoriálu čísla n (n=>0).

    Vstup: n, Výstup: n!. 
    LOAD =1
STORE 2
STORE 3
READ 1
LOAD 1
JGTZ OK
JMP FIN
OK: LOAD 3
SUB 1
JZ FIN
LOAD 3
ADD =1
STORE 3
MUL 2
STORE 2
JMP OK
FIN: WRITE 2
HALT
    Výstup funkčného programu:

  3. Návrh algoritmov a ladenie programov pre stroj RAM.
    Úloha: Navrhnite algoritmus a odlaďte program pre stroj RAM.

    Opis: Nájdenie maximálneho prvku vstupnej postupnosti celých čísel. Dĺžka postupnosti n (n>0) je prvý vstupný údaj.

    Vstup: n,a1,a2,...,an, Výstup: max(a1,...,an).

    Výstup funkčného programu:

    Úloha: Navrhnite algoritmus a odlaďte program pre stroj RAM.

    Opis: Výpočet hodnoty 2n. Číslo n (n=>0) je vstupný údaj.

    Vstup: n, Výstup: 2n.

    Výstup funkčného programu:

comments powered by Disqus