Algoritmy pro inženýrskou informatiku (2371014)
Departments: | ústav přístrojové a řídící techniky (12110) |
Abbreviation: | | Approved: | 02.10.2097 |
Valid until: | ?? | Range: | 2P+2C |
Semestr: | 8 | Credits: | 5 |
Completion: | Z,ZK | Language: | CS |
Annotation
Předmět seznamuje se základními algoritmy.
Výuka je zaměřena spíše prakticky, na aplikaci algoritmů při řešení inženýrských úloh. Příklady jsou prezentovány v jazyce Java.
Structure
Pro úplné laiky
Jak počítá počítač
OOP - hodně zjednodušený úvod
Java 1
NetBeans, JavaFX, basic I/O
Basic Syntax: Classes, Data Types, Variables, Operators
Methods
Decision Making, Loops
Loops - for, while and do...while
Numbers Class
String Class
String Buffer & String Builder Classes
Třída Math
Rekurze
Základní datové struktury
Fronta, zásobník, Halda, Strom
Stromy
Terminologie. Realizace polem, haldou, dynamicky
Hufmannův strom
Binární stromy: hledání, vkládání
AVL stromy: hledání, vkládání
2-3-4 stromy, 2-3 stromy, B-stromy, červeno-černé stromy
Seznamy
Lineární spojový seznam, Vkládání na začátek, za konec
Vkládání na značku, před značku. Odebírání za značkou, na značce.
Zvláštní druhy seznamů.
Hledání
Přímé, lineární, půlením
Metoda transformace klíče
Řazení (=třídění)
BubbleSort, ShakeSort, ShellSort, InsertSort
QuickSort
Řazení v lineárním čase
CountingSort
BucketSort
Asymetrické šifry, RSA, útok MIM
Praktické použití: klíče, certifikát, podpis
(Obsah přednášek podrobněji na www.fs.cvut.cz/cz/U12110/aii).
Structure of tutorial
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.
Literarture
Doporučené studijní materiály jsou uvedeny v sylabech, které jsou k dispozici na ????? v sekci "Téma 01"
Requirements
Předmět nepředpokládá žádné předběžné znalosti.
Ke zkoušce jsou předepsány znalosti v rozsahu přednášek. Zkouška je praktická a ústní. Praktická část zkoušky - napsat a odladit jednoduchý program z odpřednášeného učiva.
Na cvičení studenti obdrží zadání 3 příkladů k vypracování.
Keywords
Dynamické datové struktury: zásobník, fronta, tabulka, seznam, strom (binární, AVL, B-stromy).
Operace s datovými strukturami: Vkládání a vybírání, rotace AVL.
Algoritmy hledání: přímé, indexové, transformace klíče.
Algoritmy řazení: bubblesort, shellsort, shakesort, quicksort.
Řazení s dodatečnou informací: countingsort, bucketsort.