====== Přehled ====== - Softwarové inženýrství - Byznys modelování. Diagramy aktivit a tříd. - Specifikace požadavků. Diagramy scénářů užití (Use Case) a sekvenční diagramy. - Analýza a návrh systému. Diagramy tříd, relace mezi třídami a organizace modelů. - //Modelování dynamického chování objektů pomocí sekvenčních a stavových diagramů.// - Implementace systému. Diagramy komponent a nasazení. - Formální metody specifikace. Jazyk OCL a způsob jeho použití. - Návrhové vzory tvořící. Vzory Továrna, Tovární metoda a Prototyp. - Návrhové vzory strukturální. Vzory Kompozit, Adaptér, Dekoratér a Proxy. - Návrhové vzory chování. Vzory Řetěz zodpovědnosti, Příkaz, Iterátor, Pozorovatel, Stav a Strategie. - Využití abstrakce při návrhu programových systémů - abstraktní datové typy, abstrakce algoritmů, rekurze. - Komponentní technologie - principy, struktura komponent, vlastnosti, metody, události. - Návrh aplikací v prostředí Internetu, architektury, webové služby, zabezpečení. - **Základy teoretické informatiky** - Konečné automaty, regulární výrazy, uzávěrové vlastnosti třídy regulárních jazyků. - Bezkontextové gramatiky a jazyky. Zásobníkové automaty, jejich vztah k bezkontextovým gramatikám. - Matematické modely algoritmů - Turingovy stroje a stroje RAM. Složitost algoritmu, asymptotické odhady. Algoritmicky nerozhodnutelné problémy. - Třídy složitosti problémů. Třída PTIME a NPTIME, NP-úplné problémy. - Pojem relace, homogenní a heterogenní relace, operace s relacemi, vlastnosti. Typy binárních relací. Relace ekvivalence a relace uspořádání. - //Obecný pojem operace a obecný pojem algebra. Algebry s jednou a dvěma binárními operacemi. Homomorfismy. Grupy, Booleovy algebry.// - Obecná rezoluční metoda a logické programování: rezoluční pravidlo a algoritmus unifikace v predikátové logice 1. řádu. - **Pojem (přímého a nepřímého) důkazu. Úplnost důkazových kalkulů v predikátové logice 1. řádu, (ne)rozhodnutelnost, neúplnost teorií obsahujících aritmetiku.** - **Softwarové inženýrství** - Deklarativní programovací jazyky, význam funkcionálního a logického programování. - //Struktura a činnost překladače, tvar zdrojového a cílového programu. Interpretační a kompilační překlad. Fáze překladu, vnitřní struktura překladače.// - Vyšší programovací jazyky a jejich moderní rysy (správa paměti, implementace objektově orientovaných prvků, výjimky). - UML, základní diagramy a použití. - Návrhové vzory, jejich rozdělení a příklady. - //**Atributovaný syntaxí řízený překlad. Sémantické akce.**// - **Softwarový proces, postup a metody tvorby softwarového produktu.** - Informační systémy - //Analýza datová, normální formy relací. Analýza funkční, dynamická - metody a nástroje.// - Návrh implementace, metody a nástroje. - Paralelní procesy v databázích. Transakce, zamykání, uváznutí, dvoufázový protokol. - Architektury databázových systémů. Distribuované báze dat, definice, centralizace řízení, rozmístění dat. - Architektury informačních systémů v prostředí Internetu. - Počítačová grafika - Základní metody výstupu grafické informace. Technické a softwarové prostředky pro grafický výstup. - Reprezentace barev (systémy RGB, HSV, HLS, CMY, CMYK). - Komprese obrazu, zejména ztrátová komprese JPEG a MPEG. - **Počítače a sítě** - **Architektura univerzálních mikroprocesorů. Principy urychlování činnosti procesorů.** - **Základní vlastnosti monolitických počítačů a jejich typické integrované periférie. Možnosti použití.** - **Struktura OS a jeho návaznost na technické vybavení počítače.** - **Protokolová rodina TCP/IP.** - Metody sdíleného přístupu ke společnému kanálu. - Problémy směrování v počítačových sítích. Adresování v IP, překlad adres (NAT). - Bezpečnost počítačových sítí s TCP/IP: útoky, paketové filtry, stavový firewall. Šifrování a autentizace, virtuální privátní sítě. ====== Softwarové inženýrství ====== ===== Byznys modelování. Diagramy aktivit a tříd. ===== * aktivitní diagram: aktivita, tok, rozhodnutí, začátek/konec, fork/join * use-case diagram * BPMN, eEPC ===== Specifikace požadavků. Diagramy scénářů užití (Use Case) a sekvenční diagramy. ===== ===== Analýza a návrh systému. Diagramy tříd, relace mezi třídami a organizace modelů. ===== ===== Modelování dynamického chování objektů pomocí sekvenčních a stavových diagramů. ===== ===== Implementace systému. Diagramy komponent a nasazení. ===== * diagram komponent: komponenta, rozhraní, závislost; různé stereotypy: infrastructure, database, application * diagram nasazení: uzly, komponenty ===== Formální metody specifikace. Jazyk OCL a způsob jeho použití. ===== * konečný automat * algebraické specifikace - představení, popis, signatury, axiomy * OCL * deklarativní, bez vedlejších efektů, napojení na UML (napojení na MOF - Meta-Object Facility) * context - třída, metoda * typy - Boolean, Integer, Real, String * conditions - invariant, pre, post, body, def, init, derive * operátory - and, or, not, implies, promenna@pre * části - if/then/else/endif, let/in, self, * kolekce * Set, Bag, OrderedSet, Sequence * sum, size, count(obj), asSet (a další), append, prepend, in/excludes, in/excludesAll, in/excluding, indexOf, isEmpty * forAll, exists, collect, select, reject, isUnique, iterate(iter; accum | expres), sortedBy ===== Návrhové vzory tvořící. Vzory Továrna, Tovární metoda a Prototyp. ===== * Singleton * Tovární metoda je na jeden typ, Továrna na více příbuzných typů * Prototyp je na klonování ===== Návrhové vzory strukturální. Vzory Kompozit, Adaptér, Dekoratér a Proxy. ===== ===== Návrhové vzory chování. Vzory Řetěz zodpovědnosti, Příkaz, Iterátor, Pozorovatel, Stav a Strategie. ===== * Řetěz zodpovědnosti - každý má následovníka * Strategie - napojená na Context ===== Využití abstrakce při návrhu programových systémů - abstraktní datové typy, abstrakce algoritmů, rekurze. ===== * oddělení implementace, rozhraní, implementace v OOP (zapouzdření, integrita vnitřku * diagram signatury * operace typu konstruktor, selektor a modifikátor * asociativní pole, zásobník, seznam, fronta, iterátor, množina, zobrazení, textový řetězec, strom, halda ===== Komponentní technologie - principy, struktura komponent, vlastnosti, metody, události. ===== ===== Návrh aplikací v prostředí Internetu, architektury, webové služby, zabezpečení. ===== ====== Základy teoretické informatiky ====== ===== Konečné automaty, regulární výrazy, uzávěrové vlastnosti třídy regulárních jazyků. ===== * DKA: stavy, vstupní abeceda, přechodová funkce, počáteční stav, přijímací stavy * NKA: přechodová funkce a počáteční stavy jiné * normovaný tvar * jazyk KA * uzavřený vůči: sjednocení, průniku, zřetězení, iteraci, doplňku, rozdílu, levému a pravému kvocientu * regulární výrazy, konstrukce automatu, převod ===== Bezkontextové gramatiky a jazyky. Zásobníkové automaty, jejich vztah k bezkontextovým gramatikám. ===== * CFG = neterminály, terminály, startovací neternimál, pravidla * zápis pravidel * levá a pravá derivace, derivační strom, jednoznačná gramatika * zásobníkový automat = stavy, vstupní abecena, zásobníková abeceda, počáteční stav, počáteční symbol zásobníku, přechodová funkce * přijímající, kdyz skončí s přecčteným slovem a prázdným zásobníkem ===== Matematické modely algoritmů - Turingovy stroje a stroje RAM. Složitost algoritmu, asymptotické odhady. Algoritmicky nerozhodnutelné problémy. ===== ===== Třídy složitosti problémů. Třída PTIME a NPTIME, NP-úplné problémy. ===== ===== Pojem relace, homogenní a heterogenní relace, operace s relacemi, vlastnosti. Typy binárních relací. Relace ekvivalence a relace uspořádání. ===== * reflexivni, tranzitivni, symetricka, antisymetricka, asymetricka * ekvivalence = refl, sym, tran * castecne usporadani = refl, tran, antisym * ostre usporadani = asym, tran * zobrazeni ===== Obecný pojem operace a obecný pojem algebra. Algebry s jednou a dvěma binárními operacemi. Homomorfismy. Grupy, Booleovy algebry. ===== * operace = postup ze vstupů na výstupy * nulární, unární, binární, ternární * aritmetické, logické, vektorové, ... * algebra = část matematiky studující operace a relace; daná nosičem a množinou operací * grupoid = algebraická struktura s jednou operací; konečný nosič = konečný grupoid; * pologrupa - asociativní * monoid - jednotkový prvek * grupa - inverzní prvky * Abelova grupa - komutativní * okruh - dvě operace * těleso - má inverzní prvky; (Z, +, .) = okruh, (R, +, .) = těleso * homomorgismus = zobrazení mezi grupoidy * Booleova algebra: (A, ^, v, -, 0, 1) * komutativita, distributivita, neutralita 0 a 1, komplementarita, nedegenerovanost ===== Obecná rezoluční metoda a logické programování: rezoluční pravidlo a algoritmus unifikace v predikátové logice 1. řádu. ===== * **skolemizace**: EI, přejmenovaní proměnných, elim. kvant., přenesení negace doprava, přenesení kvantifikátorů doleva, doplnění konstant a funkcí, distribuce, zjednodušení * unifikace * rezoluční pravidlo ===== Pojem (přímého a nepřímého) důkazu. Úplnost důkazových kalkulů v predikátové logice 1. řádu, (ne)rozhodnutelnost, neúplnost teorií obsahujících aritmetiku. ===== * teorémy, hypotézy * korektnost: vše dokazatelné je pravdivé * sémantická úplnost: vše pravdivé je dokazatelné * Hilbertova snaha o popsání matematiky, Godel dokazal neúplnost (něco nelze ani dokázat ani vyvrátit) * PL1 je úplný * rozhodnutelnost teorie * Robinsonova aritmetika (konečně axiomatizovatelná) + schéma axiomů indukce = Peanova aritmetika (nekonečně axiomatizovatelná) * rekurzivní axiomatizovatelnost - algoritmus v konečném čase rozhodující o axiomu ====== Softwarové inženýrství ====== ===== Deklarativní programovací jazyky, význam funkcionálního a logického programování. ===== * Prolog * SQL * Lisp, Scheme * Haskell * čisté funkce - deterministické, bez vedlejších efektů * striktní a nestriktní vyhodnocení - pořadí a použití nekonečných množin apod. ===== Struktura a činnost překladače, tvar zdrojového a cílového programu. Interpretační a kompilační překlad. Fáze překladu, vnitřní struktura překladače. ===== * lexikální analýza - regulární jazyk * syntaktická analýza - bezkontextová gramatika * sématická analýza - typová kontrola * mezikód - tříadresní kód, zásobníkový kód - optimalizace * tabulka symbolů * preprocesor ===== Vyšší programovací jazyky a jejich moderní rysy (správa paměti, implementace objektově orientovaných prvků, výjimky). ===== * interpretované / kompilované * imperativní (strukturované, objektové) / deklarativní (funkcionální, logické) * správa paměti: ruční / automatická * přidělování: zásobník / halda (first fit, best fit, buddy systém) * regenerace: dvoufázové značkování / počítání odkazů; defragmentace * procesy a vlákna: synchronizace * výjimky * zapouzdření, dědičnost, polymorfismus ===== UML, základní diagramy a použití. ===== * **struktura**: třídní, objektový, komponentní, package, deployment * **chování**: aktivitní, sekvenční, stavový, use-case ===== Návrhové vzory, jejich rozdělení a příklady. ===== * **tvořící** - továrna, prototyp, singleton * **strukturální** - kompozit, adaptér, proxy, dekorátor * **chování** - řetěz zodpovědnosti, příkaz, iterátor, pozorovatel * **antivzory** - magické tlačítko (kód v UI), cyklická závislost ===== Atributovaný syntaxí řízený překlad. Sémantické akce. ===== ===== Softwarový proces, postup a metody tvorby softwarového produktu. ===== ====== Informační systémy ====== ===== Analýza datová, normální formy relací. Analýza funkční, dynamická - metody a nástroje. ===== * konceptuální model, logický model, fyzický model * Armstrongova pravidla: triviální závislost, tranzitivita, kompozice, dekompozice * normální formy * 1.NF - atomické atributy * 2.NF - úplná závislost na klíči * 3.NF - bez závislosti mezi sekundárními atributy * B-C NF - všechny závislosti obsahují klíč * 4.NF - bez multizávislostí * **datová analýza** - lineární zápis entitních typů, 2x ERD, datový slovník + integritní omezení * **funkční analýza** - funkční požadavky, DFD, minispecifikace * **dynamická analýza** - stavový diagram (stavy, podmínky, akce), životní cyklus entity ===== Návrh implementace, metody a nástroje. ===== * konkretizace analýzy * systémový návrh: HW a SW prostředí, nefunkční vlastnosti, architektura prostředí, časový harmonogram * doplnění funkční analýzy: minispecifikace - algoritmy, transakce, indexy, rozmístění dat, kontrola rozpoznatelnosti stavů, moduly a afinita funkcí * mezní provoz: spuštění a instalace, zálohování, archivace, pád a zotavení * doplnění systémových funkcí: uživatelé, logování ===== Paralelní procesy v databázích. Transakce, zamykání, uváznutí, dvoufázový protokol. ===== * zpožděná aktualizace, přímá aktualizace, stínové stránkování * zamykání: souborů, tabulek, záznamů, buňek * zámky: sdílený, výlučný * uváznutí (deadlock) * prevence - čekání na všechny zámky * plánovače * časová razítka * detekce a ukončení transakce ===== Architektury databázových systémů. Distribuované báze dat, definice, centralizace řízení, rozmístění dat. ===== * centrální, file-server, klient-server (+ distribuované) * distribuovanost - centralizované / decentralizované řízení * rozmístění - replikace, fragmentace * cloud ===== Architektury informačních systémů v prostředí Internetu. ===== * třívrstvé architektury * tenký / tlustý klient * komponenty různých architektur: J2EE, ASP.NET ====== Počítačová grafika ====== ===== Základní metody výstupu grafické informace. Technické a softwarové prostředky pro grafický výstup. ===== * prostředky pro vstup: tablet, stylus, myš, skener, foťák, kamera * prostředky pro výstup: dočasný - obrazovka (CRT, LCD, plasma), trvalý - tiskárna (jehličky, inkoust, laser) * metody kreslení, vyhlazování čar, ořezávání čar ===== Reprezentace barev (systémy RGB, HSV, HLS, CMY, CMYK). ===== * HSV = hue, saturation, value (brightness); barevný kužel ===== Komprese obrazu, zejména ztrátová komprese JPEG a MPEG. ===== * BMP, PCX - RLE * PNG - LZW * JPEG - převod do YUV (jas + barva) - rozdělení na makrobloky - kvantizace - Huffmanovo kódování * MPEG - rámce: I (celé), P (z minulých), B (z minulých i budoucích) ====== Počítače a sítě ====== ===== Architektura univerzálních mikroprocesorů. Principy urychlování činnosti procesorů. ===== ===== Základní vlastnosti monolitických počítačů a jejich typické integrované periférie. Možnosti použití. ===== ===== Struktura OS a jeho návaznost na technické vybavení počítače. ===== * procesory * procesy * paměť * soubory * v/v * síť * monolitické / modulární / otevřené ===== Protokolová rodina TCP/IP. ===== * OSI vrstvy: Physical, Link, Network, Transport, Session, Presentation, Application * TCP/IP vrstvy: Network, Internet, Transport, Application * protokoly: SMTP, POP3, FTP, Telnet, DNS, TFTP, SSH, SNMP * TCP / UDP * ARP, RARP - překlady IP adres na MAC adresy * DHCP, BOOTP * ICMP - echo a další ===== Metody sdíleného přístupu ke společnému kanálu. ===== * Aloha - netestuje médium, používá potvrzování * taktovaná Aloha - redukce kolizního slotu * řízená Aloha - prodlužuje čekání mezi pokusy * CSMA - příposlech na médiu, nutná krátká vzdálenost * p-naléhavost, varianty podle pravděpodobnosti vysílání (testuje volnost kanálu 1x / pokaždé) * CD - jam signál * deterministicky * centrálně: cyklická výzva / binární vyhledávání / na žádost * distribuovaně: rezervace kanálu / logický kruh (token) / virtuální logický kruh (vysílání může začít v předem daném intervalu) ===== Problémy směrování v počítačových sítích. Adresování v IP, překlad adres (NAT). ===== ===== Bezpečnost počítačových sítí s TCP/IP: útoky, paketové filtry, stavový firewall. Šifrování a autentizace, virtuální privátní sítě. ===== * paketový filtr - 2., 3. a 4. úroveň * stavový firewall - 5. a vyšší úroveň - FTP * aplikační brány (proxy firewall) * (D)DoS útoky * VPN - SSL / IPSec