Co bylo na minulých přednáškách z NPRG030/NPRG031 Programování I/II v roce 2018/19 ================================================================================== 22.05.2019: Řešení těžkých úloh: * Motivační úloha: páková baterie * nakreslení grafu - ...řešte jinou úlohu - Graph Drawing Contest 2019! * 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 - rodičovské investice * historka o magnetofonu - ...podívejte se z odstupu - nonius - VASI lights * OCR - ...hledejte řešení v určitém tvaru - větší počet bodů ...a odolnost proti chybě * vodovodní baterie - řešení 15.05.2019: * pošta - řešení dr.Majerecha * hashování - princip - hashovací tabulka, hashovací funkce - náhodný generátor - jak si naprogramovat hashovací tabulku - ...a vliv hashovací funkce na rychlost - System.Collections.HashSet<> * 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ů * 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 – resources, šablony 6. testování 7. dokumentace = ODDĚLOVAT !! Neodbočovat při řešení problému! 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Č (spolu se změnami v kódu – viz verse) 3. bug-list – bug tracking system - issue-tracker, trello 4. správa versí - CVS, SVN, Hg, GiT… - GitHub apod. 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 24.04.2019: * delegáty - jako proměnná - jako parametr funkce: - +=, -= - anonymní funkce, => * vlákna v C#: - měření času pomocí DateTime a TimeSpan - Thread, .Start() - počet jader - může být jinak rychlé v Debug a Build režimu - kdy použít vlákno (aby nezamrzlo GUI) - race-condition - Lock - ...deadlock - k čemu vlákna - GUI vs. výpočet (aby dlouhý výpočet neblokoval reakce GUI, spustí se v novém vlákně) * zkoušky - příklad příkladu: počet různých způsobů jak poskládat papír 17.04.2019: * Grafy (jen výčet toho, co byste měli znát): * representace: - matice sousednosti - matice vzdáleností - seznam hran - matice incidence - 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: nezáporně ohodnocený, souvislý - trvale a dočasně ohodnocené vrcholy - inicializace - krok - jakou reprezentaci použít (seznam následníků) - složitost O(|V|2+|E|) (pole) resp. O((|E|+|V|)log|V|) (halda) - 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 / alespoň jeden z: - Jarníkův/Primův algoritmus - Borůvkův algoritmus (unikátní ohodncení hran) - Kruskalův („hladový“) algoritmus (min. ze všech nepoužitých hran nevytvářejících cyklus) * Faktorová množina aka UNION-FIND * topologické uspořádání (už jsem ukazoval): - test acykličnosti - jakou reprezentaci použít (seznam následníků) - => nejdelší cesta * dynamické programování: - Ad uzávorkování násobení matic: jaká je složitost - příklad: optimální vyhledávací strom * zkoušky - příklad příkladu: kontrola řešení úlohy s poštou 10.04.2019: * C#: výjimky - přístup k chybám: testování PŘEDEMpředem vs. řešení POTOM - try-catch, catch(typVyjimky1 identifikator) - hierarchie, Exception, .Message, .StackTrace - throw - finally - vnořování chráněných bloků - výjimky vs. chybové kódy, neviditelné GOTO * 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 - Porovnání jednoho výsledku - Počítání chyb - Přidávání testů (protože je to snadné) - Rozhodnutí,jak zacházet s chybami – výjimky nebo chybové kódy - Změna hlavičky funkce - Vracet chybový kód i výsledek – výsledek vs. var/out-parametry - unit-testy ve Visual Studiu Dodatečně k finally: https://docs.microsoft.com/en-gb/dotnet/csharp/language-reference/keywords/try-finally Within a handled exception, the associated finally block is guaranteed to be run. However, if the exception is unhandled, execution of the finally block is dependent on how the exception unwind operation is triggered. That, in turn, is dependent on how your computer is set up. 03.04.2019: Dynamické programování - příklad: počet binárních vyhledávacích stromů o N vrcholech Grafika v C# (WinForms) * Graphics - Získání - this.CreateGraphics() * 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 - kopie výřezu pomocí Bitmap.Clone() a Graphics.DrawImage() 27.03.2019: 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 - podmínky: - překrývající se části (jinak bychom použili Divide & Impera) - části optimálního řešení jsou optimální řešení pod-úloh - výměna paměti za čas - snadná cesta: backtracking s ukládáním parametrů a výsledků (memoizace) - příklad: vyhrávající a prohrávající pozice odebírání zápalek pro daný počáteční počet - příklad: nejdelší společný podřetězec - příklad: počet různých cest v orientovaném acyklickém grafu - příklad: optimální uzávorkování násobení matic //- složitost paměťová a časová 20.03.2019: 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 * 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 * Sdílení obslužných metod - Sender - Přetypování "(typ)" nebo "as" - Is - Kalkulačka 13.03.2019: Diskrétní simulace: * úloha s hromadou písku - další model a počet nakladatelů C#, .NET: * generické funkce, generické třídy, List, where, interface, diamond problem * System.IO.StreamReader, System.IO.StreamWriter, using Diskrétní simulace: * V čem se bude lišit jiný model: - Události - Procesy - …a reakce na události - data v Modelu... * 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) * jak mít čitelná vstupní data 06.03.2019: 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í Program: - TypUdalosti - C# enum - Udalost - Kalendar - Auto - Model * Písek v M, Písek v M * Čas * Fronta v M * Použití simulace pro zkoumání variant a OOP-změna pomocí odvozené třídy = Model2 pro různý počet aut // Model3 pro ruzný počet aut a nakladačů 27.02.2019: * objekty - konstruktor - dědičnost - virtuální metody - polymorfismus - abstraktní třída, abstraktní metoda - statické proměnné a funkce (Console, Math) - private, protected, public - a smysl ukrývání - property 20.02.2019: * 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 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 - 2000- C# lead architect - program = sbírka objektů - metoda Main() - žádné "globální" metody ani proměnné, všechno patří nějaké třídě - syntaxe jazyka C# - rozdíly C# proti Pascalu - načítání čísel - ConsoleReadLine a in32.Parse() - string.Split a Covert.ToInt32 - vlastní třída na čtení po znacích 07.01.2019: * Vnější třídění - 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 * typy pro funkce a procedury: - predavane parametry podprogramu - promenne - tabulka hodnot - hledání kořene - CHYBA * hledani na sachovnici pomoci zasobniku a pomoci fronty * ExitProc, ErrorCode, ErrorAddr 17.12.2018: * BVS - definice - vyhledání - přidání - tisk - vymazání * porovnání rychlosti se seznamem v poli - problém nevyváženosti * Vyvážené stromy - Dokonale - AVL - Definice - logaritmická výška (Fibbonacciho stromy) - Vyvažování – rotace - Kolikrát vyvažovat - B-stromy - Definice - operace * aritmetické notace - postavení stromu: stejně jako vyhodnocení - převody mezi notacemi: postavit strom a vypsat * zásobník a fronta v poli - cyklická fronta - počet prvků (nestačí indexy ZAČ a KON) 10.12.2018: * 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, 2, 4, 12 - příklad: zápalky na více hromádkách 7, 5, 3, 1 (Loni v Marienbadu) - problém výpočtu: rychlost/pomalost - řešení problému: cache (ukládat již spočítané výsledky/ohodnocení stavů) = počítat od konce (od konce hry) - 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 - počítání směrem nahoru - 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 - 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 - příklad heuristiky: skakani jezdcem * příklad rekurse - N dam na šachovnici NxN - hloupě (umisťovat jednu dámu kam to jde) - chytřeji (umisťovat jednu dámu jen do jednoho sloupečku) - ještě chytřeji (neznačkovat šachovnici, ale jen volné řádky a diagonály) 03.12.2018: * 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(zac,kon) - 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ů) - 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Í na místě ("in situ") * 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) 26.11.2018: 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 * dělení * postupné testování vytvářených funkcí (programování shora - ladění zdola) * Urychlení backtrackingu: - ukládáním výsledků ("memoizace") - k-té Fibvonacciho číslo - prořezávání, - heuristika - skákání koněm – výběr políčka s nejmenším počtem sousedů: pas/kun.txt - heuristika: nejmenší počet pokračování - loupežníci * Odstraňování rekurse - vlastním zásobníkem - nahradit iterací - jiný algoritmus (k-té Fibbonacciho číslo - sčítat dvě předchozí) 19.11.2018: * Ad spojové seznamy - mazání prvku z konce – postup 1) Jak vypadá běžná situace 2) Jaké vyjímečné situace musíme ošetřit - Prázdný seznam - jednoprvkový seznam - neexistuje předchůdce - neexistuje následník... * 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 * složitější dynamické struktury – stromy * vytvoření stromu funkcí (jako vytvoření seznamu) * vyhodnocení výrazu * výpis – průchod – notace * vyhodnocení v různých notacích - vyhodnocení INFIXu rozkladem na podvýrazy - bylo dříve - vyhodnocení INFIXu podle gramatiky ( = O(n) ) - předběžná deklarace forward * vytvoření stromu z postfixu (z prefixu by to bylo podobné) * abstraktní datový typ, ISA-vztah - Seznam, Fronta, Zásobník - Obecný algoritmus hledání. - Prohledávání do šířky (vlna) a do hloubky (backtracking) = stejný 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). 12.11.2018: * 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 - mazání prvků ze začátku //- ...a z konce * Kreslit si obrázky! * dispose - memory leak - přístup do cizí paměti - garbage collector * rekurse: proskákání šachovnice koněm 12.11.2018: * 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 - mazání prvků ze začátku //- ...a z konce * Kreslit si obrázky! * dispose - memory leak - přístup do cizí paměti - garbage collector * rekurse: proskákání šachovnice koněm 05.11.2018: * dokončení z minula: příklad vypsání nejčastějších slov * Rekurse - příklad: vyhodnocení výrazu rozkladem na pod-výrazy - 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ů - Příklady: - Vypsání všech permutací - Hanojské věže - loupežníci/batoh 29.10.2018: * 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[] * programování shora (dělením úlohy na pod-úlohy) a ladění zdola (od nejmenších podprogramů) * příklad: 20 nejčastějších slov ze souboru 22.10.2018: * pole – proč (uložit víc hodnot, nepřímá adresace) - pole 1..N použití a deklarace nepřesně - načtení, uložení, vypsání v klesajícím pořadí... * ordinální typy, výčtové typy, interval * pole pořádně - příklad: kódování - příklad: četnosti znaků => deklarace typu – type * for-cyklus - continue, break - dosazení do řídící proměnné (nedělat!) * Algoritmus: Eratosthenovo síto * vyhledávání v poli - lineárně - pomocí zarážky * typované konstanty v BP - převod data na pořadové číslo dne * znakové řetězce - ukončovací znak x délka - typ string - řetězení a jak správně načítat string po znacích - copy, pos * Na rozmyšlení: program, který vytiskne sám sebe 15.10.2018: * příklady úloh a jejich složitost - vyhledávání v krabici s účtenkami - vyhledávání v telefonním seznamu - rychlé umocňování * typ boolean * zkrácené vyhodnocování * direktivy kompilátoru //- {$B-} * PGM monotonie * typ char - požadavky na kódování číslic a písmen - hodnota znaku - Hornerovo schema * PGM načítání čísla * textové soubory - pojem - standardní vstup, standardní výstup - přesměrování vstupu a výstupu - oddělovač řádek, ukončovač souboru - příkaz read - příkaz write * Eof-EoLn x SeekEoLn (přeskočí whitespaces) a SeekEof (nic kromě whitespaces) * POZOR na konec řádky ve Win x Linux!! (CodEx) 8.10.2018: * Příklad: nalezení maximální hodnoty z posloupnosti čísel ukončené 0 - 1) přečtení - volba cyklu while/repeat-until - 2) výstup - invariant - a) nastavení na začátku b) udržení v cyklu * čí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 - test prvočíselnosti - algoritmus vlny a výměna paměti za čas 1.10.2018: * 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 větší ze dvou čísel zadaných jako vstup - vypsat největší ze tří čísel zadaných jako vstup - vypsat největší ze všech čísel před nulou