Algoritmy pro inženýrskou informatiku

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

ústav přístrojové a řídící techniky

Anotace:

Základní pojmy: algoritmus, paralelismus, reentrance. Pojem programu a procesu. Zobrazení dat, 4GL, vizuální programování. Strukturované programování - strukturované příkazy, datové typy. Jazyk Pascal (Delphi): blok a jeho náležitosti, program, deklarace procedur a funkcí, parametry (funkcionální), příkazy jazyka, standardní procedury a funkce. Abstraktní datové typy: tabulka, zásobník, fronta, seznam, strom. Binární strom, AVL strom. Abstraktní operace a algoritmy: vyhledávání, třídění, interpolace, iterace, rekurze, backtracking.

Požadavky:

Ke zkoušce jsou předepsány znalosti v rozsahu přednášek.

Na cvičení studenti obdrží zadání 3 příkladů k vypracování.

Osnova přednášek:

Big-O notace.

Algoritmy s čísly - kryptografie, universální hashing, rozděl-a-panuj, rekurentní relace, mergesort, rychlá Fourierova transformace.

Hledání do hloubky v grafu s/bez vyznačení směru hran, silně vázané komponenty.

Cesty v grafu - vzdálenosti, prohledávání breadth-first, délka hran, Dijkstrův algoritmus, implementace fronty s prioritami, nejkratší cesta v grafu se zápornými délkami hran, nejkratší cesta v acyklicky směrovém grafu.

Žravé algoritmy - Minimum spanning trees, Huffmanovo kódování, Hornova formule.

Osnova cvičení:

Spouštění programů v učebně, konta a zadání úloh

Jednoduchý program

Číselné proměnné

Podmíněný příkaz. Timer.

Pole, cyklus, konstanty (i typované)

Texty, opendialog, a ...

Cykly, náhodné proměnné, třídění.

Druhé okno programu, další komponenty.

OnMouseMove, Canvas.

Canvas - psaní textů, obdélníky, graf funkce.

Tisk z programů v Delphi.

Dynamické datové struktury. Úspora místa, zásobník, fronta, řetěz, tabulka, strom.

Cíle studia:

Studijní materiály:

0. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani:Algorithm. Dostupné online: www.cs.berkeley.edu/~vazirani/algorithms/ (pouze kapitoly 1 až 5).

1. Kokeš, Josef: Algoritmy pro inženýrskou informatiku. Skriptum ČVUT, 2006

2. Wirth, N.: Algoritmy a struktúry údajov, ALFA, Bratislava 1981.

3. Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (standardní VŠ učebnice v USA, vyšla ve 45 vydáních)

4. Wroblewski, Piotr: Algoritmy. Computer Press, Brno, 2004

5. Cantu, Marco: Mastering Delphi 7. Sybex 2003 (1011 pages) - existuje též český překlad Mistrovství v Delphi (Grada)

6. Lischner, Ray: Delphi in a Nutshell. O'Reilly, 2002

7. Borland: Delphi Developer's Guide. Borland Software Corporation, CA, USA

8. Šindelář, Jan: Tipy a triky v Delphi. Webový kurs na stránkách www.zive.cz

9. Kadlec, Václav: Umíme to s Delphi. Webový kurs na stránkách www.zive.cz

Přednášející: josef.kokes@fs.cvut.cz

Poznámka:

Další informace:

Pro tento předmět se rozvrh nepřipravuje

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

• 12 131 NSTI PRT 2012 základ (povinný předmět programu)