Algoritmizace a programování

Garant předmětu:

Pavel Smrčka

Přednášející:

Lenka Hanáková, 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 XP, 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 ANSI C resp. C++. Studenti mohou využívat např. integrované vývojové prostředí BloodshedDevC++ pro WindowsXP, postavené na GNU C (osvědčilo se při výuce) nebo jakýkoliv produkt, kompatibilní s ANSI 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:

https://moodle-vyuka.cvut.cz/

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	místnost KL:C-4 Smrčka P. 08:00–09:50 (přednášková par. 1) Kladno FBMI C4, Malý sál
Pá	místnost KL:B-435 Veselý T. 10:00–11:50 (přednášková par. 1 paralelka 4) Kladno FBMI Počítačová učebnamístnost KL:B-435 Veselý T. 12:00–13:50 (přednášková par. 1 paralelka 3) Kladno FBMI Počítačová učebna

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

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

• Bakalářský studijní program Biomedicínská technika (povinný předmět)
• Bakalářský studijní program Biomedicínská technika (povinný předmět)