Úvod do programování

katis.cs.vsb.cz

Seznam studentů kombinovaného studia

Informace ke zkoušce: Zkouška se skládá z písemné a ustní části. Písemná zkouška obsahuje 5 příkladů (algoritmy, datové struktury, složitosti). Ústni část je možné vykonat pouze v týdnu kdy byla vykonána část písemná. Ústní část se skládá z konzultace části pisemné a dalších dvou otázek.
Další termíny budou přidány později.

Upozornění: Přednáška dne 10.5.2005 se koná v místnosti B1, 13:00-14:30. Další přednášky se konají v sálu Vesmír v obvyklém čase.

Instrukce k projektům se nechází zde.

Cílem kurzu je seznámit studenty se základy algoritmizace. Kromě základních pojmů budou prezentovány algoritmy třídění a vyhledávání, lineární i nelineární datové struktury, vyhledávání v textu a komprimace dat. Na cvičení budou studenti algoritmy implementovat a své znalosti si prověří v rámci semestrálních projektů.

V rámci kurzu Úvod do programování budou studenti vypracovávat dva semestrální projekty. První projekt bude sloužit pro ověření zda je student schopen implementovat a ladit jednoduchý algoritmus. Tento projekt je hodnocen maximálním počtem bodů 10. Zadání si studenti mohou vybrat od prvního cvičení, termín odevzdání je konec 6. týdne, tedy 3.4.2005 ve 24:00.

Problémy implementované v rámci 2. projektu budou komplikovanější a od studentů se bude požadovat jejich implementační i algoritmické zvládnutí. Projekt bude umožňovat rozumné vstupy (např. stadartní vstup) a výstupy (např. standartní výstup). Tento projekt je hodnocen maximálním počtem bodů 30. Zadání si studenti mohou vybrat od 6. cvičení, termín odevzdání je předposlední týden v semestru, tedy 22.5.2005 ve 24:00.

Podmínkou zápočtu je odevzdání obou projektů a zisku minimálního počtu bodů 21 (ze 40 možných). Případný zápočet bude udělen po ústní konzultaci 2. projektu, která bude probíhat v zápočtovém týdnu.


Prezentace


Zadání k 1. projektu

Lineární Datové struktury
1.Implementuje zásobník pomocí pole.
2.Implementuje pole pomocí zásobníku.
3.Implementujte zásobník pomocí fronty.
4.Implementujte frontu pomocí zásobníku.
5.Implementujte frontu pomocí pole.
6.Implementujte pole pomocí fronty.
7.Implementujte obousměrný seznam.
8.Pomocí zásobníku implementujte algoritmus, který zjistí zda posloupnost znaků má tvar xCy, kde x je posloupnost z písmen A a B, y je opačná posloupnost k x. Např. x=AAABAB, y=BABAAA. Při čtení posloupnosti můžeme číst pouze následující symbol posloupnosti.
9.Je dána posloupnost skládající se ze závorek kulatých ( a ), hranatých [ a ] a složených { a }. Napište program, který určí, zda je posloupnost správně ozávorkována. Např. ({}[()]) je správně ozávorkovaná posloupnost, zatímco posloupnost [(] je nesprávná.
10. Napište algoritmus který bude generovat slova, která se čtou zleva i zprava stejně (např. oko, radar). Načtěte první polovinu řetězce z klávesnice (napr. RAD), po jejím načtení se automaticky doplní zbytek (např. AR). Tuto úlohu rozšiřte i na slovní spojení (kobyla ma maly bok). Umístění mezer v tomto případě nelze ovlivnit.
Třídící algoritmy
11.Přihrádkového třídění
12.Lexikografické třídění
13.Třídění vkládáním
14.ShellSort
15.RadixSort
16.Třídění výběrem
17.Bublinkové třídění
18.ShakerSort
19.Třídění binárním vkládáním
20.DobSort
21.QuickSort
Ostatní
22.Na vstupu jsou dvě data tj. den, mesíc a rok prvního datumu a den, měsíc a rok druhého datumu. Váš program určí které datum bylo dříve (prípadne vypíše, že data jsou shodná). Dále program pro oba zadané roky, jestli byl či nebyl přestupný. Pozor, pro určení přestupného roku nestačí jen dělitelnost 4!
Lineární datové struktury 2
23.Implementace pole s binární vyhledáváním.
24.Implementace dynamického pole pomocí pole.
25.Implementace dynamického zásobníku pomocí pole.
26.Implementace dynamického zásobníku pomocí seznamu.
27.Implementace dynamické fronty pomocí pole.
28.Implementace dynamické fronty pomocí seznamu.

Zadání k 2. projektu

Lineární datové struktury
1.Implementace dynamického perzistentního pole s binárním vyhledáváním.
2.Implementace dynamického perzistentního zásobníku.
3.Implementace dynamické perzistentní fronty.
4.Implementace perzistentního dynamického seznamu.
Třídící algoritmy
5.Přihrádkového třídění, Lexikografické třídění.
6.Třídění řetězců různé délky.
7.Třídění vkládáním, ShellSort.
8.RadixSort, třídění výběrem.
9.Bublinkové třídění, ShakerSort.
10.Bublinkové třídění, DobSort.
11.Nerekurzivní varianta QuickSort s dynamickým zásobníkem.
12.QuickSort kombinovaný s algoritmem přímého vkládání.
13.Heapsort.
14.Mergesort.
Nelineární datové struktury
15.Binární vyhledávácí stromy (2 studenti)
16.AVL stromy (2 studenti)
17.2-3-4 stromy (2 studenti)
18.Red-black stromy (2 studenti)
19.Vyhledávácí Trie (2 studenti)
20.Ternární stromy (2 studenti)
20,5Neperzistentní B-strom (2 studenti)
Hashování
21.Hashovací tabulka - sepárátní řetězení, hashovací funkce.
22.Hashovací tabulka - otevřené adresování.
23.Implementace jednoduché diskové cache (2 studenti).
Prostorové datové struktury
24.Neperzistentní kvandrantový strom (2 studenti).
25.Neperzistentní UB-strom (2 studenti).
26.Neperzistentní R-strom (2 studenti).
Vyhledávání v textu
27.Elementární algoritmus.
28.Morris-Pratův algoritmus.
29.Knuth-Morris-Pratův algoritmus.
30.Karp-Rabinův algoritmus.
Komprimace dat
31.Napište program pro kódování a dekódování zadaného binárního souboru, které spočívá v nahrazení n-tic následujících shodných znaků vhodným escape kódem a počtem výskytů (RLE).
Lineární algebra
32.Napište program, který určí (pomocí tzv. Eratosthenova síta) kolik prvočísel se nachází v daném intervalu <1,...,N> a vypište je.
33.Operace s maticemi: sčítání, odčítání, násobení skalárem.
34.Operace s maticemi: násobení, transponování matic.
35.Výpočet inverzní matice, řešení soustav (2 studenti).
36.Implementujte program pro výpocet řešení soustavy lineárních rovnic Gaussovou eliminační metodou.
37.Skalární součin vektorů, norma vektoru, euklidovská vzdálenost.
38.Výpočet determinantu matice.
39.Implementace řídké matice (CRS), operace.
40.Implementace řídké matice (CCS), operace.

Literatura

Ukázky kódu