460-2022/03 – Seminář z programování (SPR)
Garantující katedra | Katedra informatiky | Kredity | 4 |
Garant předmětu | doc. Ing. Zdeněk Sawa, Ph.D. | Garant verze předmětu | doc. Ing. Zdeněk Sawa, Ph.D. |
Úroveň studia | pregraduální nebo graduální | Povinnost | volitelný odborný |
Ročník | 3 | Semestr | zimní |
| | Jazyk výuky | čeština |
Rok zavedení | 2019/2020 | Rok zrušení | |
Určeno pro fakulty | FEI | Určeno pro typy studia | bakalářské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Po zvládnutí předmětu studenti budou schopni navrhovat a implementovat co nejefektivnější algoritmy pro řešení různých úloh, umět posoudit výpočetní složitost algoritmů a při řešení problémů umět využívat různé programovací techniky, jako například dynamické programování, greedy algoritmy a různé metody prohledávání. Rovněž budou seznámeni s algoritmy pro řešení některých klasických kombinatorických problémů. Jedním z cílů předmětu je i příprava studentů na ACM soutěž v programování. Z tohoto důvodu bude kladen důraz na implementaci algoritmů v jazycích C/C++ a Java.
- znalost různých programovacích technik, používaných při návrhu algoritmů
- schopnost posoudit výpočetní složitost algoritmů
- schopnost efektivně implementovat navržené algoritmy
Vyučovací metody
Semináře
Projekt
Anotace
Předmět je věnován návrhu, analýze a implementaci algoritmů s důrazem na hledání co nejefektivnějších algoritmů z hlediska výpočetní složitosti. Cílem kurzu je seznámit studenty s různými technikami, které jsou standardně používány při návrhu algoritmů, jako například dynamické programování, greedy algoritmy nebo různé metody prohledávání stavového prostoru, přičemž použití těchto technik je ilustrováno na řadě problémů z různých oblastí informatiky.
Povinná literatura:
- Sawa Z.: Seminář z programování - prezentace k předmětu, dostupná na adrese http://www.cs.vsb.cz/sawa/spr/spr.pdf
Doporučená literatura:
- Skiena, S. S., Revilla, M. A.: Programming Challenges: The Programming Contest Training Manual, Springer, 2003.
- Cormen, T. H., Leiserson, R. L., Rivest, R. L., Stein, C.: Introduction to Algorithms, MIT Press 2001.
- Dasgupta, S., Papadimitriou, C., Vazirani, U.: Algorithms, McGraw-Hill, 2006.
- Skiena, S. S.: The Algorithm Design Manual, Springer, 1998.
- Knuth, D. E.: The Art of Computer Programming, Volumes 1-3, (2nd edition), Addison-Wesley Professional, 1998.
- Graham, R. L., Knuth, D. E., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Professional, 1994.
- Sedgewick, R.: Algoritmy v C, SoftPress s.r.o., 2003.
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Podmínkou udělení zápočtu je aktivní práce na cvičení a získání alespoň 51 bodů za vyřešené problémy. (Pozn.: Část bodů může student získat i problémy vyřešené v rámci soutěže v programovaní CTU Open). Studenti by měli při řešení problémů prokázat schopnost samostatně nalézat a implementovat vhodné algoritmy pro zadané úlohy.
E-learning
Další požadavky na studenta
Na studenta nejsou kladeny žádné další požadavky.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Náplň přednášek:
1. Úvod. Časová složitost. Asymptotická notace.
2. Datové struktury.
3. Rekurzivní algoritmy.
4. Greedy algoritmy.
5. Dynamické programování.
6. Dynamické programování (pokrač.).
7. Grafové algoritmy.
8. Grafové algoritmy (pokrač.).
9. Teorie čísel.
10. Kombinatorika.
11. Hry.
12. Permutace a jejich použití při řešení hlavolamů.
13. Výpočetní geometrie.
Náplň cvičení:
(Pozn.: Témata cvičení odpovídají tématům přednášek.)
1. Úvod. Časová složitost. Asymptotická notace.
2. Datové struktury.
3. Rekurzivní algoritmy.
4. Greedy algoritmy.
5. Dynamické programování.
6. Dynamické programování (pokrač.).
7. Grafové algoritmy.
8. Grafové algoritmy (pokrač.).
9. Teorie čísel.
10. Kombinatorika.
11. Hry.
12. Permutace a jejich použití při řešení hlavolamů.
13. Výpočetní geometrie.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky