460-2022/01 – Seminář z programování (SPR)

Garantující katedraKatedra informatikyKredity4
Garant předmětudoc. Ing. Zdeněk Sawa, Ph.D.Garant verze předmětudoc. Ing. Zdeněk Sawa, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostvolitelný odborný
Ročník3Semestrzimní
Jazyk výukyčeština
Rok zavedení2010/2011Rok zrušení2020/2021
Určeno pro fakultyFEIUrčeno pro typy studiabakalářské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Klasifikovaný zápočet 0+2
kombinovaná Klasifikovaný zápočet 0+10

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.

Způsob průběžné kontroly znalostí během semestru

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

Další požadavky na studenta nejsou kladeny.

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

1. Úvod. Časová složitost. Asympytotická notace. 2. Datové struktury. 3. Rekurzivní algoritmy. 4. Dynamické programování. 5. Greedy algoritmy. 6. Grafové algoritmy. 7. Grafové algoritmy (pokrač.). 8. Teorie čísel. 9. Kombinatorika. 10. Hry. 11. Permutace a jejich použití při řešení hlavolamů. 12. Výpočetní geometrie.

Podmínky absolvování předmětu

Kombinovaná forma (platnost od: 2010/2011 zimní semestr, platnost do: 2018/2019 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Klasifikovaný zápočet Klasifikovaný zápočet 100  51
Rozsah povinné účasti: účast na alespoň 4 tutoriálech

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramOborSpec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2018/2019 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 3 volitelný odborný stu. plán
2018/2019 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 3 volitelný odborný stu. plán
2018/2019 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2018/2019 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 3 volitelný odborný stu. plán
2018/2019 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 3 volitelný odborný stu. plán
2018/2019 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 3 volitelný odborný stu. plán
2018/2019 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2018/2019 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 3 volitelný odborný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 3 volitelný odborný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 3 volitelný odborný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 3 volitelný odborný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 3 volitelný odborný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 3 volitelný odborný stu. plán
2017/2018 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 3 volitelný odborný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 3 volitelný odborný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 3 volitelný odborný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 3 volitelný odborný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 3 volitelný odborný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 3 volitelný odborný stu. plán
2016/2017 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 3 volitelný odborný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 3 volitelný odborný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 3 volitelný odborný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 3 volitelný odborný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 3 volitelný odborný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 3 volitelný odborný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 3 volitelný odborný stu. plán
2015/2016 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 3 volitelný odborný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 3 volitelný odborný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 3 volitelný odborný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 3 volitelný odborný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 3 volitelný odborný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2014/2015 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 3 volitelný odborný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 3 volitelný odborný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 3 volitelný odborný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 3 volitelný odborný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 3 volitelný odborný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 3 volitelný odborný stu. plán
2013/2014 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 3 volitelný odborný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 3 volitelný odborný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 3 volitelný odborný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 3 volitelný odborný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 3 volitelný odborný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 3 volitelný odborný stu. plán
2012/2013 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 3 volitelný odborný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 3 volitelný odborný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 3 volitelný odborný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 3 volitelný odborný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 3 volitelný odborný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 3 volitelný odborný stu. plán
2011/2012 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 3 volitelný odborný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 3 volitelný odborný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 3 volitelný odborný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 3 volitelný odborný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 3 volitelný odborný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 3 volitelný odborný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2010/2011 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 3 volitelný odborný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku