Materiály 2016/17
- 21. září: grafika v programu Blender.
- 5. října: architektura programovatelného počítače a alternativy. Instrukční sada, assembler. Zápisky.
- 12. října: cvičení v RISC assembleru.
- 19. října: operační systém: virtuální paměť, přerušení, zápisky. HTML: úvod do syntaxe, zápisky. Javascript: event-driven programování, úvodní cvičení bez podrobnějšího vysvětlení.
- 2. listopadu: Jednoduché HTML, debugger ve webovém prohlížeči, javascript DOM, podmínka
if. Cvičení, zápisky od minula.
- 9. listopadu: první písemka, rozbor viru: Cvičení. Druhá hodina odpadla.
- 16. listopadu: oprava první písemky. Dokončení rozboru viru z minula: cvičení, zápisky z dřívějška o javascriptu.
- 23. listopadu: druhá písemka. Dokončení cvičení z dřívějška, DOM strom. Zápisky.
- 30. listopadu: třetí písemka. Rekurze a fork bomba. Úvod k formátování v CSS, CSS Zen Garden.
- 7. prosince: Kaskádové styly podrobně. Změna formátování pomocí Javascriptu. Převod obecného XML obsahu pomocí XSLT.
- 14. prosince: 4. písemka. Obcházení okraje bludiště.
- 21. prosince: dokončení cvičení z minula a hledání nejkratší cesty. Sdílení kódu na Github a podobných službách.
- 4. ledna: hledání opravdu nejkratší cesty, výchozí kód, zápisky.
- 11. ledna: řešení problémů hrubou silou počítače, lámání hesel; výchozí kód, řešení. Organizační poznámky ke konci pololetí: doplňující úkoly pro Tomáše a pro Šimona.
- 18. ledna: úvod do c++, zápisky. Cvičení v C++: hledání ve stavovém prostoru, backtracking.
- 25. ledna: dokončení cvičení z minula.
- 1. února: technologické zázraky ukryté v počítačích. Přednáší Filip Dominec
- 8. února: jarní prázdniny
- 15. února: hodina odpadla
- 22. února: organizace druhého pololetí. Výpočetní složitost, zápisky. Třídění v kvadratickém čase a dále algoritmus Radix sort, zápisky. Ukázkový program na třídění seznamu čísel (vzorová data), libovolných dat a náhodných čísel.
- 1. března: 5. písemka (výpočetní složitost a související propočty, třídicí algoritmy s kvadratickou složitostí, radix sort). Chytré třídicí algoritmy: slévání, třídění haldou a quicksort. Cvičení.
- 8. března: Opakování: slévání a merge sort. Quickselect a quicksort. Halda a heap sort. Doplněné cvičení z minula – a zároveň stručné zápisky.
- 15. března: 6. písemka (Array.splice a třídění přímým výběrem, vkládáním a bubble sort).
Dokončení operací s haldou, halda v poli a operace heapify v
O(n). Teoretické odvození, proč nejde třídit v O(n). Ukázky, jak použít třídění v praxi.
- 22. března: třídění v praxi: hledání přesmyček jako zip (2MB) a přímo (14MB).
- 29. března: použití haldy: listina vítězů; Dijkstrův algoritmus na nejkratší cestu, cvičení; Základní pojmy ohledně stromů a grafů, reprezentace grafu v počítači.
- 5. dubna: 7. písemka na programování jednoduchých kousků kódu. Zadání aprílových projektů. Cvičení na použití haldy: Jarníkův algoritmus na minimální kostru grafu, Dijkstrův algoritmus na nejkratší cestu, A*.
- 12. dubna: 8. písemka na programování jednoduchých kousků kódu. Rozcvička na zacházení s haldou.
- 19. dubna: Cvičení na praktické programování: implementace algoritmů z dřívějška. Druhá hodina odpadá.
- 26. dubna: Odevzdání a stručné předvedení aprílových projektů. Dokončení Jarníkova a Dijkstrova algoritmu z dřívějška. Procházení grafu do šířky a do hloubky, zápisky; fronta a zásobník. Poznámka o mutable a immutable datových typech.
- 3. května: Řešení těžkých problémů hrubou silou: backtracking. Cvičení: problém obchodního cestujícího. Hledání ve stavovém prostoru, IDA*. Zápisky.
- 10. května: Třídy složitosti P a NP, zápisky. Fraktály: první a druhá ukázka.
- 24. května: 9. písemka. Algoritmicky nerozhodnutelné problémy, problém zastavení a jeho obdoby; zápisky. Postův korespondenční problém (ukázka), Mandelbrotova množina (ukázka).
- 31. května: Konečný automat, regulární výrazy. Ukázky: Havran.
- 7. června: 10. písemka – obecné otázky ano/ne související se složitostí P, NP a s algoritmicky nerozhodnutelnými úlohami (problém zastavení). Cvičení s regulárními výrazy: Havran, česká slova.
- 14. června: Úpravy aprílových projektů: zpřehledňování a zkracování kódu. Úvodní cvičení na ransac schéma.
- 21. června: Perličky: ransac schéma (Blender + Python): míč, střechy, hvězdy.
Zápisky podle tématu
Probraná témata se postupně mění v odkazy na příslušné zápisky.
Témata označená hvězdičkou už jsme probrali, jen nejsou (zatím) zápisky online.
- fungování počítače
- procesor a paměť:
Von Neumannova architektura a její alternativy;
instrukční sada, Assembler;
registry a instruction pointer;
adresování paměti.
- sběrnice a porty:
digitální a analogové spojení*, sériové a paralelní spojení*;
cache*;
pevný disk;
grafická karta;
periferie.
- operační systém:
proces;
vlákno;
virtuální paměť, odkládací soubor;
souborový systém;
uživatelská oprávnění;
instalace software.
- programátorské řemeslo
- teoretická informatika
- matematické základy počítačů:
binární logika;
reprezentace celých a reálných čísel;
Hornerovo schéma;
Lagrangeův interpolační polynom.
- výpočetní složitost:
časová a paměťová složitost;
horní a dolní odhad složitosti*;
třídy složitosti: polynomiální, NP;
nerozhodnutelné problémy.
- výpočetní modely:
konečný automat;
Turingův stroj, Random Access Machine.
- užitečné algoritmy
- počítačová bezpečnost
- zabezpečená komunikace:
symetrické šifry;
šifry s veřejným klíčem;
digitální podpis;
hashovací funkce a jejich uplatnění;
síť důvěry PGP/GPG.
- bezpečnostní postupy:
zabezpečení disku, především šifrování;
zacházení s hesly;
lámání hesel a šifer*.
- sítě a Internet
- TCP/IP
- internetové služby:
web;
DNS;
e-mail.
- technologie související s počítači:
aplikace pro chytré telefony;
robotika, navigace v prostoru;
mikrokontrolery, hradlová pole.
