Co bylo na minulých přednáškách z NPRG030/NPRG031 Programování I/II v roce 2017/18 ================================================================================== 23.05.2018: Ř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 - rodičovské investice * historka o magnetofonu - ...podívejte se z odstupu - nonius * OCR - ...hledejte řešení v určitém tvaru - větší počet bodů //a odolnost proti chybě * vodovodní baterie - řešení 09.05.2018: * Ještě k vláknům: - thread safety - příklad: Random * hledání k-tého prvku - postupným vybíráním - setříděním - QuickSort-like lineární algoritmus * zkoušky a příklad u písemky - není potřeba zápočet - shrnutí: 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ů * 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 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 02.05.2018: * delegáty - jako proměnná - jako parametr funkce: - +=, -= - anonymní funkce, => * vlákna v C#: - Thread, t.Start90 - 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 - k čemu vlákna - GUI vs. výpočet (aby dlouhý výpočet neblokoval reakce GUI, spustí se v novém vlákně) * C#: aplikace s více okny: - dalsi okno - hlavni okno - show: Show() - dialog: ShowDialog(); - button.DialogResult - kontrola spravnosti: událost FormClosing: E.Cancel = true; - dosazení/čtení hodnot z komponent: funkce, property - Form.AcceptButton, Form.CancelButton - Dispose okna po Show() a Close() => odchytit FormClosing, test Modal, abort a Hide(). 25.04.2018: * Grafy: - 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|) resp. - 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 - 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) * topologické uspořádání (už jsem ukazoval): - test acykličnosti - jakou reprezentaci použít (seznam následníků) - => nejdelší cesta * zkoušky - příklad příkladu: kontrola řešení úlohy s poštou * zkoušky - příklad příkladu: počet různých způsobů jak poskládat papír 18.04.2018: * 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 - Funkce na otestování jednoho volání - Funkce na otestování funkce - 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 - Změna hlavičky funkce - Vracet chybový kód i výsledek – výsledek vs. var/out-parametry - unit-testy ve Visual Studiu - projekt a solution, References * Handle (HWND) * Pošta jako ukázka „těžkého příkladu“ - návrh programu pro kontrolu řešení 11.04.2018: * 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 * výběr obdélníka a kopie býřezu pomocí Bitmap.Clone() a Graphics.DrawImage() 04.04.2018: * dynamické programování - příklad: Počet různých her odebírání zápalek pro daný počáteční počet - příklad: optimální vyhledávací strom - a jeho hledání dynamickým programováním * hashování - princip, náhodnost (v BVS) - hashovací tabulka, hashovací funkce - náhodný generátor - System.Collections.HashTable - jak si naprogramovat hashovací tabulku - ...a vliv hashovací funkce na rychlost 28.03.2018: * 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: počet (tvarů) binárních vyhledávacích stromů s N vrcholy - příklad: optimální uzávorkování násobení matic - složitost paměťová a časová 21.03.2018: 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í - Is - Kalkulačka 14.03.2018: 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) C#, .NET: * System.IO.StreamReader, System.IO.StreamWriter * generické funkce, generické třídy, List 07.03.2018: 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 A, Písek v B * Čas * Fronta v A * 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čů ################ Poznámka: V modelu (ne v C#, v logice) je jedna chyba, zkuste na ni přijít 28.02.2018: * objekty - konstruktor - dědičnost - virtuální metody - polymorfismus - abstraktní třída, abstraktní metoda - statické proměnné a funkce (Console, Math) 21.02.2018: * 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 - 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 08.01.2018: * 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 - ExitProc, ErrorCode, ErrorAddr * textove soubory - append - promenna FileMode (proc nekdy nejde otevrit soubor pro cteni) * Lo-level drobnosti (Borland)Pascalu: - absolute - prekryvani promennych - video-RAM - tick a mereni casu - Mem[] 18.12.2017: * 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 (Fobbonacciho stromy) - Vyvažování – rotace - Kolikrát vyvažovat - B-stromy - Definice - operace 11.12.2017: * 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, 6 - příklad: zápalky 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ů) - 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 04.12.2017: (přednášel doc. Töpfer) * vnitřní třídění: - přímé metody (SelectSort, InsertSort, BubbeSort) - halda a operace na haldě, implementaci haldy v poli, konstrukce haldy v lineárním čase - HeapSort - princip Rozděl a panuj - QuickSort - MergeSort - složitost problému vnitřního třídění pro nejhorší případ - třídění počítáním (CountingSort) a přihrádkové třídění (BucketSort). 27.11.2017: 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) * Příklady na rekursi a backtracking: - loupežníci / batoh - vypsání všech permutací - Hanojské věže * BP/FP: Call stack 20. 11. 2017: * Ad spojové 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) * 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 - vyhodnocení INFIXu podle gramatiky ( = O(n) ) - předběžná deklarace forward //* vytvoření stromu z různých notací //* převody mezi notacemi (vytvořit strom a vypsat) * abstraktní datový typ, 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). * Rekurse: příklad: 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) 13. 11. 2017: * 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 - s nalezením posledního - pamatovat si poslední * Kreslit si obrázky! * dispose - memory leak - přístup do cizí paměti - co je garbage collector * halda a správce haldy - vrchol a seznam děr (kde ukládat?) - MemAvail, MaxAvail * vytvoření seznamu pomocí funkce 06. 11. 2017: * 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ů - Příklady: - Vypsání všech variací s opakováním - Vypsání všech variací bez opakování - proskákání šachovnice koněm - 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" 30. 10. 2017: * program, který vytiskne sám sebe * 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 ladění zdola * příklad: 20 nejčastějších slov ze souboru 23. 10. 2017: * pole – proč (uložit víc hodnot) - 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ů ! - 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!) * Algoritmus: Eratosthenovo síto * 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í a jak správně načítat string po znacích - copy, pos * Na rozmyšlení: program, který vytiskne sám sebe 16. 10. 2017: * 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í * 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 eof v Win x Linux!! (CodEx) - typ text v BP (assign, reset/rewrite, close) - proč zavírat soubory = příklad * direktivy kompilátoru //- {$I-}, IOResult 9.10.2017: * Příklad: nalezení maximální hodnoty z posloupnosti čísel ukončené -1 - 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 2.10.2017: * 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 čtyř čísel zadaných jako vstup