I2 - Softwarové systémy

Garantující pracoviště: Katedra softwarového inženýrství
Odpovědný učitel: Prof. Ing. František Plášil, DrSc.

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 NTIN090 bude vyučován až od akademického roku 2009/2010.

² Předmět je povinný pouze pro studijní plány Systémové architektury a Spolehlivé systémy, pro ostatní studijní plány je povinně volitelný.

³ Předmět je povinný pouze pro studijní plán Softwarové inženýrství, pro ostatní studijní plány 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 studijní plány Databázové systémy, Softwarové inženýrství a Počítačová grafika, pro ostatní studijní plány je povinný.

² Předmět je povinně volitelný pouze pro studijní plány Databázové systémy, Systémové architektury, Spolehlivé systémy a Počítačová grafika, pro ostatní studijní plány je povinný.

Studijní plán: Databázové systémy

Garantující pracoviště: Katedra softwarového inženýrství
Odpovědný učitel: Prof. RNDr. Jaroslav Pokorný, CSc.

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. Bezpečné výrazy, ekvivalence dotazovacích jazyků. Relační úplnost. Věta o tranzitivním uzávěru relace. Datalog, sémantika Datalogu pomocí nejmenšího pevného bodu. Datalog s negací, stratifikace, předpoklad uzavřeného světa. Sémantika SQL. Logické problémy konstrukce informačního systému.

2. Databázové modely a jazyky
Typy dotazovacích jazyků (procedurální, neprocedurální, jazyky pro výběr dokumentů), SQL. Vyhodnocování a optimalizace dotazů. Algoritmy vyhodnocení dotazů v Datalogu a Datalogu s negací. Implementace relačních operací. Indexace dokumentů. Modely a vlastnosti transakcí. Izolace transakcí, alokace prostředků (zámky, granularita zamykání, dvoufázové uzamykání, deadlock). Zotavení, žurnály. Databáze textů: modely (boolský, vektorový), vyhledávání v textech. Rodina jazyků a nástrojů XML (XML schema, XPath, XQuery, XSLT).

3. Implementace databázových systémů
Metody indexace relací, hashování, B-stromy, datové struktury na externí paměti. Vícerozměrné dotazy implementované pomocí hashovacích metod, vícerozměrné mřížky, vícerozměrných stromů. Přístupové metody k prostorovým objektům: R-stromy a jejich varianty. Databáze textů: modely (boolský, vektorový), vyhledávání v textech, signatury, metody implementace signatur (vrstvené kódování), uspořádání odpovědi. Komprese dat: predikce a modelování, reprezentace celých čísel, obecné metody komprese, komprese bitových map, řídkých matic, trie, textů. Huffmanovo kódování (statické, dynamické), aritmetické kódování, LZ algoritmy. Uzamykací protokoly, časová razítka. Distribuované transakce.

Doporučené předměty

Studijní plán: Systémové architektury

Garantující pracoviště: Katedra softwarového inženýrství
Odpovědný učitel: Prof. Ing. František Plášil, DrSc.

Zkušební okruhy

1. Operační systémy

2. Distribuované systémy

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

Zkušební požadavky

1. Operační systémy
Struktura operačního systému, architektura mikrojádra, abstrakce poskytované mikrojádry. Virtuální stroje. Správa procesů a vláken, plánování. Komunikace a synchronizace procesů, kritické sekce, synchronizační problémy a primitiva, uváznutí a jeho řešení. Podpora multiprocesorových systémů. Mechanismus přerušení v OS, DMA. Správa periferií, ovladače zařízení. Správa paměti, hierarchie pamětí, segmentace, stránkování, strategie alokace, odkládání. Sdílení paměti mezi adresovými prostory, paměťově mapované soubory. Souborové systémy, souborové a adresářové služby, síťové souborové systémy. Informační bezpečnost a základy šifrování. Síťové služby OS.

2. Distribuované systémy
Komunikace, zasílání zpráv, RPC. Skupinová komunikace, virtuální synchronie, doručovací protokoly. Middleware (klasifikace, protokoly, RMI, EJB, CORBA, DCOM, SOAP, ...). Logické hodiny a jejich synchronizace. Distribuované synchronizační algoritmy. Distribuovaný konsensus. Distribuované sdílení paměti, konzistenční modely. Souborové a adresářové služby, distribuované souborové systémy (NFS, AFS, CODA, ...), replikace. Distribuovaná správa prostorů jmen, identifikace objektů a přístup k nim, služby (LDAP, JNDI, CORBA Namig/Trading). Procesy v distribuovaném prostředí, migrace procesů, vyvažování zátěže, zablokování.

3. Architektura počítačů a sítí
Von Neumannova architektura a její alternativy, multiprocesory. Mikroprogramové a klasické řadiče, mikroprogramování. Paměťová hierarchie, vyrovnávací paměti, stránkování a segmentace. Vstupně-výstupní subsystémy, přerušení, DMA, způsoby obsluhy periferií. Vstupně-výstupní topologie, sběrnice a jejich řízení (např. SCSI, USB, AGP, ...). Mezipočítačová komunikace, sériové a paralelní kanály, modemy. Topologie sítí, přístupové metody. Síťové technologie - ATM, FDDI, FastEthernet, bezdrátové technologie. RM ISO/OSI, aktivní prvky (bridge, routery). 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

Studijní plán: Softwarové inženýrství

Garantující pracoviště: Katedra softwarového inženýrství
Odpovědný učitel: Prof. Ing. František Plášil, DrSc.

Zkušební okruhy

1. Programovací jazyky a překladače

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

3. Analýza a návrh softwarových systémů

Zkušební požadavky

1. Programovací jazyky a překladače
Struktura kompilátoru a navazujících nástrojů (linkery, loadery, debuggery, knihovny, preprocesory). Konečné automaty a lexikální analýza. Syntaktická analýza - LL, LR techniky. Syntaxí řízený překlad a atributové gramatiky. Reprezentace programu mezikódem. Překlad výrazů a programových struktur. Rozsahy platnosti proměnných, aktivační záznamy, implementace vnořených procedur, volací konvence. Vliv architektury počítače na generování kódu a optimalizaci. Metody generování kódu, přidělování registrů, optimalizace. Podpora kompilátorů pro synchronizační primitiva, vlákna. Objektově orientované jazyky a principy jejich implementace. Překladače vs. interpretry, skriptovací jazyky.

2. Objektově orientované a komponentové systémy
Třídy a objekty (koncepty class, interface, object, vlastnosti encapsulation, inheritance, polymorphism, příklady). Prototypy a klony (koncepty prototype, clone, mixin, trait atd., základní vlastnosti, příklady). Dědičnost a subtyping (vazba mezi dědičností a subtyping, subsumption, variance signatur, příklady, implementace, diamond inheritance). Objekty v distribuovaném prostředí (koncepty IDL, proxy, marshalling, reference, předávání argumentů, paralelismus, příklady). Replikace a mobilita v distribuovaném prostředí (konzistence replik, přenos stavu). Vyhledávání prostředků (identita, naming, trading, příklady). Garbage collection (koncepty live object, garbage, algoritmy garbage collection). Architektura komponentových systémů (koncepty komponenta, rozhraní, konektor, kontejner, ADL a UML, příklady). Specifikace chování systémů (přechodové systémy, CSP, protokoly, testování a verifikace). Model checking (formulace úlohy, temporální logiky, Kripkeho struktura).

3. Analýza a návrh softwarových systémů
Algebraické specifikace, formální popis datových struktur. Modelově orientované metody: Z, VDM. Analýza algoritmů: Hoareova metoda, dynamická logika, temporální logika. Petriho sítě. Vyjadřovací prostředky a metody (datové modelování, procesní modelování - funkční a dynamické) strukturované analýzy a návrhu informačních systémů. Konceptuální modelování, databázové modelování, implementace. E-R schémata a jejich transformace do relačního modelu. Návrh relačních schémat v 3NF. Modely životního cyklu softwarových systémů. Plánování a řízení projektů, alokace zdrojů, použití metrik, řízení kvality, stupně zralosti softwarových týmů (CMM). CASE systémy. třívrstvá struktura informačních systémů, klient/server. XML a značkovací jazyky. Objektová analýza a návrh (UML). Informační bezpečnost.

Doporučené předměty

Studijní plán: Spolehlivé systémy

Garantující pracoviště: Katedra softwarového inženýrství
Odpovědný učitel: Prof. Ing. František Plášil, DrSc.

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*, CTL s fairness constraints). Základní verifikační úlohy: equivalence checking a model checking. Algoritmy pro model checking a různé metody optimalizace: BDDs, partial order reduction. Paralelní a distribuovaný model checking. Specifikace chování real-time systémů, timed automata. Proces-algebry. Behavior protocols. Statická analýza programů. Model checking programů.

2. Vestavěné systémy a systémy reálného času
Návrh 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. 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, QPN.

3. Moderní softwarové systémy
Moderní architektury: virtualizace paměti na paralelních architekturách (SMP, NUMA), 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. Softwarové služby. Moderní konstrukce programovacích jazyků (například anotace, iterátory, generics, lambda výrazy, integrované dotazy, integrované XML). Middleware architektury pro komunikaci: RPC, proxies, messaging, DSM. Čitelnost kódu, metriky čitelnosti, refaktorizace, dokumentace. Testování a ladění kódu (technické principy nástrojů), preconditions, postconditions, invariants.

Doporučené předměty

Studijní plán: Počítačová grafika

Garantující pracoviště: Kabinet software a výuky informatiky
Odpovědný učitel: RNDr. Josef Pelikán

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, Voroného diagram a Delaunayova triangulace, konvexní obal, lokalizace, datové struktury a algoritmy pro efektivní prostorové vyhledávání.

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 (Bayessův, lineární 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.

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.

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, hierarchické přístupy v radiačních metodách, 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 jazyka Cg, pokročilé techniky práce s GPU, SW a HW prostředky pro virtuální realitu, vlastnosti jazyka VRML, struktura scény, typy uzlů (datové typy, trikové uzly), tvorba statické scény VRML, dynamické a interaktivní scény VRML, práce se skripty, rozhraní EAI, víceuživatelská virtuální realita.

Doporučené předměty