I2 Softwarové systémy

2. Softwarové systémy I2

Garantující pracoviště: Katedra softwarového inženýrství
Oborový garant: doc. RNDr. Tomáš Skopal, Ph.D.

Povinné předměty

¹ Místo předmětu NTIN090 Základy složitosti a vyčíslitelnosti je možné absolvovat dvojici předmětů NTIN062 Složitost I, NTIN064 Vyčíslitelnost I.

² Předmět je povinný pouze pro zaměření Systémové architektury a Spolehlivé systémy; pro ostatní zaměření je povinně volitelný.

³ Předmět je povinný pouze pro zaměření Databázové systémy; pro ostatní zaměření je povinně volitelný.

⁴ Předmět je povinný pouze pro zaměření Softwarové inženýrství; pro ostatní zaměření je povinně volitelný.

Povinně volitelné předměty

Je požadováno splnění povinně volitelných předmětů z následujícího seznamu v rozsahu alespoň 25 kreditů:

¹ Předmět je povinně volitelný pouze pro zaměření Databázové systémy, Softwarové inženýrství, Počítačová grafika; pro zaměření Systémové architektury a Spolehlivé systémy je povinný.

² Předmět je povinně volitelný pouze pro zaměření Databázové systémy, Systémové architektury, Spolehlivé systémy, Počítačová grafika; pro zaměření Softwarové inženýrství je povinný.

³ Předmět je povinně volitelný pouze pro zaměření Softwarové inženýrství, Systémové architektury, Spolehlivé systémy, Počítačová grafika; pro zaměření Databázové systémy je povinný.

Zaměření: Databázové systémy

Zkušební okruhy

1. Formální základy databázové technologie

2. Databázové modely a jazyky

3. Implementace databázových systémů

Zkušební požadavky

1. Formální základy databázové technologie
Relační kalkuly, relační algebry, deduktivní databáze. Relační úplnost. Bezpečné výrazy, ekvivalence relačních dotazovacích jazyků. Věta o tranzitivním uzávěru relace. Sémantika SQL. Datalog, 3 sémantiky a jejich ekvivalence. Datalog s negací, stratifikace. Deduktivní databáze. Rekurze v SQL. Tablo dotazy - statická analýza a optimalizace relačních dotazovacích jazyků. Modelování preferencí, dotazování s preferencemi.

Doporučené předměty: NDBI006 Dotazovací jazyky II, NDBI021 Dotazování s preferencemi 
Rozšiřující předměty: NDBI003 Organizace a zpracování dat II, NDBI016 Transakce, NAIL029 Strojové učení 

2. Databázové modely a jazyky
Typy dotazovacích jazyků (procedurální, neprocedurální, jazyky pro výběr dokumentů), SQL a jeho standardy. Algoritmy implementace relačních operací. Vyhodnocování a optimalizace dotazů. Algoritmy vyhodnocení dotazu v Datalogu a Datalogu s negací. Objektové rozšíření relačního modelu dat. Databáze textů - modely (Booleovský, vektorový). Vyhledávání vzorků v textech (sousměrné, protisměrné). XML data v relacích, indexace XML dat, podobnost XML dat, XML a webové služby. Datový model RDF, dotazovací jazyk SPARQL, podobnostní dotazy v multimediálních databázích, metrické indexační metody.

Doporučené předměty: NDBI001 Dotazovací jazyky I, NPRG039 Teoretické a pokročilé aspekty XML technologií, NDBI010 Dokumentografické informační systémy, NDBI034 Vyhledávání multimediálního obsahu na webu 
Rozšiřující předměty: NDBI016 Transakce 

3. Implementace databázových systémů
Architektury databázových systémů. Modely a vlastnosti transakcí: uzamykací protokoly, časová razítka. Izolace transakcí, alokace prostředků. Distribuované transakce. Zotavení z chyb, žurnály. Indexace relačních dat: B-stromy, hašování, GRACE algoritmus. Přístupové metody k prostorovým objektům: R-stromy a jejich varianty. Vyhledávání v textech: boolské a vektorové indexy a indexace, uspořádání odpovědí, signatury a jejich implementace. Komprese dat: modely textu, kódování, Huffmanovo kódování (statické, dynamické), aritmetické kódování, LZ algoritmy, komprese bitových map, řídkých matic, Burrows-Wheelerova transformace.

Doporučené předměty: NDBI003 Organizace a zpracování dat II, NDBI034 Vyhledávání multimediálního obsahu na webu, NDBI010 Dokumentografické informační systémy, NTIN066 Datové struktury I, NDBI016 Transakce 
Rozšiřující předměty: NPRG039 Teoretické a pokročilé aspekty XML technologií, NDBI026 Databázové aplikace, NDBI013 Administrace Oracle 

Zaměření: Softwarové inženýrství

Zkušební okruhy

1. Formální základy softwarového inženýrství

2. Analýza, návrh a management softwarových systémů

3. Vývoj softwarových systémů

4. Překladače a výkonnost software

Zkušební požadavky

1. Formální základy softwarového inženýrství
Doménové, konceptuální a databázové modelování. Konceptuální schémata a jejich transformace do logických modelů, implementace. Relační model, návrh relačních schémat. Modely řízený vývoj, reverzní inženýrství. Formální metody specifikace, algebraické specifikace, formální popis datových struktur. Modelově orientované metody: Z, VDM. Datové modelování, funkční a dynamické procesní modelování, UML. Analýza algoritmů: dynamická a temporální logika. Petriho sítě. Automaty a gramatiky. RDF(S) modely splňování, OWL, deskripční logika.

Doporučené předměty: NSWI026 Pokročilé aspekty softwarového inženýrství, NSWI130 Architektury softwarových systémů, NSWI108 Sémantizace webu 
Rozšiřující předměty: NTIN043 Formální základy softwarového inženýrství, NSWI109 Konstrukce překladačů, NSWI101 Modely a verifikace chování systémů, NAIL029 Strojové učení 

2. Analýza, návrh a management softwarových systémů
Životní cyklus SW systémů. Základní metriky pro životní cyklus SW. Volba cílů, smlouva a principy vyjednávání. Zjišťování a analýza požadavků na softwarový systém. Popis, návrh a modelování architektury softwarového systému. Styly softwarových architektur. Hodnocení kvality, integrace a znuvupoužitelnost architektury. Odhady pracnosti a doby řešení. Modelem řízený vývoj. Analýza a návrh softwarových systémů. Návrh uživatelského rozhraní. Datové a procesní modelování. Notace UML. Plánování a řízení projektů, řízení kvality. Stupně zralosti softwarových procesů. Řízení rizik. Řízení vývojového týmu, jeho dynamika, uspořádání. Zavádění, údržba a rušení systémů. Prototypy, verifikace a validace softwaru, testování.

Doporučené předměty: NSWI130 Architektury softwarových systémů, NSWI026 Pokročilé aspekty softwarového inženýrství 
Rozšiřující předměty: NPRG042 Programování v paralelním prostředí, NSWI145 Webové služby, NSWI089 Ochrana informací I, NSWI071 Ochrana informací II 

3. Vývoj softwarových systémů
Architektury sw systémů, vývoj multiplatformních aplikací. Webové služby a servisně-orientovaná řešení, webově orientovaná řešení. 2-, 3- a 4-vrstvé architektury IS a související problémy. CASE nástroje, správa verzí, nástroje pro kompilaci a sestavení. Vývojová prostředí, nástroje pro ladění a testování funkčnosti a výkonnosti. Objektově orientované jazyky a technologie, návrhové vzory. Testování, testovací scénáře, metody testování černé, šedé a bílé skříňky, testování uživatelského rozhraní. Provoz a údržba, detekce a odstraňování chyb, konfigurační řízení. Vývojové prostředí, dodávky systému, akceptační a produkční prostředí, distribuce a instalace software. Správa a řízení konfigurace.

Doporučené předměty: NSWI130 Architektury softwarových systémů, NSWI126 Pokročilé nástroje pro vývoj a monitorování software, NSWI026 Pokročilé aspekty softwarového inženýrství, NTIN070 Testování software 
Rozšiřující předměty: NPRG051 Pokročilé programování v C++, NSWI145 Webové služby, NPRG024 Návrhové vzory 

4. Překladače a výkonnost software
Architektura překladače. Mezikód, základní blok, životnost proměnných. Syntaktická analýza, úpravy gramatiky. Analýza shora dolů, LL(1), rekurzivní sestup. Analýza zdola nahoru, LR(1). Sémantická analýza, syntaxí řízený překlad, atributové gramatiky. Běhová podpora, volací konvence, garbage collection. Paralelní programování, Flynnova taxonomie, SMP, NUMA, Amdahlův zákon. Atomické instrukce, paměťové modely, cache. Struktury a návrhové vzory paralelních algoritmů.

Dopoučené předměty: NSWI109 Konstrukce překladačů, NPRG042 Programování v paralelním prostředí 
Rozšiřující předměty: NSWI092 Systémové architektury mikroprocesorů, NPRG017 Programování v asembleru 

Zaměření: Systémové architektury

Zkušební okruhy

1. Operační systémy

2. Distribuované systémy

3. Architektura počítačů a sítí

4. Objektově orientované a komponentové systémy

Zkušební požadavky

1. Operační systémy
Virtualizace. Správa procesů a vláken, spouštění, plánování. Komunikace a synchronizace procesů, kritické sekce, synchronizační problémy, nástroje k jejich řešení. Správa periferií, mechanismus přerušení, přenos dat bez účasti procesoru, ovladače zařízení (struktura, funkce). Správa paměti, stránkování, strategie alokace, sdílení paměti, paměťově mapované soubory. Souborové systémy (rozhraní, typické diskové datové struktury), VFS. Bezpečnost v OS, autentizace, autorizace, modely přístupových práv. Síťové služby OS, sockety, filtrování a plánování paketů.

Doporučené předměty: NSWI004 Operační systémy, NSWI106 Administrace Unixu 
Rozšiřující předměty: NSWI035 Principy distribuovaných systémů, NSWI080 Middleware 

2. Distribuované systémy
Komunikace zasíláním zpráv (a JMS). RPC (a RMI, CORBA, SOAP). Objekty v distribuovaném prostředí (koncepty IDL, proxy, marshalling, reference, předávání argumentů, paralelismus, distribuovaný garbage collector). Skupinová komunikace, virtuální synchronie, doručovací protokoly. Kauzalita, logické hodiny. Distribuované synchronizační algoritmy (vzájemné vyloučení, volba koordinátora, distribuovaný konsensus, detekce globálního stavu). Procesy v distribuovaném prostředí, migrace, zablokování. Distribuované sdílení paměti, konzistenční modely (a konkrétní technologie DDS, JavaSpaces). Distribuované souborové systémy (NFS, AFS, CODA). Distribuovaná správa prostorů jmen, identifikace objektů a přístup k nim, služby (LDAP, JNDI, CORBA Namig, CORBA Trading). Distribuované hašovací tabulky (Chord, Pastry). Replikace a mobilita v distribuovaném prostředí (konzistence replik, přenos stavu). Architektury distribuovaných aplikací, SOA, ESB, P2P.

Doporučené předměty: NSWI021 Počítačové sítě II, NSWI035 Principy distribuovaných systémů, NSWI080 Middleware 
Rozšiřující předměty: NSWI004 Operační systémy 

3. Architektura počítačů a sítí
Architektura procesoru a zpracování programu počítačem (operace a operandy, podpora pro vyšší programovací jazyky, instrukční kód), výkonnost procesorů (základní metriky a vztahy mezi nimi). Mikroarchitektura, datová cesta (jednocyklové a více cyklové zpracování instrukcí), radič (klasické a mikroprogramové řadiče, mikroprogramování). Zřetězené zpracování instrukcí (zrychlení a hranice výkonnosti, datové a řídící hazardy), superskalární procesory (statické/dynamické plánování instrukcí, spekulativní provádění instrukcí). Architektura paměťového subsystému, vyrovnávací paměti (vnitřní architektura, strukturální parametry a jejich vliv na výkonnost). Periferní zařízení a rozhraní pro komunikaci mezi SW a HW, propojovací systémy (základní parametry, topologie) a sběrnice (řízení přístupu, řízení přenosu, transakce a jejich průběh). Topologie sítí, přístupové metody. Síťové technologie - Ethernet, Wi-Fi, ATM, xDSL, problematika broadbandu, datové přenosy v mobilních sítích. RM ISO/OSI, aktivní prvky (opakovače, přepínače, směrovače, brány). Síťový model TCP/IP, IPv6. Přenosové služby počítačových sítí: spolehlivé a nespolehlivé, spojované a nespojované. Přenos a sdílení dat, elektronická pošta, služby pro zpřístupnění informací (WWW, proxy, peer-to-peer sítě). Bezpečnost síťového přístupu, zabezpečené protokoly, překlad adres, firewally, certifikáty, VPN.

Doporučené předměty: NSWI120 Principy počítačů a operačních systémů, NSWI021 Počítačové sítě II, NSWI080 Middleware, NSWI089 Ochrana informací I, NSWI071 Ochrana informací II, NSWI073 Moderní síťová řešení, NSWI045 Rodina protokolů TCP/IP 
Rozšiřující předměty: NSWI004 Operační systémy 

4. Objektově orientované a komponentové systémy
Třídy a objekty (koncepty třída, rozhraní, objekt, vlastnosti zapouzdření, dědičnost, polymorfismus). Prototypy a klony (koncepty prototyp, klon, mixin, trait, vlastnosti). Dědičnost a subtyping (vazba mezi dědičností a subtyping, variance signatur, implementace, vícenásobná dědičnost). Vyhledávání prostředků (identita, naming, trading, příklady). Garbage collection (koncepty live object, garbage, algoritmy garbage collection). Meta-modelování a transformace modelů (text-to-model, model-to-model, model-to-text). Architektura komponentových systémů (koncepty komponenta, rozhraní, konektor, kontejner, ADL a UML). Specifikace chování systémů (přechodové systémy, CSP, testování a verifikace). Model checking (formulace úlohy, temporální logiky, Kripkeho struktura).

Doporučené předměty: NSWI080 Middleware, NSWI101 Modely a verifikace chování systémů, NSWI057 Výběrový seminář z distribuovaných a komponentových systémů I, NSWI058 Výběrový seminář z distribuovaných a komponentových systémů II, NPRG014 Koncepty moderních programovacích jazyků 
Rozšiřující předměty: NSWI132 Analýza programů a verifikace kódu 

Zaměření: Spolehlivé systémy

Zkušební okruhy

1. Modely a verifikace programů

2. Vestavěné systémy a systémy reálného času

3. Moderní softwarové systémy

Zkušební požadavky

1. Modely a verifikace programů
Matematické struktury pro modelování chování systémů (přechodové systémy, Kripkeho struktury). Specifikace vlastností systému pomocí temporálních logik (LTL, CTL, CTL*). Základní verifikační úlohy: equivalence checking a model checking. Algoritmy pro model checking a různé metody optimalizace: BDDs, partial order reduction. Specifikace chování real-time systémů, timed automata. Procesové algebry. Statická analýza programů. Model checking programů.

Doporučené předměty: NSWI101 Modely a verifikace chování systémů, NSWI132 Analýza programů a verifikace kódu 
Rozšiřující předměty: NSWE001 Vestavěné systémy a systémy reálného času 

2. Vestavěné systémy a systémy reálného času
Návrh a modelování embeded a real-time systémů. Funkce real time operačních systémů. Plánování v real-time systémech: rate monotonic, deadline monotonic, earliest deadline first. Srovnání plánování a analýza vytížení prostředků. Plánování a sdílené prostředky: blokování, priority inheritance, priority ceiling, priority inversion. Offline plánování, globální plánování. Analýza worst case execution time. Komunikace v real-time systémech, komunikační protokoly (CAN, TTP). Metriky výkonnosti počítačových systémů a jejich statistické vyhodnocování. Nástroje pro měření výkonnosti, profiling, tracing. Simulace a modelování výkonnosti, systémy hromadné obsluhy.

Doporučené předměty: NSWE001 Vestavěné systémy a systémy reálného času, NSWI131 Vyhodnocování výkonnosti počítačových systémů, NSWI126 Nástroje pro vývoj a monitorování software 
Rozšiřující předměty: NSWI101 Modely a verifikace chování systémů, NSWI132 Analýza programů a verifikace kódu 

3. Moderní softwarové systémy
Architektura paměti na paralelních systémech (SMP, NUMA), ordering, koherence. Paralelismus, hyperthreading, multicore, podpora v operačním systému, programování v paralelních prostředích, neblokující algoritmy. Objektové koncepty moderních jazyků, třídy, mixiny, klony, vazba na typový systém. Metaprogramování, reflexe, aspekty. Softwarové komponenty. Moderní konstrukce programovacích jazyků (anotace, iterátory, generics, lambda výrazy, integrované dotazy, integrované XML). Čitelnost kódu, metriky čitelnosti, refaktorizace, dokumentace. Testování a ladění kódu, preconditions, postconditions, invariants.

Doporučené předměty: NPRG043 Doporučené postupy v programování, NSWI004 Operační systémy, NPRG038 Pokročilé programování pro .NET I, NPRG021 Pokročilé programování na platformě Java, NPRG051 Pokročilé programování v C++, NPRG042 Programování v paralelním prostředí, NPRGG014 Koncepty moderních programovacích jazyků 
Rozšiřující předměty: NSWI101 Modely a verifikace chování systémů, NSWI080 Middleware, NSWI035 Principy distribuovaných systémů, NSWI126 Nástroje pro vývoj a monitorování software 

Zaměření: Počítačová grafika

Zkušební okruhy

1. Geometrické modelování a výpočetní geometrie

2. Analýza a zpracování obrazu, počítačové vidění a robotika

3. 2D počítačová grafika, komprese obrazu a videa

4. Realistická syntéza obrazu, virtuální realita

Zkušební požadavky

1. Geometrické modelování a výpočetní geometrie
Projektivní rozšíření afinního prostoru, homogenní souřadnice, afinní a projektivní transformace v rovině a v prostoru, kvaterniony v reprezentaci 3D orientace, diferenciální geometrie křivek a ploch, základní spline funkce, kubické spliny C2 a jejich vlastnosti, interpolace kubickými spliny, Bézierovy křivky, Catmull-Rom spliny, B-spline, de Casteljaův a de Boorův algoritmus, aproximační plochy, plochy zadané okrajem, Bezierovy plochy, plátování, B-spline plochy, NURBS plochy, základní věty o konvexitě, kombinatorická složitost konvexních mnohostěnů, návrh geometrických algoritmů a jejich složitost, Voronoi diagram a Delaunayova triangulace, konvexní obal, lokalizace, datové struktury a algoritmy pro efektivní prostorové vyhledávání.

Doporučené předměty: NPGR016 Aplikovaná výpočetní geometrie, NPGR020 Geometrie pro počítačovou grafiku, NPGR021 Geometrické modelování 
Rozšiřující předměty: NDMI009 Kombinatorická a výpočetní geometrie I, NDMI013 Kombinatorická a výpočetní geometrie II 

2. Analýza a zpracování obrazu, počítačové vidění a robotika
Matematický model obrazu, 2D Fourierova transformace a konvoluce, vzorkování a kvantování obrazu, změna kontrastu a jasu, odstranění šumu, detekce hran, inverzní a Wienerův filtr, určení vzájemné polohy snímků, problém korespondence bodu a objektu, odstranění geometrických zkreslení snímků, detekce hranic objektů, detekce oblastí, příznaky pro popis a rozpoznávání 2D objektů, momentové invarianty, wavelety a jejich použití, statistická teorie rozpoznávání, klasifikace s učením (Bayesův, lineární, SVM a k-NN klasifikátor), klasifikace bez učení (hierarchické a iterační shlukování), počítačové vidění, úvod do počítačové robotiky, plánování cesty mobilního robota.

Doporučené předměty: NPGR002 Digitální zpracování obrazu, NPGR001 Počítačové vidění a inteligentní robotika, NPGR013 Speciální funkce a transformace ve zpracování obrazu 
Rozšiřující předměty: NPGR029 Variační metody ve zpracování obrazu, NPGR022 Speciální seminář ze zpracování obrazu, NPGR032 Digitální zpracování obrazu v praxi, NAIL028 Úvod do mobilní robotiky 

3. 2D počítačová grafika, komprese obrazu a videa
Výstupní grafická zařízení, plošné útvary - jejich reprezentace a množinové operace s nimi, kreslicí a ořezávací algoritmy v rovině, anti-aliasing, barevné vidění a barevné systémy, reprodukce barevné grafiky, rozptylování a půltónování, kompozice poloprůhledných obrázků, geometrické deformace rastrových obrázků, morphing, základní principy komprese rastrové 2D grafiky, skalární a vektorové kvantování, prediktivní komprese, transformační kompresní metody, hierarchické a progresivní metody, waveletové transformace a jejich celočíselné implementace, kódování koeficientů, komprese videosignálu, časová predikce - kompenzace pohybu, standardy JPEG a MPEG, snímání obrazu v digitální fotografii.

Doporučené předměty: NPGR003 Počítačová grafika I, NPGR007 Pokročilá 2D počítačová grafika, NPGR025 Introduction to Colour Science 
Rozšiřující předměty: NPGR005 Speciální seminář z počítačové grafiky, NPGR024 Seminář z vědecké práce, NSWI072 Algoritmy komprese dat, NSWI100 Seminář z komprese dat, NPGR030 Optika pro počítačovou grafiku 

4. Realistická syntéza obrazu, virtuální realita
Metody reprezentace 3D scén, klasické zobrazovací algoritmy, výpočet viditelnosti, výpočet vržených stínů, modely osvětlení a stínovací algoritmy, rekurzivní sledování paprsku, textury, anti-aliasing, urychlovací metody pro ray-tracing, princip radiačních metod, výpočet konfiguračních faktorů, řešení radiační soustavy rovnic, fyzikální model šíření světla - zobrazovací rovnice, Monte-Carlo přístupy ve výpočtu osvětlení, hybridní zobrazovací metody, přímé metody ve vizualizaci objemových dat, generování izoploch, schéma grafického akcelerátoru, předávání dat do GPU, textury v GPU, programování GPU, základy OpenGL, jazyka Cg a GLSL, CUDA, pokročilé techniky práce s GPU, SW a HW prostředky pro virtuální realitu, jazyk VRML, struktura scény, statické, dynamické a interaktivní scény VRML, práce se skripty, rozhraní EAI, víceuživatelská virtuální realita.

Doporučené předměty: NPGR004 Počítačová grafika II, NPGR010 Počítačová grafika III, NPGR019 Hardware pro počítačovou grafiku, NPGR012 Virtuální realita, NPGR023 Visualizace, NPGR026 Predictive Image Synthesis Technologies, NPGR028 Real-Time Raytracing, NPGR031 Vybrané partie z výpočtu globálního osvětlení 
Rozšiřující předměty: NPGR027 Shading Languages, NPGR005 Speciální seminář z počítačové grafiky, NPGR024 Seminář z vědecké práce, NPGR030 Optika pro počítačovou grafiku