Algoritmizace a programování
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
F7ABBALP | KZ | 4 | 2P+2C | anglicky |
- Garant předmětu:
- Pavel Smrčka
- Přednášející:
- Lenka Hanáková, Christiane Malá, Pavel Smrčka, Tomáš Veselý
- Cvičící:
- Lenka Hanáková, Christiane Malá, Pavel Smrčka, Tomáš Veselý
- Předmět zajišťuje:
- katedra informačních a komunikačních technologií v lékařství
- Anotace:
-
Pojem algoritmus, způsoby zápisu algoritmů, základní řídicí a datové struktury. Proměnné, identifikátory, datové typy. Přiřazovací příkaz, podmíněný příkaz, větvení, cykly. Aritmetické a logické operace. Číslicová reprezentace datových typů, číselné soustavy. Rekurzivní a iterační postupy, posuzování kvality algoritmu, abstraktní datové typy (zásobník, fronta, seznam, množina, strom). Metody třídění a vyhledávání dat. Přehled základních numerických algoritmů - numerická derivace a integrace, metody lineární algebry, interpolace a aproximace funkcí, řešení rovnic iteračními metodami, metoda nejmenších čtverců. Ideový úvod do zpracování biomedicínckých dat z pohledu programátora, algoritmus FFT. Stručný úvod do strukturovaného programování v jazyce C a C++; integrované vývojové prostředí, stavební prvky programu, struktura jednoduchých programů, princip tvorby uživatelských funkcí, princip práce se soubory, přidělování paměti. Základy tvorby grafického uživatelského rozhraní. Úvod do objektově orientovaného programování v C++. Ladění programů. Základní principy softwarového inženýrství.
- Požadavky:
-
Povinná účast na cvičeních, realizace průběžných úloh s minimálním ziskem 20 bodů (maximum 40), absolvování testů s celkovým minimálním ziskem 30 bodů (maximum 60). Celkové hodnocení: 50-59 bodů = E (3), 60-69 bodů = D (2.5), 70-79 bodů = C (2), 80-89 bodů = B (1.5), 90-100 bodů = A (1)
- Osnova přednášek:
-
1. Algoritmus: intuitivní zavedení pojmu, vymezující vlastnosti. Algoritmizace úlohy: způsoby zápisu algoritmu (slovní popis, graficky, v programovacím jazyce), pojem „procesor“, pojem „program“. Etapy řešení problému. Příklady slovního popisu algoritmů. Grafický zápis algoritmů - datové a řídicí struktury vývojových diagramů - část 1. Jednoduchá proměnná, identifikátor proměnné. Základní datové typy - celá čísla a čísla v plovoucí řádové čárce. Přiřazovací příkaz, příkaz vstupu a výstupu. Výrazy a operátory. Složené příkazy: sekvence a selekce.
2. Grafický zápis algoritmů - část 2. Pole proměnných, vektory, matice. Logická proměnná, znaky a řetězce. Větvení, cykly (indukční, iterační). Členění kódu, podprogramy, funkce. Trasovací tabulka.
3. Úvod do číselných soustav: reprezentace celých čísel, rozsahy datových typů. Výlet do historie informačních technologií. Programátorský model moderního počítačového systému. Přehled současných vyšších programovacích jazyků.Úvod do jazyka C - přepis elementárních řídicích a datových struktur vývojových diagramů do jazyka C. Bloky, deklarace a inicializace proměnné. Struktura jednoduchých programů v jazyce C - příklady krátkých programů v C.
4. Fáze vývoje programů v jazyce C - editace zdrojového kódu, kompilátor, linker. Integrované vývojové prostředí, ladění programu. Syntaktické a sémantické chyby.Výrazy, operátory, přiřazení. Data - typy, proměnné, deklarace. Řídicí struktury - příkazy: výrazový příkaz, blok, podmíněný příkaz, přepínač, příkazy cyklu, příkaz skoku.
5. Odvozené datové typy - struktura, sjednocení, ukazatel, pole. Uživatelem definované typy. Příklady použití. Podprogramy, rozklad kódu. Standardní knihovní funkce, uživatelem definované funkce. Předávání parametrů hodnotou a pomocí ukazatelů.
6. Řízení preprocesoru jazyka C: vkládání souborů, expanze maker, podmíněný překlad. Debugger, krokování programu, sledování proměnných. Práce se soubory: soubory textové a binární, proudy, otevírání a zavíraní souboru, strukturovaný zápis do souboru, čtení ze souboru.
7. Dynamické přidělování paměti, ukazatele na složené datové typy. Předávání ukazatelů na složené datové typy jako parametry funkcí. Projekt. Práce s více moduly zdrojového kódu. Prototypy funkcí, hlavičkové soubory. Oddělená kompilace jednotlivých modulů, stromová struktura projektu, závislosti. Tvorba vlastních knihoven funkcí.
8. Rekurzivní a iterační algoritmy, vzájemná konverze. Dekompozice úlohy. Programátorská metoda „rozděl a panuj“. Příklady aplikace.Posuzování kvality algoritmu. Požadavky na paměť a na rychlost výpočtu. Funkcečasové náročnosti algoritmu, asymptotická složitost.
9. Složitější datové typy a operace s nimi: zásobník, fronta, spojový seznam (obousměrný i jednosměrný), množina, strom (prohledávání do hloubky a do šířky). Třídění: vlastnosti metod (stabilita, přirozenost, vnější a vnitřní třídění, třídění in situ), princip a srovnání základních algoritmů Selection sort, Insertion sort, Bubble sort, Shaker sort, Quick sort, Shell sort a Heap sort.
10. Vyhledávání. Adresní a asociativní algoritmy, jednorozměrné vyhledávání. Elementární vyhledávací metody: sekvenční vyhledávání, vyhledávání binárním půlením, interpolační vyhledávání, Hoarův algoritmus. Binární rozhodovací stromy. Numerické algoritmy I. Výpočet hodnot funkcí. Hornerovo schéma. Základní metody numerické derivace a integrace. Interpolace. Aproximace metodou nejmenších čtverců.
11. Numerické algoritmy II. Algebraické a transcendentní rovnice, iterační metody - půlení intervalu, metoda sečen, Newtonova metoda, Birge-Vietova metoda, Linova a Bairstowova metoda. Numerické algoritmy III. Sčítání, odčítání matic a násobení matic, transpozice, inverze, výpočet determinantu. Gaussova eliminační metoda. Řešení soustav lineárních rovnic.
12. Úvod do zpracování biomedicínských dat z pohledu programátora: rámcový přehled metod. Statistické výpočty, časová oblast, trendy, vyhlazování. Algoritmus rychlé Fourierovy transformace. Aplikační a systémové programy. Funkce operačního systému z pohledu aplikačního programátora. Přehled typických současných operačních systémů na platformě PC (Windows, GNU/Linux). Využití služeb operačního systému Windows a Unix.
13. Úvod do objektově orientovaného programování (OOP) v jazyce C++. Datová abstrakce, zapouzdření, instance, objekt. Třída a její členy - konstruktor, destruktor, přetížení, soukromé a veřejné metody. Dědičnost, polymorfismus. Příklad aplikace v C++.
14. Grafické uživatelské rozhraní (GUI). Událostmi řízené programování. Běžné komponenty GUI. Přehled knihoven pro tvorbu GUI: MFC, GTK+, Qt, Winforms. Základy tvorby GUI v multiplatformní knihovně GTK+.
- Osnova cvičení:
-
1. Slovní zápis algoritmů. Grafický zápis algoritmů -vývojové diagramy - proměnná, data, výraz, přiřazovací příkaz. Sekvence. Vstup a výstup.2. Logický výraz, podmíněný příkaz, větvení programu. Trasovací tabulka.
2. Typizované cykly: s podmínkou před tělem, za tělem, s pevným počtem opakování. Převod obecného cyklu na typizovaný. Jednorozměrná a dvourozměrná pole. Číselné soustavy - převody, základní operace.
3. Seznámení s integrovaným vývojovým prostředím pro jazyk C, kompilace a ladění ukázkového programu. Syntaktické versus sémantické chyby. Přepis elementárních algoritmů do jazyka C: funkce pro vstup z klávesnice a textový výstup na obrazovku, přiřazovací příkaz, sekvence.
4. Větvení programu v jazyce C - podmíněný příkaz a přepínač. Cykly v jazyce C - while, do-while, for. Příkaz skoku. Ukazatele. Odvozené a uživatelem definované typy, příklady použití. Dynamické přidělování paměti.
5. Tvorba podprogramů: uživatelem definované funkce, ukázky předávání parametrů hodnotou a ukazatelem. Ukázky fungování preprocesoru, podmíněný překlad, vkládání obsahu souborů.
6 Praktické základy práce se soubory: otevírání, zavírání, načítání a zápis strukturovaných dat. Rozdělení zdrojového kódu do více modulů, oddělená kompilace. Tvorba knihovny funkcí a hlavičkového souboru.
7. Využití stávajícího kódu v projektu. Vlastní tvorba a praktické využití knihoven v jazyce C. Příklad rekurzivního výpočtu. Převod na iterační postup, porovnání obou přístupů.
8. Kontrolní bod 1 (test) a jeho vyhodnocení.
9. Ukázka a využití zdrojového kódu knihovny pro základní metody třídění dat. Úpravy a porovnání jednotlivých algoritmů. Sekvenční, binární a interpolační vyhledávání - modifikace a použití zdrojového kódu. Odhad časové složitosti algoritmu. Měření časové náročnosti úseku programu.
10. Příklad použití binárního rozhodovacího stromu. Ukázka výpočtu hodnot funkcí. Hornerovo schéma.Ukázka algoritmů numerické derivace a integrace. Interpolace a aproximace funkcí a experimentálních dat. Metoda nejmenších čtverců.
11. Iterační metody hledání kořenů rovnic - ukázka a srovnání elementárních metod. Statistické výpočty na biomedicínckých datech, výpočet spektra pomocí algoritmu rychlé fourierovy transformace.
12. Ukázky využití služeb operačního systému v aplikačním programu. Tvorba objektově orientovaného programu v C++, vlastní definice a použití třídy.
13. Ukázka událostmi řízeného programu s grafickým uživatelským rozhraním sestaveným pomocí knihovny GTK.
14. Kontrolní bod 2(test) a jeho vyhodnocení, udělení klas. zápočtu.
- Cíle studia:
-
Osvojení praktických základů (pojmů, postupů a prostředků) algoritmizace se zaměřením na oblast biomedicínského inženýrství. Osvojení základních programátorských technik, nezbytných pro pochopení vnitřního fungování moderních softwarových systémů. Důraz bude kladen na praktickou a samostatnou aplikaci nejpoužívanějších algoritmů, bezprostředně využitelných v biomedicínckém inženýrství. Během výuky se student naučí specifikovat algoritmickou úlohu, provést její analýzu, dekompozici, navrhnout, implementovat a odladit jednoduché řešení. Platforma použitá k výkladu a k řešení úloh je ISO C resp. C++. Studenti mohou využívat např. integrované vývojové prostředí BloodshedDevC++ nebo CodeBlockspro nebo jakýkoliv produkt, kompatibilní s ISO C/C++. Obsah předmětu je strukturován tak, aby byly nabyté znalosti využitelné v navazujících předmětech na FBMI ČVUT, zaměřených na informační technologie.
- Studijní materiály:
-
Výukové materiály pro tento předmět jsou zveřejněny prostřednictvím e-learningového systému na adrese <a href="https://moodle-vyuka.cvut.cz">https://moodle-vyuka.cvut.cz</a>
[1] Wroblewski, S.: Algoritmy, Datové struktury a programovací techniky, ComputerPress, Brno 2004
[2] Kadlec: Učíme se programovat v jazyce C, ComputerPress, Praha 2002
[3] Sedgewick, J.: Algoritmy v C, SoftPress, Praha 2005
[4] Herout: Učebnice jazyka C (IV. vydání), KOPP, České Budějovice 2004
[5] Corman et al.: Introduction to Algorithms, The MIT Press, 2nd edition 2001
[6] Goodrich et al: Algorithm Design - Foundations, Analysis, and Internet Examples, John Wiley & Sons, New York 2002
- Poznámka:
- Další informace:
- Výukové materiály pro tento předmět jsou zveřejněny prostřednictvím e-learningového systému na adrese <a href="https://moodle-vyuka.cvut.cz">https://moodle-vyuka.cvut.cz</a>
- Rozvrh na zimní 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á - Rozvrh na letní semestr 2024/2025:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů:
-
- Prospectus - bakalářský (!)
- Bakalářský studijní program Biomedicínská technika v aj (povinný předmět)
- Bakalářský studijní program Biomedicínská technika v aj (povinný předmět)