460-2022/04 – 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ýukyangličtina
Rok zavedení2019/2020Rok zrušení
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 2+2

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.

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

Prezenční forma (platnost od: 2019/2020 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodůMax. počet pokusů
Klasifikovaný zápočet Klasifikovaný zápočet 100  51 3
Rozsah povinné účasti: Účast na cvičeních je povinná a je kontrolována. S rozsahem povinné účastí seznámí studenty garant předmětu na začátku semestru.

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP: Splnění všech povinných úkolů v individuálně dohodnutých termínech. Rozsah účasti na cvičeních si student na začátku semestru dohodne s garantem předmětu.

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2024/2025 (B0613A140010) Informatika P angličtina Ostrava 3 volitelný odborný stu. plán
2023/2024 (B0613A140010) Informatika P angličtina Ostrava 3 volitelný odborný stu. plán
2023/2024 (B0541A170009) Výpočetní a aplikovaná matematika P angličtina Ostrava 3 volitelný odborný stu. plán
2022/2023 (B0613A140010) Informatika P angličtina Ostrava 3 volitelný odborný stu. plán
2022/2023 (B0541A170009) Výpočetní a aplikovaná matematika P angličtina Ostrava 3 volitelný odborný stu. plán
2022/2023 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P angličtina Ostrava 3 volitelný odborný stu. plán
2021/2022 (B0613A140010) Informatika P angličtina Ostrava 3 volitelný odborný stu. plán
2021/2022 (B0541A170009) Výpočetní a aplikovaná matematika P angličtina Ostrava 3 volitelný odborný stu. plán
2021/2022 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P angličtina Ostrava 3 volitelný odborný stu. plán
2020/2021 (B0613A140010) Informatika P angličtina Ostrava 3 volitelný odborný stu. plán
2020/2021 (B0541A170009) Výpočetní a aplikovaná matematika P angličtina Ostrava 3 volitelný odborný stu. plán
2019/2020 (B0613A140010) Informatika P angličtina Ostrava 3 volitelný odborný stu. plán
2019/2020 (B0541A170009) Výpočetní a aplikovaná matematika P anglič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

Hodnocení Výuky

Předmět neobsahuje žádné hodnocení.