NMIN101 Programování 1

 

akademický rok 2017/2018

 

3. 10. 2017 a 4. 10. 2017

Úvod, obsah přednášek, literatura, požadavky.

Tvorba programu, postupy a nástroje, programovací jazyk, ladění.

Algoritmus, důkaz správnosti, porovnávání kvality algoritmů.

Časová a paměťová složitost algoritmů, asymptotická složitost, notace „velké O“.

Složitost algoritmu v nejhorším, nejlepším a průměrném případě.

Složitost problému.

PREZENTACE

 

10. 10. 2017 a 11. 10. 2107

Programovací jazyk – syntaxe x sémantika, norma x implementace.

Struktura programu v Pascalu (hlavička, deklarace, tělo).

Proměnná, identifikátor, typ.

Přehled typů v Pascalu. Číselné typy – rozsahy hodnot.

Úprava textu programu – mezery, řádkování, komentáře.

Dosazovací příkaz, read, write. První program – vyhodnocení výrazu.

Definice konstant.

Přehled příkazů v Pascalu.

Dosazovací příkaz.

Volání procedury, standardní procedury read, write, inc, dec.

Podmíněný příkaz, sémantika vnořených if.

Složený příkaz begin – end.

PREZENTACE

 

17. 10. 2017 a 18. 10. 2017

Číselné výrazy – operátory, standardní funkce, celočíselné a reálné hodnoty ve výrazu.

Vyhodnocování výrazu, priority operátorů.

Kompatibilita při dosazování, konverzní funkce (trunc, round).

Cykly while, repeat.

Programy: ciferný součet, Eukleidův algoritmus (verze odčítání a modulo), prvočíselný rozklad.

Cyklus for, přerušení cyklu break, continue.

Standardní procedury read, write, readln, writeln, formátování výstupu.

Programy: formátování výstupu.

Inicializované proměnné.

Relace, jednoduché a složené podmínky.

Program: Test prvočíselnosti.

PREZENTACE

 

24. 10. 2017 a 25. 10. 2017

Typ Boolean, logické výrazy.

Program: test prvočíselnosti – druhá verze.

Pole – význam, definice type, indexování polí, konstantní meze, přepínač $R.

Programy: Hornerovo schéma, Eratosthenovo síto.

Vyhledávání v poli - $B, break, pomocí zarážky.

Binární vyhledávání v uspořádaném poli – půlení intervalů.

Třídění čísel v poli – přehled metod.

PREZENTACE

 

31. 10. 2017

Imatrikulace – výuka zrušena

 

1. 11. 2017 a 7. 11. 2017

Třídění výběrem, třídění vkládáním, bublinkové třídění (programy).

Zásobník a fronta, realizace v poli.

Práce s dlouhými čísly v poli.

Vícerozměrná pole – př. součin matic.

Inicializované proměnné typu pole.

Dekompozice problému, členění na podprogramy, význam procedur a funkcí.

PREZENTACE

 

8. 11. 2017

Děkanský den – výuka zrušena

 

14. 11. 2017 a 15. 11. 2017

Procedury a funkce – význam, lokalita, viditelnost identifikátorů.

Předávání parametrů hodnotou a odkazem.

Komunikace podprogramu s okolím – shrnutí.

Vnořené procedury, viditelnost identifikátorů.

Alokace paměti na zásobníku.

Inicializace lokálních proměnných, lokální inicializované proměnné.

Metody návrhu a ladění programů shora dolů, resp. zdola nahoru.

PREZENTACE

 

21. 11. 2017 a 22. 11. 2017

Znaky – typ char.

Znakové řetězce – typ string.

Poziční číselné soustavy, převody.

Program: převody z/do binární a hexadecimální soustavy.

Rychlé umocňování.

Textové soubory – operace, použití, formátování výstupu, $I, příklady.

PREZENTACE

 

28. 11. 2017 a 29. 11. 2017

Rekurze – princip, příklady, efektivita (Eukleidův algoritmus, faktoriál, Fibonacciho čísla).

Programy: Eukleidův algoritmus, Fibonacciho čísla (různé verze).

Příklady využití rekurze ke zkoušení všech možností.

Programy: K-ciferná čísla, kombinace, variace, vkládání znamének, rozklad čísla.

PREZENTACE

 

5. 12. 2017 a 6. 12. 2017

Princip základních rekurzivních metod – backtracking, metoda Rozděl a panuj.

Backtracking – princip, příklady, efektivita.

Zrychlení backtrackingu ořezáváním – osm dam na šachovnici, magické čtverce.

Zrychlení backtrackingu pomocí heuristik – proskákání šachovnice koněm.

Programy: osm dam na šachovnici, prosákání šachovnice koněm (dvě verze)

Spojení ořezávání a heuristik – nejkratší cesta bez znalosti mapy.

Metoda Rozděl a panuj – princip, příklady použití.

Program: vyhodnocení výrazu.

PREZENTACE

 

12. 12. 2017 a 13. 12. 2017

Informace o praktických zápočtových testech – podmínky, termíny, úlohy.

Metoda Rozděl a panuj – dokončení.

Program: Hanojské věže.

Prohledávání do šířky – princip, vztah prohledávání do hloubky a do šířky, příklady.

Způsoby realizace prohledávání do hloubky a do šířky (zásobník a fronta).

Příklady: úlohy na šachovnici, nejkratší cesta v grafu, souvislost grafu.

Programy: nejkratší cesta koněm na šachovnici (dvě verze).

Strom hry, algoritmus minimaxu a jeho realizace.

PREZENTACE

 

19. 12. 2017 a 20. 12. 2017

Algoritmus minimaxu, alfa-beta-prořezávání.

Nepřímá rekurze – forward.

Program: vyhodnocení aritmetického výrazu (nepřímá rekurze).

Unit CRT.

PREZENTACE

 

3. 1. 2018, 9. 1. 2018 a 10. 1. 2018

Pseudonáhodná čísla – použití v programování, generátor.

Příkaz case.

Příkazy skoku – goto, break, continue, exit, halt.

Záznam – použití, příklady (reprezentace polynomu), příkaz with.

Výčtový typ.

Ordinální typy, jejich společné vlastnosti (interval, ord, indexování, for, case).

Typ množina, množinové operace.

Třídy ekvivalence (faktorové množiny).

Programy: třídy ekvivalence (dva způsoby realizace)

Aritmetické přetečení, zaokrouhlovací chyby.

Programy: přetečení hodnoty maxint (vliv $Q), zaokrouhlovací chyby (X=X+1, součet N-tin).

Procedurální typy a parametry.

Program: plocha pod grafem funkce (dvě verze).

PREZENTACE z 3. 1. 2018

PREZENTACE z 10. 1. 2018