Efektivní programování 2

Garant předmětu:

Martin Kačer

Přednášející:

Martin Kačer

Cvičící:

Martin Kačer

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Předmět navazuje na Efektivní programování 1 (ale jeho předchozí absolvování NENÍ NUTNÉ).

Studenti si prakticky ověří implementaci algoritmů a datových struktur na konkrétních slovně zadaných příkladech. Důraz je kladen nejen na návrh řešení, ale i na jeho korektní a efektivní implementaci, včetně ošetření všech okrajových podmínek. Studenti se naučí přemýšlet o různých variantách řešení, budou se snažit vybírat mezi nimi tu nejvýhodnější a vyhýbat se chybám při implementaci.

Požadavky:

BI-AG1, BI-EP1 (doporučeno), BI-AG2 (doporučeno absolvovat souběžně)

Osnova přednášek:

1. Mřížky a algoritmy spojené s mřížkami. Čtvercové matice, trojúhelníkové a šestiúhelníkové mřížky, jejich rozšíření do vyšších dimensí.

2. Řetězce, práce s řetězci, možnosti v Javě. Přesné a přibližné vyhledávání v řetězcích, protisměrné vyhledávání.

3. Základní grafové algoritmy: procházení grafů, nejkratší cesty.

4. Stavový prostor, metody ořezávání stavového prostoru, prohledávání stavového prostoru, prohledávání s návratem (backtracking).

5. Pokročilejší grafové algoritmy: toky v sítích, párování.

6. Operační složitost, pokročilé techniky jejího určování v průměrném případě. Kumulativní složitost.

7. Geometrie a výpočetní geometrie. Výpočty úhlů a konvexních obalů mnohoúhelníků, hledání nejkratších cest v prostoru s geometrickými objekty.

Osnova cvičení:

1. Mřížky, matice, trojúhelníkové a šestiúhelníkové mřížky.

2. Řetězce, práce s řetězci, přesné a přibližné vyhledávání.

3. Základní grafové algoritmy: procházení grafů, nejkratší cesty.

4. Stavový prostor, metody prohledávání a ořezávání.

5. Pokročilejší grafové algoritmy: toky v sítích, párování.

6. Operační složitost, pokročilé techniky jejího určování.

7. Geometrie a výpočetní geometrie.

Cíle studia:

V rámci předmětu se na praktických příkladech ukazuje, že kdokoli a

v jakémkoli programu může udělat chybu. Účelem je osvojit si techniky,

které pravděpodobnost chyb snižují, zejména naučit se navrhnout takové

řešení, které bude dostatečně efektivní, ale současně co nejméně náročné

na implementaci. Pokud chyby vzniknou, procvičují se dále způsoby ladění

programu.

Studijní materiály:

Steven S. Skiena, Miguel Revilla: Programming Challenges.

Jon Bentley: Programming Pearls.

Poznámka:

určeno pro pokročilé studenty

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/BI-EP2/

Další informace:

https://courses.fit.cvut.cz/BI-EP2/

Rozvrh na zimní semestr 2024/2025:

Rozvrh není připraven

Rozvrh na letní semestr 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St
Čt
Pá	místnost T9:302 Kačer M. 11:00–12:30 (přednášková par. 1) Dejvice NBFIT učebnamístnost T9:302 Kačer M. 12:45–14:15 (přednášková par. 1 paralelka 101) Dejvice NBFIT učebna

Předmět je součástí následujících studijních plánů:

• Bc. program Informatika, pro fázi studia bez oboru, 2015-2020 (volitelný předmět)
• Bc. obor Bezpečnost a informační technologie, 2015-2020 (volitelný předmět)
• Bc. obor Teoretická informatika, 2015-2020 (volitelný předmět)
• Bc. obor Počítačové inženýrství, 2015-2020 (volitelný předmět)
• Bc. obor Informační systémy a management, 2015-2020 (volitelný předmět)
• Bc. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, 2015-2020 (volitelný předmět)
• Bc. obor Webové a softwarové inženýrství, zaměření Webové inženýrství, 2015-2020 (volitelný předmět)
• Bc. obor Webové a softwarové inženýrství, zaměření Počítačová grafika, 2015-2020 (volitelný předmět)
• Bc. obor Znalostní inženýrství, 2018-2020 (volitelný předmět)
• Bc. specializace Informační bezpečnost, 2021 (volitelný předmět)
• Bc. specializace Manažerská informatika, 2021 (volitelný předmět)
• Bc. specializace Počítačová grafika, 2021 (volitelný předmět)
• Bc. specializace Počítačové inženýrství, 2021 (volitelný předmět)
• Bc. program, pro fázi studia bez specializace, 2021 (volitelný předmět)
• Bc. specializace Webové inženýrství, 2021 (volitelný předmět)
• Bc. specializace Umělá inteligence, 2021 (volitelný předmět)
• Bc. specializace Teoretická informatika, 2021 (volitelný předmět)
• Bc. specializace Softwarové inženýrství, 2021 (volitelný předmět)
• Bc. specializace Počítačové systémy a virtualizace, 2021 (volitelný předmět)
• Bc. specializace Počítačové sítě a Internet, 2021 (volitelný předmět)
• Study plan for Ukrainian refugees (volitelný předmět)
• Bc. specializace Informační bezpečnost, 2024 (volitelný předmět)
• Bc. program, pro fázi studia bez specializace, 2024 (volitelný předmět)
• Bc. specializace Manažerská informatika, 2024 (volitelný předmět)
• Bc. specializace Počítačová grafika, 2024 (volitelný předmět)
• Bc. specializace Softwarové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Webové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Počítačové sítě a Internet, 2024 (volitelný předmět)
• Bc. specializace Počítačové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Počítačové systémy a virtualizace, 2024 (volitelný předmět)
• Bc. specializace Umělá inteligence, 2024 (volitelný předmět)
• Bc. specializace Teoretická informatika, 2024 (volitelný předmět)
• Bc. specializace Počítačová grafika s vynecháním BI-SVZ (volitelný předmět)