456-0114/02 – Základy algoritmizace (T) (ZALT)

Garantující katedraKatedra informatikyKredity4
Garant předmětuRNDr. Daniela Szturcová, Ph.D.Garant verze předmětuRNDr. Daniela Szturcová, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostpovinně volitelný
Ročník4Semestrzimní
Jazyk výukyčeština
Rok zavedení2001/2002Rok zrušení2002/2003
Určeno pro fakultyFEIUrčeno pro typy studiamagisterské
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2

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

Prezenční forma (platnost od: 1960/1961 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (145) 51
        Zkouška Zkouška 100  0
        Zápočet Zápočet 45  0
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2002/2003 (M2612) Elektrotechnika a informatika (2612T999) Společný základ pro FEI P čeština Ostrava 1 povinný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava 1 povinný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava 1 povinný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2612T999) Společný základ pro FEI P čeština Ostrava 1 povinný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava 1 povinný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava 1 povinný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 1 povinný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava 1 povinný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2000/2001 (M3646) Geodézie a kartografie (3602T002) Geoinformatika P čeština Ostrava 4 povinně volitelný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku