Co bylo na minulých přednáškách z NPRG030/NPRG031 Programování I/II v roce 2015/16 ================================================================================== 24.5.2016: Řešení těžkých úloh: * Motivační úloha: páková baterie * nakreslení grafu - ...řešte jinou úlohu * hádání obrázku - ...zapojte přirozený výběr - genetické algoritmy, fitness, selekce, křížení, mutace - význam mutace * broučci BROUCCI2.PAS * broučci s pamětí BROUCCI.DPR - cil = zjistit výhodu paměti, - jak měřit – měřící bludiště - výsledky pro 1 a pro 3 stavy * broučci BCY * historka o magnetofonu - ...podívejte se z odstupu - nonius - VASI * OCR - ...hledejte řešení v určitém tvaru - větší počet bodů a odolnost proti chybě * vodovodní baterie - řešení 17.5.2016: * "zkouškový" příklad - úloha počet přehnutí papíru * Hygiena programování: 1. oddělovat činnosti 1. analýza 2. design 3. GUI design 4. (hledání algoritmu) kódování 5. grafika/zvuky/texty 6. testování 7. dokumentace = ODDĚLOVAT !! Neodbočovat při řešení problému! - resources 2. pracovní deník - důležitý už kvůli psaní - rozhodnout se, co budu dělat teď - = gumová kačenka - evidovat časy (a učit se odhadovat) - záznam PROČ 3. správa versí CVS, SVN, GiT, Hg… 4. bug-list – bug tracking system 5. testy a test-driven programming - psát volání funkce dříve než funkci - assert - testy – TEST a počítat chyby - testovací procedury – automatické testy, ladění proti testům, testy výkonnosti, regresní testy - Ntest - asserty * těžký příklad - podezřelé osoby na video-záznamu 10.5.2016: * "zkouškový" příklad - odpověď = analýza (a design): 0) upřesnění zadání 1) postřehy 2) zdůvodněná volba algoritmu (složitost atd.) 3) representace dat 4) dekomposice - rozklad řešení na části 5) diskuse * příklad příkladu: úloha ANKETA - zadání - kroky - data-flow diagram - celková složitost - možné paralelní provádění některých kroků * delegáty jako proměnná jako parametr funkce: anonymní funkce * vlakna v C#: - Thread, t.Start - počet jader //- t.Abort(); - t.ThreadState - // Ad výjimky: neošetřená výjimka na vlákně shodí celou aplikaci * čekání: - aktivní x pasivní - Thread.Sleep - t.Join(); * race condition, thread safety !! - Random NENI thread-safe * zamykání: - lock //* deadlock 3.5.2016: * Grafy: - representace: - matice sousednosti - matice vzdáleností - seznam hran - matice incidence (-1 -> +1, 0) - seznam následníků * trik se seznamem seznamů (jedno pole následníků a indexy) - = volit reprezentaci podle toho, jaké operace budeme provádět. * úlohy a algoritmy: * nejkratší vzdálenost (z A do B, z A do všech) - Dijkstrův algoritmus - předpoklady: kladně ohodnocený, souvislý - trvale a dočasně ohodnocené vrcholy - inicializace - krok - jakou reprezentaci použít (seznam následníků) - složitost O(|V|2+|E|) (resp. log |V|...) - Floyd-Warshall (ze všech do všech) - předpoklady: ne záporné cykly - algoritmus, dynamické programování - jakou reprezentaci použít (matici vzdáleností) * minimální kostra - co je to - Kruskalův („hladový“) algoritmus (min. ze všech nepoužitých hran nevytvářejících cyklus – UNION-FIND problem) * faktorová množina (UNION-FIND) - množina tříd ekvivalence - příklad: komponenty grafu - => vidět, že lze použít na hledání minimální kostry hladovým algoritmem - jakou reprezentaci použít (seznam hran v haldě, třídy ekvivalence (jedno pole)) - zlepšení složitosti, pokud pamatujeme počty prvků a přejmenováváme menší třídu * topologické uspořádání (už jsem ukazoval): - jakou reprezentaci použít (seznam následníků) - nejdelší cesta * grafika - vyber a kopirovani * těžká úloha ABCD * zkoušky – vypsané termíny 26.4.2016; * výjimky - jiný přístup k chybám - try - catch - Exception a hierarchie - vnořování try-bloků - odchytávat jen to, čemu rozumím - throw (znovyvyhození i vytvoření nové výjimky) - finally - diskuse o vhodnosti používání výjimek * Programování pomocí testů - Příklad: funkce na určení podílu dvou čísel zadaných ve stringu - Testování – vstup ručně, kontrola očima = pracné, pomalé, nespolehlivé - Nahradit zadávání vstupu kódem - Nahradit kontrolu výsledků kódem - Funkce na otestování jednoho volání - Očekávaný výsledek - Počítání chyb - Porovnání jednoho výsledku - Přidávání testů (protože je to snadné) - Rozhodnutí,jak zacházet s chybami – výjimky nebo chybové kódy - postup: - testy -> chyby -> funkce -> 0 chyb - unit-testy, test-driven programming, NUnit * Grafika v C# (WinForms) - Bitmap.Clone(...) 19.4.2016: * Grafika v C# (WinForms) * Graphics - Získání - this.CreateGraphics() //- Graphics.From… * Pen - Pens (properties) - New Pen * Color - Připravené (properties) * Pero – caps * PictureBox * Bitmap * Brush - Brushes (properties) - new SolidBrush * Color - FromARGB, RGB = vypočítaná barva * Bitmap.GetPixel, SetPixel - kopie - Zmena souradnic - Preklopeni x,y - Zvetseni - deformace - barevna slozka - světlost – převod na šedou - prah - Distribuce chyby - změna jasu a kontrastu - reliéf * DrawString - Font 12.4.2016: * optimální vyhledávací strom - a jeho hledání dynamickým programováním * Floyd-Warshallův algoritmus * hashování - jeho naprogramování - System.Collections.HashTable * C# dialogy: - AcceptButton, CancelButton - DialogResult - FormClosing - ...e.Cancel - dialog po skončení uvolní okno 5.4.2016: * dynamické programování - příklad: editační vzdálenost a nejdelší společný podřetězec - lehčí příklad: 6 dětí do 3 skupin - řešení rozborem případů - ještě lehčí příklad: mrkev a petržel 10 záhonů - rekurentní vzorce - skládání řešení z řešení menších úloh stejného typu - části optimálního řešení jsou optimální řešení pod-úloh - výměna paměti za čas - příklad: Optimální uzávorkování násobení matic - složitost - příklad: Vyhrávající a prohrávající pozice odebírání zápalek pro daný počáteční počet - příklad: Počet různých her odebírání zápalek pro daný počáteční počet - příklad: Počet různých cest v orientovaném acyklickém grafu - příklad: Nákupní vycházka po NYC - snadná cesta: backtracking s ukládáním parametrů a výsledků - příklad: nejdelší společný podřetězec - ...pomocí tabulkového kalkulátoru * C#: aplikace s více okny: - dalsi okno - hlavni okno - show: Show() - dialog: ShowDialog(); * C#: vytvoření nové komponenty za běhu - nastavit vlastnost Parent - ...jde i jiné okno 29.3.2016: Programování řízené událostmi (Event-driven programming) * programování řízené událostmi - princip * události – klávesnice, myš * jak probíhá zpracování události - hierarchie - polymorfismus https://msdn.microsoft.com/en-us/library/windows/desktop/ms644927%28v=vs.85%29.aspx * Visual Studio: - Designer, ToolBox, Property editor * Druhy properties - Oddělení designu a funkčního kódu * Syntaxe: partial class * Vytvoření obslužné procedury via propertie a via dbl-click - MessageBox * Timer - Hodiny * Sdílení obslužných metod - Sender - Přetypování - Is - Kalkulačka * příklad s poštou 22.3.2016: Drobnosti, zbytky, nedodělky * pole - odvozeno od System.Array - dosazovani pointru vs. kopie pole - Clone() // vysledek - pretypovani: # int[] b = (int[])a.Clone(); //- proc je vysledek Object a ne System.Array <= pozdeji (ICloneable) - ostatni metody - Array.BinarySearch - ty prvky musi implementovat IComparable! //- genericke funkce/typy: "where - foreach - pro vsechny prvky v poli nebo kolekci, ktera implementuje System.Collections.IEnumerable nebo System.Collections.Generic.IEnumerable - detaily PavelJezek a C# * OOP - staticka metoda, staticka trida sl_2. 21/26 - atributy viditelnosti - zapouzdreni - gettery a settery - properties - sealed * DateTime - Now, TotalMiliseconds * string x StringBuilder - String, pridavani a 10.000 znaku, vypis casu; .xls * simulace - obchodni dum - nahodny zakaznik * Random - seed, chyba pri vytyvoreni vice generatoru 15.3.2016: Diskrétní simulace: * Cílem zpravidla není jeden konkrétní případ, ale sledovat chování systému * Cílem NENÍ optimalizovat, jen odpovídat na otázku, jak by to dopadlo * Počet aut: - Nemusíme přepisovat kód, nový model - protected int PocetAut - Výstup a graf * Počet nakladačů: - Nový model Model3 - protected int PocetNakladacu - Volani konstruktoru : base(pocetAut) - Výstup a graf - Tabulka, cena auta/min, cena nakladace/min => minimum a podmíněný formát - optimum * V čem se bude lišit jiný model: - Procesy - Události - …a reakce na ně * Návrh modelu – obchodní dům * Procesy * Události * Stavový diagram - Kdo vyvolá změnu stavu - Jaké akce se při ní mají provést * => Popis, který je výsledkem (důležitější než program) http://ksvi.mff.cuni.cz/~holan/pas/obchod.txt http://ksvi.mff.cuni.cz/~holan/pas/obchod_data.txt C#: * System.IO.StreamReader * generické funkce a třídy - proč a jak, List<> * výstup pomocí šablon 8.3.2016 Diskrétní simulace: * úloha s hromadou písku * Model - Zjednodušený, jen některé atributy - I rovnice je model - Co modelovat a co zanedbat - Co modelovat jak * Simulace spojitá vs. diskrétní * Auto - Atributy podstatné pro výpočet * Písek v A, Písek v B * Čas * Fronta v A Program: * událost - C# enum * Kalendář * Auto * PísekVA, PísekVB, Čas 1.3.2016: * syntaxe C#, rozdíly proto Pascalu - pokračování - cykly - funkce - pole - dynamické proměnné - vstup a výstup - čtení čísel ze vstupu - int.Parse() nebo si napsat vlastní čtečku * objekty - konstruktor - dědičnost - virtuální metody - polymorfismus - abstraktní třída, abstraktní metoda //- atributy viditelnosti, zapouzdření //- properties 23.2.2016: * Zápočty – program, zápočtový test * zkouška – písemka, ústní, jaká písemka * obsah – další algoritmy, meta-algoritmy * slajdy a zdrojové texty – na webu * jazyk – C#, MS Visual Studio - nový jazyk, ale známé konstrukce * objekty a OOP: - způsob uvažování o částech programu - CO x JAK - Historie (Simula 67, Smaltalk, OOP boom 90-tých let) - spojení dat a funkcí - zapouzdření – ukrývání vnitřku, díky tomu konsistentní stav - vzor x instance: třída x objekt - příklad: komplexní čísla - příklad s tiskem slov na řádky dané šířky * C# a Microsoft Visual Studio - 1995 Java, bytecode - 2002 C#, .NET - Anders Hejlsberg - Nascom microcomputer: Blue Label Software Pascal -> PolyPascal -> Turbo Pascal - 1989 Borland - Borland Delphi chief architect - 1996 Microsoft - J++ - 2000- C# lead architect - program = sbírka objektů - metoda Main() - žádné “globální” metody ani proměnné, všechno patří nějaké třídě - sin – Math – instance? => static metody - syntaxe jazyka C# - rozdíly C# proti Pascalu 11.1.2016: * vnejsi trideni - Základní operace: slučování (merge) - dvoufázové dvoucestné přirozené slučování - vylepšení: - jednofázové - vícecestné - předtřídění - obyčejně - pomocí haldy - pomocí dvou hald - polyfázové * zbytky Pascalu: - funkce v proměnných, funkce jako parametry * příklady - postup řešení - Lloydova šestka - znaménka do 1 2 3 4 5 6 7 8 9 4.1.2016: * datové struktury - abstraktní typ, rozhraní - jak zatím umíme representovat seznam - stromy! * BVS - definice - vyhledání - přidání * příklad rekurse: tisk BVS - kvuli "GotoXY" zminka o unitach v BP: - unit-interface-implementation, uses, unit Crt, GotoXY * BVS - vymazání * Vyvážené stromy - Dokonale - AVL - Definice - logaritmická výška - Vyvažování – rotace - Kolikrát vyvažovat - B-stromy - Definice - operace * příklad na rekursi: hra 7531 21.12.2015: * vnitřní třídění (řazení, sorting) - složitost zvlášť v počtu porovnání a zvlášť v počtu přesunů - přímý výběr (selection sort) - přímé vkládání (insertion sort) - bublinkové třídění (bubble sort) - třídění přetřásáním (shake sort) - meze nesetříděné části - Shellovo třídění - stromové třídění - HeapSort - halda, definice - representace haldy v poli (obecně jakéhokoliv binárního stromu) - oprava po odebrání kořene - procedura VytvorHaldu(L,R) - postavení haldy - v lineárním čase - třídění sléváním (merge sort) - myšlenka - složitost - paměť - O(N), (lze pole indexů) * hledání k-tého prvku - postupným vybíráním - setříděním - QuickSort-like lineární algoritmus * pojem složitost úlohy - složitost úlohy vnitřního třídění založeného na porovnání dvou prvků - přihrádkové třídění (bucket sort) - ...s více průchody (radix sort) * Příklad: "absolute" a systémové proměnné (VideoRAM, tick) 14.12.2015: * Hry: - konečné hry s úplnou informací - rekurentní definice prohrávající a vyhrávající pozice (kdyby neexistovala remíza) - strom hry (nemusí být strom) - konečný počet sehrávek, u každé známý výsledek - důsledek: existence neprohrávající strategie - rekurentní definice -->> rekurzivní funkce - příklad: zápalky 1..3 - příklad: zápalky 1, 5, 6, 18 - problém výpočtu: rychlost/pomalost - řešení problému: cache (ukládat již spočítané výsledky/ohodnocení stavů) - hry s ohodnocením: - hry s nulovým součtem (- hry s nenulovým součtem - Vězňovo dilema) - algoritmus Minimax - příklad: odebírání z řady čísel - počítání směrem dolů - negamax - opravdové hry: - příliš veliké - alfa-beta prořezávání - počítání do omezené hloubky a nahrazení statickou ohodnocovací funkcí - ...ne všude stejná funkce //- kaskádová metoda //- okénko - procházení do rostoucí hloubky - příklad BP/CHESS - HEURISTIKA: - záleží na pořadí prohledávání (ale jen rychlost) - širší a užší význam - příklad heuristiky: loupežníci * metoda "Rozděl a panuj" - Vyhodnocování výrazu rozkladem na podvýrazy - QuickSort ... * problém vnitřního třídění: - QuickSort - myšlenka - program - proč (ostré nerovnosti, neostrá nerovnost...) - složitost v nejhorším a průměrném případě - volba pivota - zásobník - QuicSort NETŘÍDÍ n amístě ("in situ") (ukládat VĚTŠÍ díl a menší řešit iterací) * Odstraňování rekurse - vlastním zásobníkem - nahradit iterací (QuicSort v Borland Delphi) 07.12.2015: Dlouhá čísla: * representace - nezáporná x i záporná - se znaménkem x doplněk - celá x desetinná - pevná x pohyblivá řádová čárka - pole x spojový seznam - odpředu x odzadu - obsah jednoho prvku - délka - kolik míst navíc - spočítat a ještě zkusit * příklad e (Leonhard Paul Euler 1707-1783) - odhad počtu kroků - potřebné operace - dosazení - sčítání - dělení integerem - přeskočení nul - test konce * odčítání - doplněk * násobení - dlouhým číslem - integerem Příklad: faktoriál 450 * dělení * postupné testování vytvářených funkcí (programování shora - ladění zdola) * Příklad na rekursi a backtracking: umístit N dam na šachovnici: - hloupě (umisťovat dámu do šachovnice) - lépe (umisťovat dámu do sloupce) - nejlépe (obsazovat řádky a diagonály) 30.11.2015: * soutěž 11.12.2015 15:00-18:00 * oddělení CO a JAK u kódu – funkce, hodilo by se i pro data. Pro hledání potřebujeme seznam dosud neprozkoumaných stavů - přidej - vyber a vrať nějaký - řekni, jestli je prázdný Přitom nás nezajímá JAK – pole, spojový seznam, soubor(y)… = abstraktní datový typ. Rozhraní (interface) Časem – tohle realizují objekty. * Obecný algoritmus hledání. Seznam: není řečeno, který prvek vybírá. Dva zvláštní typy: fronta a zásobník. Prohledávání do šířky (vlna) a do hloubky (backtracking) = stený obecný algoritmus. * Realizace zásobníku a fronty v poli. Cyklická fronta. * Realizace zásobníku a fronty pomocí spojových seznamů (kam přidávat, odkud ubírat). * Hledání cesty na šachovnici, pomocí fronty a pomocí zásobníku. * složitější dynamické struktury – stromy * vyhodnocení výrazu * výpis – průchod – notace * vyhodnocení v různých notacích - předběžná deklarace forward * vytvoření stromu z různých notací * převody mezi notacemi (vytvořit strom a vypsat) * Příklad na rekursi - proskákat šachovnici koněm 23.11.2015: * Ad spojove seznamy – postup (na příkladu "Přidání x do setříděného seznamu"): 1. Jak vypadá běžná situace 2. Jaké vyjímečné situace musíme ošetřit - Prázdný seznam - Všechny prvky jsou větší (neexistuje předchůdce) - Všechny prvky jsou menší (neexistuje následník) - …a běžná situace * Kreslit si obrázky! * Ad vyjímečné situace a potíže spojových seznamů: - Předchůdce => obousměrný seznam - Prázdný seznam => hlava - Poslední prvek => cyklický seznam * Spojové seznamy a vyhledávání se zarážkou – NYL * Rekurse - co to je, jak v Pascalu - musí obsahovat větvení - vlastní kopie proměnných pro každou instanci - Klady a zápory - Odstrašující příklad: Fibonacci - Náprava ukládáním výsledků - BP: Call stack - Příklady: - Hanojské věže - Vypsání všech permutací - Loupežníci - Vyhodnocení výrazu rozkladem na podvýrazy * typy "set of ..." = jen zmínka, abych mohl použít pro podmínky tvaru "if c in ['+','-','*','/'] then" 16.11.2015: * record * dynamické proměnné - motivace - proměnné vyráběné podle potřeby za běhu programu, rekursivní data - implementace - ukazatele - NIL - vsuvka o tabulce přerušení - new - dispose * jednosměrný lineární spojový seznam - projití všech prvků - přidávání prvků na začátek a na konec - ...a s ukazatelem na konec - smazání prvního prvku * representace, halda - MemAvail, MaxAvail v TP - správce haldy, vrchol haldy, seznam děr - seznam děr uložený v dírách, minimální velikost alokace 2.11.2015: * program, který vytiskne sám sebe - Jakub Saksa * podprogramy: - motivace: - dělení programu na části (pro rozdělení, hledání i dělbu práce) - zabránění opakování - příklad Násobilka - procedury vs. funkce - parametry pořádně: * blok – const, type, var * konstanty * podprogramy - blok, procedura-funkce-program - lokální symboly, viditelnost identifikátorů - formální a skutečné parametry * předávání parametrů podprogramům: - hodnotou - odkazem - konstantní parametry * kdy jsou proměnné stejného typu… a proč nelze definovat ppgm s parametrem array[] * příklad: 10 nejčastějších slov ze souboru * programování shora // ladění zdola 26.10.2015: * pole – proč (uložit víc hodnot) - pole 1..N použití a deklarace nepřesně - načtení, uložení, vypsání v klesjícím pořadí... * ordinální typy, výčtové typy, interval * pole pořádně - příklad: kódování - příklad: četnosti znaků ! - odstrašující příklad nehlídaného přetečení (...pole do jiných proměnných) => deklarace typu – type * for-cyklus - continue, break - dosazení do řídící proměnné (nedělat!) * vyhledávání v poli - lineárně - pomocí zarážky * typované konstanty v BP * znakové řetězce - ukončovací znak x délka - typ string //- řetězení - copy, pos * DÚ: program, který vytiskne sám sebe 19.10.2015: * složitost algoritmů - příklady a jejich složitosti - vyhledávání v krabici s účtenkami - vyhledávání v setříděném telefoním seznamu - umocňování na N-tou – rychlý algoritmus - převod do dvojkové soustavy * typ boolean - zkrácené vyhodnocování = Př: počet čísel ze vstupu, pro která ln(sin(x)) > -2 * typ char - požadavky na kódování číslic a písmen - hodnota znaku - Hornerovo schema - PGM načítání čísla * volby kompilátoru - nastavování pomocí direktiv {$písmeno} * textové soubory - pojem - standardní vstup, standardní výstup - přesměrování vstupu a výstupu - oddělovač řádek, ukončovač souboru - využití CR pro (kontrolní) tisky - eof(f) vs. SeekEof(f) - příkaz read - příkaz write - proč je potřeba zavírat soubory // - použití {$I-} reset(f); // - {$I+} if IOResult... - append - proměnná FileMode 12.10.2015: * čísla v počítači (přesná a nepřesná) => integer a real * typ integer - operátory, priority, funkce - representace v paměti - doplňkový kód * typ real, operátory, funkce, problémy s porovnáním * složitost algoritmů - pojem, k čemu - složitost jako funkce velikosti vstupních dat - časová, paměťová, přelévání mezi nimi - v nejhorším, v průměrném případě - asymptotická složitost, O() - příklady a jejich složitosti - algoritmus vlny a výměna paměti za čas - test prvočíselnosti * typ boolean - PGM monotonie 5.10.2015: * o čem to bude * pokus o vymezení pojmů programování, program, algoritmus * algoritmy: - sčítání dvou čísel v desítkové soustavě - Euklidův - nejkratší cesta koněm na šachovnici - algoritmus vlny - hledání v bludišti - backtracing * typické vlastnosti algoritmu * dokazování správnosti algoritmu - korektnost - částečná správnost - invariant - priklad s lamanim cokolady - konečnost - metoda s ohodnocením stavů výpočtu * formalizovaný zápis algoritmů - pojem proměnné, typ - přiřazovací příkaz, příkazy vstupu a výstupu - řízení běhu programu - pomocí skoku - strukturované programování - podmíněný příkaz - složený příkaz - cykly while a repeat-until * příklady - vypsat největší číslo z neprázdné řady ukončené nulou, která se nepočítá - volba cyklu - while x repeat-until - invariant - jeho nastavení na začátku - jeho udržení v kroku cyklu