Kolegové a kolegyně, obecné informace o přednášce Programování I (vztahující se k oběma skupinám) najdete na stránce kolegy Kryla. Jelikož informace platí pro obě skupiny, bylo by kontraproduktivní zveřejňovat je dvakrát.

Zde se můžete kromě obsahu mých proběhlých přednášek dozvědět informace pro externisty, které jsem letos dostal na starosti.

Na přednáškách bylo probráno:

1. října:

• Organizační informace, informace o zápočtu a technických aspektech (účty, které si je třeba zařídit), informace o Praktiku z programování
• Pojem algoritmu, správnost algoritmu a způsob dokazování správnosti.
• Příklady algoritmů: Eukleidův algoritmus (s důkazem správnosti), magické čtverce lichého řádu (bez důkazu správnosti), Stabilní párování (zformulován problém, naznačen algoritmus, ponecháno k rozmyšlení na příště). Promítané slidy si můžete stáhnout. K Eukleidovu algoritmu si můžete prohlédnout animace verze s rozdílem a se zbytkem po dělení. Příklady jsou ovšem psány v pseudokódu připomínajícím Pascal, který vám nemusí být v tuto chvíli ještě zcela srozumitelný!

• Stabilní párování (algoritmus a důkaz "pánské volenky"),
• Theseus v bludišti (viz pojednání a animace kolegy Kryla.
• Úvod do Pascalu: Vzhled programu v Pascalu, konstanty, proměnné, typy proměnných, aritmetické výrazy, přiřazovací příkaz, relační operátory, podmínky, cykly. Promítnuté slidy si můžete prohlédnout. Povídání o důkazu pánské volenky ve stabilním párování, které, jak jsem vyrozuměl, někteří nepochopili.

• Demonstrace prostředí Turbo Vision a integrované rozhraní (IDE) Borland Pascal 7.0
• příklady jednoduchých programů (převod do dvojkové soustavy - odzadu, rozklad na prvočinitele),
• pole (definice a použití, klíčové slovo array, operátory hranatých závorek), komentáře,
• Eratosthenovo síto (předešlé několika naivními algoritmy),
• Algoritmy a složitost:
  • Definice složitosti (v nejhorším případě), poznámka, že tato složitost bývá občas zvána "dynamická složitost" a uvedeno, čemu se občas říká "statická složitost",
  • asymptotické odhady, definice O, Ω a Θ,
  • poznámka o průměrném a nejlepším případě a amortizované složitosti,
  • složitost problému,
• Algoritmy vyhledávání v nesetříděném a setříděném poli, složitost problému vyhledávání v nesetříděném poli.
• Slidy si jako obvykle můžete prohlédnout.

• Praktikum z programování začne v týdnu od 26. října. V tomto týdnu všichni účastníci praktik kontaktujte svého cvičícího (včetně těch, kteří mají cvičení ve středu, na kterou připadá státní svátek)!
• Definice funkcí a procedur, volání a návratová hodnota,
• předávání parametrů hodnotou a referencí, globální a lokální proměnné, vnořené funkce, "viditelnost identifikátorů".
• Rekurze - myšlenka a příklady: Faktoriál, Fibonacciho čísla.
• Slidy

• Ordinální datové typy (tedy typy, které nesou hodnotu),
• konverze čísla do řetězce,
• Hornerovo schéma a jeho konkrétní aplikace:
  • konverze řetězce na číslo,
  • evaluace (vyhodnocení) polynomu.
• Labely a goto (s vysvětlením proč nepoužívat),
• fronta a zásobník (definice, nikoliv implementace),
• prohledávání do šírky alias algoritmus vlny - příklad "cestování krále po děravé šachovnici",
• slidy.

• Předvýpočet a jeho využití. Příklad hledání největší jedničkové podmatice:
  • předveden naivní algoritmus,
  • algoritmus s předvýpočtem a složitostí O(mn²)
  • a algoritmus s předvýpočtem a složitostí O(mn),
  • snadný argument proč je složitost problému Ω(mn).
• Rekurze příklady:
  • Výpis všech čísel nejvýše zadané délky v zadané číselné soustavě,
  • problém batohu a jeho řešení pomocí rekurze,
  • Fibonacciho čísla (úloha přednášející stoupá do F1) a analýza složitosti při generování tabulky Fibonacciho čísel od prvního do n-tého. Vysvětlení, že s problémem batohu můžeme udělat podobný trik, poznámka, že této metodě říkáme dynamické programování (které bude důkladněji předneseno později).
• Slidy.

• Předávání pole v parametru,
• výčtové datové typy
• konstrukce case... of,
• základní třídící algoritmy (bubblesort, insertsort, selectsort, quicksort)
• slidy, došli jsme ke slidu 25!
• Příklady, které se na slidy nevešly:
  • příklad na využití výčtového typu (jednoduchý "kalendář"),
  • příklad na využití case... of (rozšíření kalendáře aby místo čísla dne bylo vypisováno jméno dne,
  • příklady implementace třídících algoritmů, implementován je BubbleSort (procedura bublej), SelectSort (procedura vytrid), InsertSort (procedura zatridovani) a Quicksort (procedura quicksort). Věnujte pozornost samotným algoritmům spíše nežli technickému předávání polí jako parametry, i když tato záležitost byla motivací pro odpřednesení pole jako parametru.

• Direktivy překladače
• Textové soubory a práce s nimi (proměnná typu Text, funkce Assign, Reset, Rewrite, Append, Read, ReadLn, Write, Writeln, Close...).
• Proměnná IOResult a práce s potenciálně rizikovými funkcemi (příklad vypnutí IO-erroru na nezbytnou dobu pomocí direktivy).
• Quicksort,
• myšlenky metody "rozděl a panuj",
• metody analýzy složitosti rekurzívních algoritmů.
• Slidy

• Jednotky (units), jejich definice, využití, jednotky dodávané s překladačem.
• Struktury (records) a jejich využití.
• Hledání mediánu v lineárním čase (algoritmus).
• Slidy

• Oznámení soutěže v programování, která se odehraje v pátek 11. 12.
• Hledání mediánu v lineárním čase,
• odstrašující příklad zásahu do cyklící proměnné ve for-cyklu (každý překladač reaguje jinak),
• odstrašující příklad předávání parametru referencí - předání jednoho parametru vícekrát.
• Parametry programu (co to je), funkce ParamCount a ParamStr.
• Úlohy řešitelné pomocí rekurze s cachováním výsledků: Přednášející jde do F1, nejdelší rostoucí podposloupnost.
• Slidy - dojeli jsme jen k obrázku 21 (ostatní budou příště).

10. prosince: Slidy - konec pred Pascalovym trojuhelnikem (tedy slide 28).

17. prosince: Slidy - konec pred nasobenim matic (tedy slide 31).

7. ledna: Slidy - predpokladany konec u slidu 18.

14. ledna: Slidy.