Neprihlásený používateľ
Cesta: Menu > Štúdium > Bakalárske > Štátne skúšky

Obsah a organizácia záverečného konania pre I. stupeň štúdia študijného programu v odbore 9.2.1. Informatika na FMFI UK

Doc. RNDr. Daniel Olejár, PhD., garant študijného programu

Úvod

Bakalárske štúdium informatiky je podľa študijného programu ukončené štátnymi skúškami. Tento dokument je určený študentom bakalárskeho štúdia informatiky, ktorí budú končiť štúdium v školskom roku 2016/17 a obsahuje informácie o obsahu a organizácii štátnych skúšok. Dokument vychádza zo študijných poriadkov UK, FMFI UK a akreditovaného študijného programu I. stupňa v odbore 9.2.1. Informatika na FMFI UK.

Úlohou štátnej skúšky bakalárskeho štúdia je overiť, či študent získal vedomosti a zručnosti dané profilom absolventa bakalárskeho štúdia informatiky, či je schopný syntetizovať poznatky získané štúdiom čiastkových predmetov a tvorivo ich uplatniť.

Štátne skúšky bakalárskeho štúdia informatiky pozostávajú z dvoch častí:
  • štátna skúška z dvoch predmetov matematika a informatika sa štandardne koná začiatkom 5. semestra štúdia,
  • obhajoba bakalárskej práce sa koná na záver bakalárskeho štúdia.

Obsah štátnej skúšky

Štátna skúška bakalárskeho štúdia pokrýva potreby dvoch rozličných skupín študentov bakalárskeho štúdia informatiky. Pre tých študentov, ktorí budú pokračovať v magisterskom štúdiu informatiky, musí overiť ich vedomosti a schopnosť syntetizovať základné poznatky odboru pred ďalšou hlbšou špecializáciou. Pre tých absolventov bakalárskeho štúdia, ktorí nebudú pokračovať v magisterskom štúdiu, má záverečná skúška overiť ich odbornú spôsobilosť (danú profilom absolventa bakalárskeho štúdia informatiky) pred nástupom do reálnej praxe.
Štátnicový predmet matematika pokrýva základné matematické predmety, ktoré tvoria základ teoretickej informatiky aj samotnej informatiky. Pozostáva z nasledujúcich okruhov (zodpovedajúcich predmetom povinného základu):
Štátnicový predmet informatika obsahuje teoretickú informatiku a aplikovanú informatiku, pokrytú nasledujúcimi predmetmi bakalárskeho štúdia informatiky:
Obsah predmetov štátnej skúšky

Matematická analýza

  1. Limita reálnej funkcie jednej reálnej premennej (definícia vlastnej a nevlastnej limity, vety o výpočte limít, číslo e, Cauchyho-Bolzanovo kritérium konvergencie postupnosti).
  2. Spojité funkcie a ich základné vlastnosti (definícia spojitej funkcie, Darbouxova vlastnosť, vlastnosti spojitých funkcií na uzavretých ohraničených intervaloch).
  3. Derivácia funkcie a jej využitie na vyšetrovanie priebehu funkcie (definícia derivácie, vety o výpočte derivácií, vety o strednej hodnote, derivácie vyšších rádov, vyšetrovanie monotónnosti, extrémov a konvexnosti pomocou derivácií).
  4. Primitívna funkcia a neurčitý integrál (definícia neurčitého integrálu, metóda per partes a substitúcie, univerzálna trigonometrická substitúcia).
  5. Riemannov určitý integrál (definícia riemannovsky integrovateľnej funkcie, integrovateľnosť monotónnych a spojitých funkcií, Newtonov-Leibnizov vzorec, integrál ako funkcia hranice).
  6. Číselné rady (definícia číselného radu, Cauchyho-Bolzanovo kritérium konvergencie radu, kritériá pre konvergenciu radov s nezápornými členmi, Leibnizovo kritérium, relatívne a absolútne konvergentné rady, prerovnanie radov).
  7. Mocninové a Taylorove rady (definícia mocninového radu, polomer a interval konvergencie, derivovanie a integrovanie mocninových radov, definícia Taylorovho radu, pojem analytickej funkcie).

Algebra

  1. Vektorové priestory, lineárne zobrazenia [priestor, podpriestor, lineárna závislosť, báza a dimenzia. Steinitzova veta, súčty podpriestorov, lineárne zobrazenia, kompozícia lineárnych zobrazení, inverzné lineárne zobrazenia, matica lineárneho zobrazenia, jadro a obraz lineárneho zobrazenia]
  2. Matice a riešenia lineárnych rovníc nad poľom F [matice, operácie s maticami (násobenie, sčítanie), elementárne riadkové operácie, trojuholníkový a redukovaný trojuholníkový tvar matice, systémy lineárnych rovníc nad poľom F, množina riešení homogénnych a nehomogénnych systémov lineárnych rovníc, existencia a tvary riešení]
  3. Determinanty [Determinant matice. Vlastnosti determinantov. Výpočty determinantov a ich použitie pri riešení lineárnych rovníc a hľadaní inverznej matice]
  4. Grupy [grupy, podgrupy, izomorfizmus a homomorfizmus grúp, cyklické grupy (s klasifikáciou) a ich podgrupy, rozklad grupy podľa podgrupy, Lagrangeova veta, homomorfizmus a izomorfizmus grúp, normálna podgrupa, faktorizácia grupy podľa podgrupy]
  5. Okruhy [základné vlastnosti operácií v okruhoch, podokruh, ideál (hlavný, maximálny, prvoideál), faktorizácia okruhu podľa ideálu, vzťah medzi výsledkom faktorizácie a vlastnosťami ideálu, podľa ktorého sa faktorizuje]
  6. Okruhy hlavných ideálov [existencia jednotky v okruhu, najväčší spoločný deliteľ, vlastnosti deliteľnosti, ireducibilné prvky, veta o jednoznačnom rozklade]
  7. Okruhy polynómov [pojem algebraického a transcendentného prvku pre daný okruh, okruh polynómov R[x], okruh polynómov F[x] nad poľom F ako okruh hlavných ideálov, veta o jednoznačnom rozklade polynómov nad daným poľom, substitučný homomorfizmus (veta o substitúcii), korene, viacnásobné korene, Hornerova schéma]
  8. Rozšírenia polí [konečné rozšírenie poľa, stupeň rozšírenia, algebraické rozšírenie, minimálny polynóm daného algebraického prvku]
  9. Konečné polia [charakteristika poľa, možné počty prvkov konečných polí, počítanie v poli F[x]/(p(x)) pre ireducibilný polynóm p(x), rozkladové pole polynómu, existencia poľa s p^n prvkami]

Úvod do diskrétnych štruktúr

  1. Základy matematickej logiky [logické operácie, formuly, výrokové funkcie, kvantifikácia výrokov, tautógia, kontradikcia]
  2. Matematický dôkaz [logický dôsledok, základné typy matematickych dôkazov]
  3. Intuitívny pojem množiny [základné pojmy a označenia, množinové operácie. Množinové identity]
  4. Karteziánsky súčin množín [definícia usporiadanej dvojice, karteziánsky súčin dvoch a viacerých množín, množinové identity s karteziánskym súčinom, použitie karteziánskeho súčinu]
  5. Relácie [skladanie relácií, inverzná relácia, relácie na množinách. Relácia ekvivalencie, rozklad množiny. Tranzitívny uzáver relácie, reflexívno-tranzitívny uzáver – definície, vlastnosti.]
  6. Usporiadania [definícia čiastočného a úplného usporiadania množiny, ostré a neostré usporiadanie, minimálny, maximálny, prvý a posledný prvok množiny, lexikografické usporiadanie karteziánskeho súčinu]
  7. Zobrazenia [definícia pomocou relácií, injektívne, surjektívne a bijektívne zobrazenia a ich skladanie]
  8. Mohutnosť množiny [Základné vlastnosti mohutnosti a nerovnosti. Počítanie s mohutnosťami, súčet, súčin a mocnina.]
  9. Cantor-Bernsteinova veta a jej dôsledky [formulácia vety, idea dôkazu, usporiadanie kardinálnych čísel]
  10. Konečné a nekonečné množiny [definícia konečnej množiny, definícia nekonečnej množiny, existencia nekonečných množín, vlastnosti konečných a nekonečných množín]
  11. Spočítateľné a nespočítateľné množiny [zjednotenie a karteziánsky súčin spočítateľných množín, existencia nespočítateľných množín, Cantorova diagonálna metóda]
  12. Potenčná množina a jej kardinalita [formulácia Cantorovej vety o potenčnej množine, idea dôkazu, dôsledky pre nekonečné množiny]

Úvod do matematickej logiky

  1. Výstavba logickej teórie [Jazyk logiky, formálne systémy logiky]
  2. Výroková logika [Syntax a sémantika výrokovej logiky. Formálny systém výrokovej logiky]
  3. Základné vety výrokovej logiky [Veta o kompaktnosti a jej dôsledok, veta o dedukcii. Základné teorémy výrokovej logiky]
  4. Postova veta [slabá forma, silná forma]
  5. Bezospornosť formálneho systému [Definícia sporného a bezosporného formálneho systému a množiny formúl. Vzťah bezospornosti a splniteľnosti množiny formúl výrokovej logiky.]
  6. Pravidlá odvodenia vo výrokovej logike [Veta o nahradení podformúl ekvivalentnými formulami. De Morganove pravidlá. Veta o dôkaze rozborom prípadov. Veta o substitúcii prvotných formúl.]
  7. Disjunktívna a konjunktívna normálna forma formuly [Definícia DNF a KNF. Vety o vyjadrení každej formuly výrokovej logiky v DNF a KNF.]
  8. Predikátová logika. [Jazyk predikátovej logiky. Sémantika a syntax predikátovej logiky. Substitúcia termov za premenné. Voľné a viazané premenné.]
  9. Axiómy a pravidlá odvodenia predikátovej logiky. [Pravidlá zavedenia kvantifikátorov. Veta o uzávere. Lema o distribúcii kvantifikatorov. Veta o ekvivalencii. Veta o variantoch. Veta o dedukcii. Dôsledky vety o dedukcii. Veta o konštantach. Zovšeobecnená veta o dedukcii a jej dôsledok.]
  10. Prenexný a Skolemov tvar formuly [Definície príslušných tvarov formúl. Vety o vyjadriteľnosti formúl predikátovej logiky v prenexnom a Skolemovom tvare.]
  11. Rovnosť [Axiómy rovnosti. Základné vlastnosti rovnosti. Príklady teórií s rovnosťou.]

Úvod do kombinatoriky a teórie grafov

  1. Prirodzené čísla a matematická indukcia, Dirichletov princíp [definícia prirodzených čísiel, vlastnosť dobrého usporiadania, dôkaz matematickou indukciou]
  2. Základné pravidlá kombinatorického počítania [pravidlo súčtu, súčinu, mocnenia, počítanie prvkov množiny dvoma spôsobmi]
  3. Variácie a enumerácia zobrazení [variácie s opakovaním a bez opakovania, permutácie, určenie ich počtu]
  4. Kombinácie a enumerácia podmnožín [kombinácie bez opakovania a s opakovaním a určenie ich počtu, príklady kombinácií s opakovaniami]
  5. Binomická a polynomická veta [znenie a dôkaz, dôsledky]
  6. Rovnosti a nerovnosti s kombinačnými číslami [identity zahŕňajúce kombinačné čísla, metódy dokazovania identít]
  7. Princíp zapojenia a vypojenia [formulácia, dôkaz a aplikácie: enumerácia surjektívnych zobrazení, počet permutácií bez pevných bodov]
  8. Hierarchia rastu funkcií, odhady čísla n! O-symbolika, rádová rovnosť, asymptotická rovnosť, odhady
  9. Stromy a lesy, kostry, súvislé grafy, meranie vzdialeností v grafe [definície, vlastnosti, rozličné charakterizácie stromov]
  10. Eulerovské a bipartitné grafy [charakterizácie eulerovských a bipartitných grafov, algoritmus na nájdenie eulerovského ťahu]
  11. Meranie vrcholovej a hranovej súvislosti grafu [definície, vzájomný vzťah, artikulácie, mosty, charakterizácia 2-súvislých grafov]
  12. Hamiltonovské grafy [definícia, postačujúce podmienky, zložitosť problému]

Princípy počítačov

  1. Kódovanie informácie v počítači (číselná, textová, obrazová, riadiaca a i.)
  2. Formáty a aritmetika celých čísel (celé čísla bez znamienka a so znamienkom, jednotkový a binárny doplnkový kód, excess kód, Golayov zrkadlový kód, osmičkový, šestnástkový kód, BCD kód; sčítanie, odčítanie násobenie a delenie, identifikácia a ošetrenie chýb (pretečenie, delenie nulou))
  3. Formáty a aritmetika reálnych čísel (pevná rádová čiarka, pohyblivá rádová čiarka, normalizovaný tvar, technika skrytého bitu, základné aritmetické operácie s reálnymi číslami vo formáte pohyblivá rádová čiarka)
  4. Booleovské funkcie a operátory (definícia, základné vlastnosti BF, skladanie BF, formuly, uzáver množiny BF, uzavreté množiny BF, úplnosť množiny BF, realizácie BF formulami)
  5. Realizácia Booleovských funkcií a operátorov disjunktívnymi normálnymi formami (DNF)
  6. Minimalizácia DNF (úplnosť systému AND, OR, NOT, úplná DNF, princíp minimalizácie. Karnaughove mapy, Quine-McCluskey-ova metóda minimalizácie DNF. Neúplne určené BF a ich realizácia pomocou DNF.)
  7. Fyzikálne aspekty logických obvodov (signál, modulácia signálu (amplitúdová, frekvenčná, fázová), odchýlky od ideálnych hodnôt, vstupné, výstupné vetvenie obvodu, preklápanie obvodu a i.)
  8. Kombinačné obvody (základné kombinačné obvody, návrh kombinačných obvodov, časová a priestorová zložitosť kombinačných obvodov; sčítačka, sčítačka so zrýchleným prenosom, ALU)
  9. Sekvenčné obvody (základné pamäťové členy, statická a dynamická analýza SR člena, konečný automat, návrh sekvenčného obvodu, registre, čítač, pamäť)
  10. Digitálne systémy (jazyk RTL, riadiace jednotky, návrh digitálneho systému, násobenie a delenie)
  11. Architektúra a princíp činnosti počítača (s von Neumannovského a Harvardskou architektúrov).
  12. Inštrukcie počítača (inštrukčný súbor, formát inštrukcií, spracovanie inštrukcie, CPU cykly, RTL, spôsoby adresovania).
  13. CPU (Central Processing Unit) – hlavné časti CPU a ich základné funkcie, makroinštrukcie a mikroinštrukcie, konfigurácie CPU, spracovanie prerušení).
  14. ALU (Arithmetic and Logic Unit) – aritmetické operácie, logické funkcie, podmienkové bity.
  15. Mikroprogramovanie – napevno zdrôtovaná vs. mikroprogramovo riadená CLU, horizontálne vs. vertikálne mikroinštrukcie.
  16. RISCCISC – východiská a motivácia, princípy návrhu RISC, porovnanie RISC vs. CISC, špecifiká registrov pri RISC architektúre (rozdelenie do okien).
  17. Spracovanie vstupu a výstupu – vstupno-výstupné zariadenia, formáty a spôsoby prenosu údajov, memory mapped I/O vs. I/O mapped I/O, riadenie vstupu a výstupu (programom riadený I/O, I/O využívajúci prerušenia, DMA prenos, I/O kanál).
  18. Konfigurácie multiprocesorových systémov – so spoločnou zbernicou, s duálnou zbernicou, NUMA, switching (crossbar) matrix interconnection scheme.
  19. Pamäť– hierarchia pamätí, delenie pamätí (RAM, ROM, ...), asociatívna pamäť, cache, zásobníková pamäť.
  20. Pipelining – aritmetický a inštrukčný, jednofunkčný a polyfunkčný, statický a dynamický, sušenie rúry.

Programovanie

  1. Objektovo orientované programovanie (zapúzdrenie, dedičnosť, polymorfizmus, trieda, modifikátory prístupu, konštruktory, abstraktné triedy a rozhrania), vnorené triedy (nested classes), garbage collection.
  2. Výnimky (exceptions) - vyhodenie výnimky, zachytenie a spracovanie výnimiek (try, catch, finally), vlastné triedy výnimiek, checked a unchecked výnimky.
  3. Vlákna (threads) – stav vlákna (new, runnable, blocked, waiting, timed_waiting, terminated), životný cyklus vlákna (vytvorenie, spustenie, zastavenie, ...), plánovanie vlákien (fixed-priority scheduling, yield, time-slicing). Synchronizácia vlákien (kritické úseky, wait a notify, explicitné zámky a podmienkové premenné).
  4. Generics (formálne typové parametre, parametrizovaný typ, wildcards, ohraničené wildcards, generic methods).
  5. Návrhové vzory: Composite, Strategy
  6. Návrhové vzory: Decorator, Abstract Factory
  7. Návrhové vzory: Bridge, Memento
  8. Návrhové vzory: Iterator, Visitor

Systémové programovanie

  1. Jazyk assemblera – prvky jazyka, typy inštrukcií, operandy, adresné módy.
  2. Práca so zásobníkom – volacie konvencie C a Pascal a ich vlastnosti.
  3. Assembler a makroprocesor – úloha, spôsob práce, jednoprechodové a dvojprechodové.
  4. Linker a loader – úloha, spôsob práce, knižnice, dynamické linkovanie.
  5. Systémové volania – procesy a spracovanie signálov – vytváranie a ukončovanie procesu, spúšťanie programu, signály.
  6. Systémové volania – vstupno-výstupné operácie so súbormi a terminálmi.
  7. Systémové volania – sieťová komunikácia.

Operačné systémy

  1. Koncepcia OS (procesy, súbory, funkcie a služby OS, systémové volania, interpreter príkazov) a štruktúra OS (monolitický kernel, mikrokernel, …).
  2. Procesy (hierarchia procesov, vytváranie, swapovanie procesov, životný cyklus procesu) a komunikácia medzi procesmi (synchronizácia, adresovanie).
  3. Synchronizácia procesov (časová závislosť procesov /race conditions/, vzájomné vylúčenie /mutual exclusion/ a spôsoby jeho dosiahnutia – hardvérové aj softvérové) a klasické problémy synchronizácie procesov (producent/konzument, problém obedujúcich filozofov, problém čitateľov a zapisovateľov).
  4. Uviaznutie – podmienky pre vznik uviaznutia, metódy riešenia uviaznutia (ignorovanie, detekcia a vyvedenie, prevencia, vyhýbanie sa). Rozdiel medzi uviaznutím a vyhladovaním.
  5. Správa procesov a procesora – plánovače a ich funkcie. Algoritmy plánovania procesov (FCFS, SJF, HRN, SRT, RR, ...).
  6. Správa pamäte – jej funkcie, typy správy pamäte (jeden súvislý úsek, statické súvislé úseky, dynamické súvislé úseky, stránkovanie, segmentovanie).
  7. Správa pamäte – virtuálna pamäť, výpadok stránky, nahradzovacie algoritmy (FIFO, NRU, LRU, NFU), stránkovanie na žiadosť, model s pracovnou množinou, implementačné problémy (zálohovanie inštrukcií, zamykanie stránok v pamäti, zdieľanie stránok).
  8. Správa súborov – funkcie, typy súborov, štruktúra súboru, hierarchické systémy adresárov, správa voľného priestoru na disku (spájaný zoznam voľných blokov, indexové bloky, bitová mapa), správa priestoru prideleného súboru (FAT, i-node), zdieľané súbory.
  9. Správa zariadení – funkcie, klasifikácia V/V zariadení, pojem riadiaca jednotka, DMA, techniky prideľovania V/V, V/V softvér, správa diskových požiadaviek (SSTF, SCAN, C-SCAN, N-step SCAN).

Počítačové siete

  1. Vrstvové modely, služby - vrstva, rozhranie, protokol, služba, typy služieb, referenčný model ISO OSI a model TCP/IP.
  2. Fyzická vrstva – metalické a optické káble, elektromagnetické spektrum a bezdrôtové prenosy.
  3. Linková vrstva – Ethernet a WiFi – adresácia, spôsob prenosu, obmedzenia, rozširovanie, BSS, ESS, access point, distribučný systém, portál.
  4. Sieťová vrstva TCP/IP (IPv4) – adresácia, služby, protokol IP, smerovanie, ARP, NAT, ICMP.
  5. Transportná vrstva TCP/IP – služby, protokoly UDP a TCP.
  6. Aplikačná vrstva – DNS, DHCP.
  7. Aplikačná vrstva – web – organizácia webu, protokoly, proxy servery, bezpečnosť.
  8. Aplikačná vrstva – elektronická pošta – organizácia elektronickej pošty, protokoly, MIME, bezpečnosť.
  9. Sieťová vrstva TCP/IP – IPv6 – adresácia, služby, protokol IPv6, smerovanie, ICMPv6, Neighbour Discovery Protocol, konfigurácia, 6to4, prepojenie s IPv4.
  10. Bezpečnosť sietí – bezpečnostné problémy a mechanizmy na rôznych vrstvách – VLAN, VPN, SSL/TLS, firewall, bezpečnosť na aplikačnej vrstve.

Úvod do databáz

  1. Účel databázových systémov. Charakteristika databázových aplikácií. Trojstupňová architektúra ANSI SPARC. Dátové modely.
  2. Relačný kalkul. Syntax predikátových formúl. Formulácia dotazov v relačnom kalkule. Negácia, doménovo nezávislé a bezpečné formuly. Súvis s inými dotazovacími jazykmi.
  3. Datalog. Syntax a sémantika Datalogových programov. Negácia. Bezpečnosť Datalogových programov. Výpočet dotazu na Datalogový program. Súvis s inými dotazovacími jazykmi.
  4. Relačná algebra. Operátory relačnej algebry. Grupovanie a agregácia. Rekurzia, výpočet pevného bodu. Súvis relačnej algebry s inými dotazovacími jazykmi.
  5. Jazyk SQL. Programovanie v SQL (Data Definition Language, Data Manipulation Language). Negácia. Grupovanie a agregácia. Rekurzia. Súvis SQL s inými dotazovacími jazykmi.
  6. Teória navrhovania relačných databáz. Funkčné závislosti. Armstrongove axiómy. Uzáver množiny atribútov, uzáver množiny funkčných závislostí. Pokrytie a minimálne pokrytie množiny funkčných závislostí. Nadkľúče a kľúče relácie.
  7. Normálne formy. Účel normalizácie databáz. Tretia normálna forma, Boyce-Coddova normálna forma. Algoritmy pre dekompozíciu do normálnych foriem. Bezstratovosť dekompozície, zachovanie funkčných závislostí.
  8. Transakcie. Požiadavky na transakčný systém (ACID). Architektúra transakčného systému. Rozvrhy. Triedy sériovateľnosti a obnoviteľnosti.
  9. Implementácia sériovateľnosti a obnoviteľnosti v transakčných systémoch. Testy sériovateľnosti. Algoritmy izolácie. Zámky, časové pečiatky, validácia. Uviaznutie (deadlock) a metódy riešenia uviaznutia. Algoritmy obnovy. Log-file, checkpointing.
  10. Fyzická organizácia. Dvojúrovňový model pamäti a organizácie dát. Indexové stromy, hashovanie. Operátory fyzickej algebry. Implementácia vybraných fyzických operátorov (merge-sort, nested-loop join).

Formálne jazyky a automaty

  1. Regulárne jazyky. [Deterministické a nedeterministické konečné automaty, regulárne gramatiky, regulárne výrazy, ekvivalencia popisov regulárnych jazykov, pumpovacia lema, uzáverové vlastnosti.]
  2. Bezkontextové jazyky. [Bezkontextové gramatiky, normálne tvary, nedeterministické zásobníkové automaty, ekvivalencia zásobníkových automatov a bezkontextových gramatík, pumpovacia lema, uzáverové vlastnosti.]
  3. Rekurzívne vyčísliteľné a rekurzívne jazyky. [Turingove stroje, frázové gramatiky, ich ekvivalencia, uzáverové vlastnosti, univerzálny Turingov stroj, Turingova hypotéza.]
  4. Nerozhodnuteľné problémy. [Diagonalizácia, problém zastavenia, metódy dokazovania nerozhodnuteľnosti.]
  5. Miery zložitosti pre Turingove stroje [triedy zložitosti, kompresia pásky, zrýchľovanie výpočtov, vplyv redukcie počtu pások na zložitosť]
  6. Triedy P a NP [polynomiálna redukovateľnosť. Cook-Levinova veta a ďalšie NP-úplné problémy]

Efektívne algoritmy a dátové štruktúry

  1. Analýza časovej zložitosti algoritmov. (Definícia časovej zložitosti. O-notácia. Odhad časovej zložitosti rekurzívnych algoritmov používajúcich metódu rozdeľ a panuj.)
  2. Algoritmy pre triedenie. (Efektívne algoritmy triedenia porovnávaním. Triedenie v lineárnom čase. Dolný odhad časovej zložitosti každého triedenia porovnávaním.)
  3. Dátové štruktúry v poli. (Pole s dynamickou veľkosťou – vektor. Zásobník, fronta. Binárna halda a implementácia prioritnej fronty pomocou nej.)
  4. Usporiadané dátové štruktúry. (Binárne vyhľadávacie stromy. Usporiadaná množina, usporiadané asociatívne pole – slovník. Vyvažovanie binárnych stromov.)
  5. Hešovanie. (Kolízie a rôzne spôsoby ich riešenia. Narodeninový paradox. Množina, asociatívne pole.)
  6. Základné grafové algoritmy. (Reprezentácie grafu v pamäti. Prehľadávanie do hĺbky a do šírky. Topologické triedenie.)
  7. Najkratšie cesty v grafe. (Dijkstrov algoritmus, Floydov-Warshallov algoritmus.)
  8. Najlacnejšia kostra grafu. (Algoritmus Union-FindSet. Kruskalov algoritmus.)
  9. Násobenie matíc. (Naivný algoritmus. Strassenov algoritmus. Efektívne umocňovanie matice. Tranzitívny uzáver grafu pomocou umocňovania matíc.)
  10. Dynamické programovanie (Konkrétne príklady použitia. Charakterizácia problémov riešiteľných dynamickým programovaním. Porovnanie iteratívneho prístupu a rekurzie s memoizáciou.)
  11. Ďalšie princípy tvorby efektívnych algoritmov. (Rozdeľuj a panuj, pažravé algoritmy, princíp vyváženosti, voľba vhodnej dátovej štruktúry. Konkrétne príklady použitia.)

Princípy tvorby softvéru

  1. Metódy vývoja softvéru (vodopádový model; I-I vývoj; agilné metodiky; LEAN; LEAN startup; porovnanie metodík)
  2. Ako popisovať softvér (4+1 view; základné typy diagramov UML)
  3. Požiadavky, tvorba špecifikácie (spôsoby zachytenia požiadaviek; typy požiadaviek; use case; scenario; user story; stopovateľnosť; change management)
  4. Architektúra a základné dizajnové princípy (architektúra softvéru; architektonicky signifikantné požiadavky; YAGNI; rule of 3; DRY; SOLID)
  5. Mechanizmy a návrhové vzory v konkurentných aplikáciách (best practices; imutable dátové štruktúry; BlockingQueue; Future; Promise; ThreadPool; ActiveObject)
  6. Testovanie a kvalita softvéru (typy testov; testovateľný kód; dependency injection; techniky na zabezpečenie kvality softvéru)
  7. Manažment konfigurácií a softvérové nástroje, ktoré ho podporujú (typy VCS; branch; merge; version; commit; GIT; Issue tracking)
  8. Implementácia, integrácia, dokumentácia a údržba (programovacie konvencie; continuous integration; dokumentácia a údržba softvéru)
  9. Manažment projektov, estimácie a manažment rizík (aktivity softvérového manažmentu; tradičná štruktúra tímu vs DevOps; problémy pri tvorbe estimácií; metódy tvorby estimácií)

Kontakt Hlavná stránka © 2012