456-0540/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í1999/2000Rok zrušení2009/2010
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:

- 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. - Skiena, S. S., Revilla, M. A.: Programming Challenges: The Programming Contest Training Manual, Springer, 2003. - 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

Prerekvizity

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

Korekvizity

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

Osnova předmětu

Cvičení: Úvod. Časová složitost. Asympytotická notace Datové struktury Práce s řetězci Prohledávání s návratem (backtracking) Dynamické programování Greedy algoritmy Prohledávání grafu Další grafové algoritmy Teorie čísel Kombinatorika Hry Permutace a jejich použití při řešení hlavolamů Výpočetní geometrie

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

Kombinovaná forma (platnost od: 2003/2004 zimní semestr, platnost do: 2010/2011 zimní 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 (100) 0
        Programy řešící zadané problémy Projekt 100  0
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2009/2010 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 3 volitelný odborný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 3 volitelný odborný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 3 volitelný odborný stu. plán
2009/2010 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 3 volitelný odborný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 3 volitelný odborný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 3 volitelný odborný stu. plán
2008/2009 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2008/2009 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 3 volitelný odborný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 3 volitelný odborný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 3 volitelný odborný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 3 volitelný odborný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 3 volitelný odborný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 3 volitelný odborný stu. plán
2007/2008 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2007/2008 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 3 volitelný odborný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 3 volitelný odborný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 3 volitelný odborný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 3 volitelný odborný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 3 volitelný odborný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 3 volitelný odborný stu. plán
2006/2007 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2006/2007 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 3 volitelný odborný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 3 volitelný odborný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 3 volitelný odborný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 3 volitelný odborný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 3 volitelný odborný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 3 volitelný odborný stu. plán
2005/2006 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2005/2006 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 volitelný odborný stu. plán
2004/2005 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2004/2005 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 volitelný odborný stu. plán
2003/2004 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2003/2004 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2003/2004 (B2612) Elektrotechnika a informatika (1801R001) Informatika P č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