Jste zde

17PBIALP - Algoritmizace a programování

Kód Zakončení Kredity Rozsah Jazyk výuky
17PBIALP Z,ZK 5 2P+2C česky
Předmět je ekvivalentem v KFS pro:
17KBIALP
Garant předmětu:
Přednášející:
Cvičící:
Předmět zajišťuje:
katedra biomedicínské informatiky
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.

(CVIČENÍ BYLO INOVOVÁNO V RÁMCI PROJEKTU RPAPS 2016)

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.

(CVIČENÍ BYLO INOVOVÁNO V RÁMCI PROJEKTU RPAPS 2016)

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ů.

(CVIČENÍ BYLO INOVOVÁNO V RÁMCI PROJEKTU RPAPS 2016)

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.

(CVIČENÍ BYLO INOVOVÁNO V RÁMCI PROJEKTU RPAPS 2016)

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 ISOC resp. C++. Studenti mohou využívat např. integrované vývojové prostředí BloodshedDevC++ , CodeBlocks 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="http://skolicka.fbmi.cvut.cz">http://skolicka.fbmi.cvut.cz</a>

Obsahuje veškeré podpůrné materiály: sylaby přednášek, náplně jednotlivých cvičení atd.

[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

Poznámka:
Předmět je součástí následujících studijních plánů:
Materiály ke stažení:

Přednášky - odkaz: 

VEŠKERÉ STUDIJNÍ MATERIÁLY (SYLABY PŘEDNÁŠEK, CVIČEBNÍ ÚLOHY ATD. JSOU ZVEŘEJNĚNY NA FAKULTNÍM E-LEARNINGOVÉM SERVERU NA ADRESE "skolicka.fbmi.cvut.cz", KURZ "Algoritmizace a programování". Přihlásit se lze na server pomocí uživatelského jména a hesla shodného s uživatelským jménem a heslem do fakultního emailu. Taktéž lze použít anonymní přístup přes uživatelské jméno "student" a heslo "student".

Níže jsou uvedené jsou pouze materiály ke cvičením inovovaným v rámci projektu RPAPS 2016 (tyto materiály jsou již rovněž zařazené do ostatních výukových materiálů na uvedeném e-learningovém serveru).

Dodatečné studijní materiály pro KFS: