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.
Na přednáškách bylo probráno:
4. rijna:
- 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, zbytek ponechán k rozmyšlení). 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ý!
5. října:
Stabilni parovani vysvetlene, prohledavani grafu do hloubky a s navratem.
Tvorba programů v Pascalu. Vzhled programu v Pascalu, prostřední Borland
Pascalu. Definice konstant a proměnných.
Slidy.
19. října:
Tvorba programů v Pascalu - příklady, pole. Slidy.
2. listopadu (plan):
- Algoritmy a složitost (definice složitosti v nejhorším případě). Definice O, Omega a Theta.
- Poznámky se složitosti, složitost v nejhorším, nejlepším a průměrném případě, amortizovaná složitost, složitost problému.
- Vyhledávání v poli (nesetříděném a setříděném).
- Procedury a funkce. Definice funkcí a procedur, globální a lokální proměnné,
předání parametrů hodnotou a referencí.
- Vnořené funkce a procedury, scope resolution.
- Slidy.
9. listopadu:
- Ordinální datové typy, funkce ord, pred, succ a chr.
- Hornerovo schéma a jeho využití. Příklady: Převod čísla ve stringu na číslo, evaluace polynomu (vyhodnocení v bodě x),
- Základní povídání o rekurzi. Příklady: Faktoriál
- Slidy
16. listopadu:
- Algoritmus mocnění ab
v čase O(log b) (tedy lineární vůči délce binárního zápisu exponentu).
- Největší jedničková podmatice,
- Další příklady rekurze (případně lepších nerekurzivních algoritmů): Výpis všech nejvýše n ciferných čísel v soustavě o základu k, přednášející jde o M1
aneb Fibonacciho posloupnost rekurzí.
- Slidy.
23. listopadu:
Direktivy prekladace, textove soubory, definice vlastnich datovych typu
Slidy.
30. listopadu:
Struktury (typu record), klicove slovo with, bubblesort, insertsort, selectsort.
Slidy.
7. prosince:
Quicksort (aneb trideni rekurzi), jednotky (units), standardni jednotky,
povidani o jednotce CRT, median v linearnim case.
Slidy.
14. prosince
- Dámy (a další haraburdí) na šachovnici, dominance a nezávislost,
- aritmetické výrazy, notace a jejich vyhodnocení,
- některé problémy řešitelné "vyplněním tabulky" (zavorkovani a rozklad cisla na soucet - neni na slidech).
- Slidy.
21. prosince
- Fronta a zásobník, implementace pomocí pole,
- dlouhá čísla, reprezentace polynomů,
- grafy, jejich reprezentace a základní algoritmy nad nimi,
- faktorová množina (vyšetření tříd ekvivalence).
- Slidy.
4. ledna 2012
- Grafove algoritmy
- nejdelsi rostouci podposloupnost.
- Slidy. Ve slidech si, prosim, opravte: Na druhem slidu pred
navstiv(i);
na zacatek while-cyklu pridejte i:=prvni prvek z(fronta);