20.05.2020: Ř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 * OCR - ...hledejte řešení v určitém tvaru - větší počet bodů ...a odolnost proti chybě * vodovodní baterie - řešení 13.05.2020: * Výjimky * Generické metody a třídy - omezení where - interface * Panoptikum OOP jazyků * Automatické testy: NUnit * Hygiena programování - oddělovat činnosti - pracovní deník - ToDo-list, bug-list, issue tracker - správa versí - Automatické testy 06.05.2020: * Grafy, reprezentace a algoritmy - jen výčet s pár příklady: - definice graf, orientovaný graf - representace grafu: - matice sousednosti - matice incidence (HxV) - seznam následníků - definice sled, tah, cesta, kružnice - souvislost - prohledáním, zda cesta odevšud všude - union-find - jestli je strom - souvislý a bez kružnic - bez kružnic a má jen jednu komponentu - souvislost (nebo ne-kružnice) a správný počet hran - nejkratší cesta - Dijkstrův algoritmus - Bellman-Forduv algoritmus: - Floyd-Warshalluv algoritmus - minimální kostra - Kruskal - Boruvka - Jarnik/Prim - maximální kostra - nejdelší cesta - topologické uspořádání --- výpadek spojení --- * optimální vyhledávací strom - co to je a nalezení dynamickým programováním 29.04.2020: * hašování: - co to je - příklad - hašovací funkce (a její vady) - třída HashSet<> * příklad zkouškového příkladu: překládání čtverečkovaného papíru 22.04.2020: * měření času - DateTime, TimeSpan, měření času - String vs StringBuilder * delegáty - jako proměnná - jako parametr funkce: - +=, -= - anonymní funkce, => * vlákna v C#: - using System.Threading; - 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 15.04.2020: * zkoušky * příklad zkouškového příkladu - ANKETA * diagram toku dat (data-flow diagram) 08.04.2020: Grafika v C# (WinForms) * Graphics - Získání - this.CreateGraphics() * Pen - Pens (properties) - New Pen * Color - Připravené (properties) * Pero – ...Cap * 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 01.04.2020: 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) - složitost paměťová a časová - příklad: optimální uzávorkování násobení matic 25.03.2020: 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 18.03.2020: Objektový návrh * proč * UML 2.0 * diagram tříd * sekvenční diagram * principy a pravidla (SOLID) - Single Responsibility Principle - Open–closed principle - Liskov substitution principle - Interface segregation principle - Dependency Inversion Principle - Law of Demeter - DRY - High cohesion, Low coupling * CRC cards * Návrhové vzory 11.03.2020: Diskrétní simulace II * co bude jinak u jiného modelu - třídy - události - reakce na události * návrh modelu - pomůcka diagram stavů * Příklad: obchodní dům * Implementace 04.03.2020: Diskrétní simulace: * úloha s hromadou písku * Model - Zjednodušený, jen některé atributy * Simulace spojitá vs. diskrétní Program: - TypUdalosti - C# enum - Udalost - Kalendar - Auto - Model * 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čů 26.2.2020: * syntaxe C# - proměnná = místo v paměti - hodnotové a referenční typy - podmínka, cyklus – jeden! příkaz - předávání parametrů funkcím - pole - pevná velikost - vícerozměrné pole - zubaté pole Objekty: * http://ksvi.mff.cuni.cz/~holan/oop.txt * deklarace, členské proměnné * inicializace 0 * konstruktor, this - vice konstruktorů - výchozí konstruktor bez parametrů * Př: Pes, Stekni() * dědičnost - co to je, co se dědí - Př: VelkyPes, : base(…), Stekni() - Problem s konstruktorem //- …implicitní konstruktor mizí ! - konstruktor - base - Problem s prepsanou metodou Stekni2x - virtuální metody, hrachová polévka, VMT * Polymorfismus - abstraktní metoda, abstraktní třída * Statické členy a třídy * atributy viditelnosti, zapouzdření * properties 19.02.2020: organizační záležitosti * Zápočty – program, zápočtový test * zkouška – písemka, ústní, jaká písemka * obsah – programování, meta-algoritmy, jazyk C#, techniky, konstrukce, SWING * slajdy a zdrojové texty – na webu objektově orientované programování * proč: - organizace kódu - vyšší odolnost proti změnám - CO x JAK - Uvažování v problémové doméně - Historie (Smaltalk, Simula 67, 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 jazyk * C#, MS 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 - proměnná – jiný význam (= místo v paměti) - 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 Pythonu - hodnotové a referenční typy * čtení čísel – problém – třída Čtečka 07.01.2020: * příklad PočetDní - ošklivý začátek a konec => CisloDne - fce PocetDnu - PocetDni(*[int(x) for x in input().split()]) - zkoušení ruce-oči * nahradit ruce * nahradit oči * testovaci funkce a počítání testů a chyb - snadne testovani => hodně testů - testovat okrajové případy - chyby mohou být i v testech... - pouštět jen když # if __name__==__main__ - import sys // sys.path.append("../..") * == unit-testy * nevýhody: - testy v deploy-kódu - psát si sám porovnávání * modul unittest - testovací případ - class TestCase(unittest.testCase): - def test.... - assert * metodika TDD: Test-Driven Development - příklad: fce Podil( string ): return 7 - pozitivni testy x negativni testy - chybové kódy nebo výjimky => jakXXX - failure vs. error * vymýšlení chyb – tester = změna přístupu - out of the box: špatný typ parametru! - self.assertRaises = očekávaná výjimka - další druhy testů * k Funkcím: - proměnné - parametry - lambda - closure 17.12.2019: Moduly 2 * doplnit a uvést na pravou míru - doplnit: dependency hell - uvést na pravou míru: bez používání sw 3.stran se neobejdeme * 2 balíčky: Matplotlib a NumPy Matplotlib * knihovna, 18 let, support by neziskovka * matplotlib.pyplot = interface ala MATLAB - ne-objektový přístup - ne-objektový přístup – viz Turtle, turtle.py (když nemá objekt, tak si ho vytvoří) * plot(), show() - jen y - xy - body místo čar - více grafů - osy = automaticky, axis( [0,10,0,10] ) - popisky os - bar - subplot( sizex-sizey-poradi ) - neblokující show(...) - ukládání obrázku do souboru NumPy * knihovna, 14 let, support by neziskovka * vícerozměrná pole * vytvoření pole: - np.array( [1,2,3,4] ) * prvky mají TYP np.dtype * změna typu: af = a.astype( 'float64' ) - np.arrange(20) = vyplní hodnotami - b = np.array([(1.5,2,3), (4,5,6)]) * seznam seznamů = vícerozměrné pole - uvést typ při vytváření - hodnoty * np.zeros * np.ones * np.empty = co, zrovna leží v paměti * default typ = float64 * arange * np.random.random = [0.0, 1.0) - změna tvaru = shape, resharpe - operace - maticové operace - dosazení - výběr podle indexů * Matplotlib & NumPy * Příklady: - HRA: odebírání zleva/zprava - Minimax - negamax – prohledávání: Loupežníci - heuristika 10.12.2019: Moduly * jmenný prostor * dir() - Př: cyklus přes dir(math) a __doc__ * import – možnosti - vytvořit modul * __name__ * Proč vytvářet moduly * cizí moduly: standardní knihovna - Př: měření času pomocí time: - Př: random.randint * odbočka: dokumentační komentáře: - __doc__ - help - help( random.Random ): __getstate__ * Př: urllib.request * balíček - co to je - PyPI 204,421 projects 1,536,788 releases 2,288,324 files vs 208,413 projects 1,576,339 releases 2,362,506 files * problémy (temná strana) - že se to programování posouvá od vymysli k najdi/nastuduj - cizí kód - bugy, verse - zpětná kompatibilita - Př: 29.02.1900 Excel - Př: help( random.Random.__getstate__ ) //- dependency hell Příklad: dlouhá čísla - e: * 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 03.12.2019: * předehra: čtení Z a psaní DO souborů * ...proč zavírat soubory * Chyby: syntaktické, běhové, sémantické * Výjimky jako zpráva o běhové chybě - jak číst výpis výjimky - co se děje, když nastane výjimka (vynořování ze zásobníku volání) - odchycení výjimky: - try-except - except TYP - více except-bloků - except bez typu (nedělat!) - except – proměnná (lokální v except) - znovu-vyvolání: raise - Příklad: existence souboru = používat výjimky jen na výjimečné stavy - finally * vlastní vyvolání výjmky - BaseException - vlastní typy - výjmky vs. návratové kódy * Assert * Defenzivní programování Příklad: * prohledávání šachovnice - list comprehension - abstraktní seznam, fronta, zásobník - prohledávání do hloubky a do šířky - vlna vs backtracking - přidat překážky 26.11.2019: * Funkce definované ve třídě: 1) funkce instance/objektu 2) statická funkce 3) funkce třídy - dekorátory (NEBUDU VYSVĚTLOVAT) - parametr cls - TYP je taky objekt - příklad: class-method vracející nový objekt (náhražka více konstruktorů) - příklad: class-method vracející dvojici nových objektů - int(), str()... jsou třídy, ne funkce * Proměnné definované ve třídě: 1) proměnné instance/objektu 2) proměnné třídy - příklad: počitadlo vytvořených objektů - zmatek: proměnná třídy jako výchozí hodnota proměnné objektu - pokud v něčem nemáte jasno, tak to nepoužívejte! * Příklady: - čtečka čísel - aritmetický výraz - konstruktor - vytváření vnořeným voláním - funkce Hodnota - funkce Prefix - funkce ZeStringu 19.11.2019: * Dynamické proměnné - ukazatel - Halda - Garbage collector * Objekty - Společně data a funkce (metody) - Proč - Pojmy OBJEKT a TŘÍDA - Dědičnost, násobná dědičnost, interface * Objekty v Pythonu - Definice - Funkce a parametr self - Konstruktor - Příklady: - Komplex - Seznam slov pomocí listu - Seznam slov pomocí slovníku - Dědičnost - Volání funkce předka - Polymorfismus - Abstraktní třída - Duck typing - Zapouzdření – viditelnost atributů - Další příklady: Prvek a LSS 05.11.2019: * příklady na rekursi: - výpočet hodnoty výrazu rozkladem na podvýrazy - hledání cesty koněm na šachovnici NxN * dictionary * textové řetězce obecně a typ string v Pythonu - výstup pomocí šablon * (letmo) tuple (n-tice) * textové soubory - ideál, skutečnost - (některé) problémy s nejednotným formátem mezi různými operačními systémy 22.10.2019: * rozklad problému na podproblémy a podprogramy - programování shora x programování zdola - psaní a ladění shora x zdola - operátor * (rozbalení seznamu parametrů) * rekurse - volání sebe sama - musí obsahovat nějaké větvení, jinak by byla nekonečná - zásobník volání a jeho zobrazní ve VisualStudiu - klady a zápory rekurse - příklady - faktoriál - N-tý prvek Fibbonacciho poslopnosti - exponenciální složitost - náprava ukládáním výsledků - hanojské věže 15.10.2019: * funkce (podprogramy) * příklad tabulka násobilky - formát v příkazu print # print( "%3d"% i, end=" " ) * Proč používat podprogramy * Co potřebujeme umět - Jak definovat novou funkci - Jak vracet výsledek - Jak popsat parametry (více možností) - Jak volat funkci - Způsoby předávání parametrů - Viditelnost proměnných (a funkcí) - Funkce B definovaná uvnitř funkce A - Pořadí hledání významu identifikátoru - Kdy je funkce známá * Příklad: - přečtení jednoho čísla ze vstupu (a zbytek řádky) 08.10.2019: * Složitější datové typy * Proměnná = ODKAZ na hodnotu (obrázek s šipkou) = budu připomínat ještě mockrát, zdroj chyb! * String - přístup ke znaku - neměnný – dosadit do znaku nelze - slice * Kód znaku * List * For-cyklus * Range * Příklady práce s listem: - list listů ("tabulka") - součet hodnot ze vstupního řádku - vlastní převod string-int (Hornerovo schema, bez názvu) 01.10.2019: * Předmět NPRG030 Programování I. - Zkouška v létě - Zápočet, podmínky určuje cvičící, obecně docházka, DÚs, zápTest, zápPgm - mj-cvičení pro pokročilé * Co to je programování - Algoritmus - Vlastnosti algoritmu - Zápis algoritmu => jazyk * Jazyk Python - verse 3 * Nástroje – překladače interpret… - IDLE - IDLE-Editor, uložení, spuštění - Spuštění .py souboru poklikáním - Visual Studio - Krokování - Náhled proměnné - Watch - Červené změněné hodnoty * print() * dosazení * input() - přetypování * řízení běhu programu - if, while - odsazení: tabulátor x mezery - a problém - VS: Ctrl-R+W = Edit/Advanced/View WhiteSpace * Jednoduché příklady: - Čísla 1..100 - Prvočísla 1..100 * Co by taky šlo: - Re-use = používat to, co už je hotovo - svoje i cizí části kódu - Posun Python – více na výpočty „pro sebe“ než pgm, který si někdo koupí a za který ručím = potřebujeme kompromis * od začátku: * Hodnoty, typy - Čísla - Int, float * Proměnné - spíš jmenovka než přihrádka, problém více jmen pro stejnou hodnotu * Příklady: - želvy, dosazení NENÍ kopie!