456-0114/02 – Základy algoritmizace (T) (ZALT)
Garantující katedra | Katedra informatiky | Kredity | 4 |
Garant předmětu | RNDr. Daniela Szturcová, Ph.D. | Garant verze předmětu | RNDr. Daniela Szturcová, Ph.D. |
Úroveň studia | pregraduální nebo graduální | Povinnost | povinně volitelný |
Ročník | | Semestr | letní |
| | Jazyk výuky | čeština |
Rok zavedení | 2001/2002 | Rok zrušení | 2002/2003 |
Určeno pro fakulty | FEI | Určeno pro typy studia | magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Po absolvování kurzu be měl posluchač zvládnout sestavit algoritmus vedoucího ke správnému řešení základních úloh s podporou probraných datových struktur.
Vyučovací metody
Anotace
Kurz je určen studentům se zájmem o obor Inženýrská
informatika. Náplň předmětu je proti základnímu kurzu širší.
Posluchači naučí sestavit algoritmus řešení daného problému
a seznámí se s pojmem algoritmus, datový typ a řídicí struktura,
rekurze etc. Získají přehled o základních algoritmech, jejich
principy jsou využívány při řešení většiny typických úloh
z oblasti computer science. Výklad je proti základnímu kurzu
rozířen o některé abstraktní datové typy, další třídící
a vyhledávací algoritmy, velká pozornost se věnuje některým
druhům DT Strom. Podrobněji než v základním kurzu se také
studenti seznámí s problematikou reprezentace čísel v počítači.
Algoritmy budou zapisovány v pseudokódu, bez závislosti na
detailech kteréhokoliv programovacího jazyka.
Povinná literatura:
Sylaby přednášek
Wirth, N.: Algoritmy a struktůry údajov, Alfa, Bratislava 1989
Topfer, P.: Algoritmy a programovací techniky, Prometheus, Praha 1995
Harel, D.: Algorithmics, The Spirits of Computing, Addison-Wesley Publishing Company, 1993
Virius, M.: Základy algoritmizace, ČVUT Praha, 1997, skripta
Sedgewick, R.: Algorithms in C++, Addison-Wesley Publishing Company, 1992
Doporučená literatura:
Sylaby přednášek v elektronické podobě.
Manuály programovacích jazyků.
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Podmínky udělení zápočtu:
Zápočtový test 2*20 bodů (pro udělení zápočtu je nutno získat alespoň 15 bodů, z každého testu minimálně 5 bodů)
E-learning
Další požadavky na studenta
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
Pojem algoritmu. Konstanty, proměnné, výrazy, přiřazení. Návrh algoritmu. Řídicí struktury. Krokovací tabulka.
Princip číslicového počítače. Reprezentace čísel v číslicovém počítači. Číselné soustavy.
Základní datové typy. Vlastnosti datových typů. Jednoduché datové typy (boolean, číselné typy, znak) a operace nad nimi. Ukazatel.
Strukturované datové typy a operace nad nimi. Pole, struktura.
Abstraktní datové typy. Zásobník, fronta, graf (strom), stream, tabulka, seznam.
Implementace. Procedury a funkce.
Rekurze. Rekurzivní a nerekurzivní definice a algoritmus. Rekurzivní funkce.
Složitost. Dominantní operace, O(f) notace.
Třídění. Třídění přímým vkládáním, přímým výběrem. Bubble sort, Quick sort, Heap sort, Radix sort.
Vnější třídění. Princip slévání, Merge sort.
Hashing. Hashovací funkce, řešení kolizí. Separate chaining, Linear probing.
Vyhledávání. Sekvenční, binární vyhledávání. Vyhledávání k-tého prvku.
Vyhledávání podřetězce (Pattern Matching). Jednotlivé algoritmy.
Operace se stromy (vkládání, vyhledávíní, rušení uzlů). Průchody stromem. Operace vyvažování. Vybrané typy stromů (Red-Black stromy, B-stromy řádu n).
Zpracování aritmetických výrazů, prefix, infix a postfix.
Cvičení:
Cvičení navazuje na přednášky praktickými příklady.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.