Dátové štruktúry a algoritmy

Vitajte, na stránke predmetu Dátové štruktúry a algoritmy.

Tento predmet je vyučovaný v letnom semestri pre študentov 1. ročníka na Paneurópskej vysokej škole.

Na tejto stránke nájdete všetky materiály, ktoré sú potrebné pre štúdium predmetu ako:

Priebeh predmetu

• Úvod do jazyka C++
• Triedy, abstraktné dátové typy
• Dátové štruktúry - zásobník, zoznam, fronta, strom, graf
• Triediace algoritmy
• Vyhľadávacie algoritmy
  • stromy
  • grafy
• Zložitosť a optimalizácia algoritmov
• Bonus: Git, Dokumentácia, Testovanie

Podmienky absolvovania

• 40 bodov počas semestra
  • 2 zadania na vypracovanie po 20 bodov
  • na vypracovanie bude 7 dní (s možnosťou predĺženia)
  • 1. zadanie na cvičení v 5. týždni semestra,
  • 2. zadanie na cvičení v 10. týždni semestra
• 60 bodov skúška - praktická, zadanie na programovanie
• Pre úspešné absolvovanie predmetu je potrebné:
  • odovzdať obe zadania
  • získať 20 bodov zo zadaní počas semestra
• Výsledná známka bude určená na základe platnej klasifikačnej stupnice PEVŠ

Sylabus predmetu

• Vysoká škola: Paneurópska vysoká škola

• Fakulta: Fakulta informatiky

• Kód predmetu: BIAX10031

• Názov predmetu: Dátové štruktúry a algoritmy

• Druh, rozsah a metóda vzdelávacích činností:

  • prednáška 2 hod. týždenne / 24 hod. za semester štúdia (prezenčná metóda)
  • cvičenie 2 hod. týždenne (prezenčná metóda)

• Počet kreditov: 6

• Odporúčaný semester/trimester štúdia: 1. ročník, 2. semester

• Stupeň štúdia: 1.

• Podmieňujúce predmety: žiadne

• Podmienky na absolvovanie predmetu:

  • priebežné testy a semestrálne zadania - 40 %
  • záverečná písomná skúška - 60 %

Študent získa základné poznatky nielen o abstrakcii údajov, abstraktných údajových typoch, ale aj o základných štruktúrach údajov akými sú zásobník, fronta a pod., ich definícii a rôznych možnostiach ich implementácie. Okrem toho predmet obsahuje základy analýzy algoritmov, najmä algoritmov usporiadania, triedenia, vyhľadávania a tiež rekurzie.

Stručná osnova predmetu

1. Abstrakcia údajov, abstraktné údajové typy, špecifikácia a implementácia abstraktných údajových typov, ich inicializácia.
2. Úvod do štruktúr údajov, údajové typy a údajové štruktúry, prehľad štruktúr údajov: reťazec, zásobník, fronta, pole, tabuľka, množina, zoznam, strom, graf.
3. Návrh a implementácia abstraktných údajových typov, implementácia údajových štruktúr: reťazec, zásobník, fronta, pole, tabuľka, množina.
4. Smerníky a dynamické údaje, typ smerník, pojem dynamického údaju, prideľovanie a uvoľňovanie dynamickej pamäte, dynamické programovanie.
5. Zreťazene zoznamy, implementácia pomocou poľa, dynamická implementácia, dvojmo zreťazené zoznamy, kruhové zoznamy, stromy a grafy.
6. Rekurzia: definícia, rekurzívne funkcie, nekonečná rekurzia, implementácia rekurzie, otázka zložitosti rekurzie.
7. Analýza zložitosti algoritmov. Pamäťová a operačná zložitosť algoritmov.
8. Klasifikácia algoritmov usporiadania (triedenia). Algoritmy usporiadania s kvadratickou operačnou zložitosťou.
9. Algoritmy usporiadania zložitosti n log n, špeciálne algoritmy triedenia.
10. Vyhľadávací problém, jednosmerne adresné vyhľadávanie.
11. Jednosmerné asociatívne vyhľadávanie, vyhľadávacie stromy, vyhľadávanie vzoru v texte.
12. Viacrozmerne vyhľadávanie, viacrozmerne vyhľadávacie stromy, algoritmy prehľadávania s návratom.

Odporúčaná literatúra:

• RILEY, D D; HEADINGTON, M R. Data Abstraction and Structures using C++. Lexington Massachusetts: D. C. Heath and Company, 1994. ISBN 0-669-29220-6.
• LEISERSON, CH E; RIVEST, R L; CORMEN, T H. Introduction to Algorithms. Massachusetts: MIT Press, 2001. ISBN 0-262-53196-8.

Bodové hodnotenie