Bakalářská státnice - Informatika - Základy informatiky - obor Programování

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Súvisiace stránky: Státnice, Základy matematiky, Obecná informatika, Správa počítačových systémů

Tato stránka není kompletní a/nebo může obsahovat chyby!

Obsah

Základy teoretické informatiky

Zkompilovaná verze textu ze SVN státnicových otázek (pozor, nemusí být nutně aktuální).

Požadavky:[1]

  • Logika
    • jazyk, formule, sémantika, tautologie
    • Rozhodnutelnost, splnitelnost, pravdivost, dokazatelnost
    • Normální tvary výrokových formulí, prenexní tvary formulí predikátové logiky
  • Automaty
    • Chomského hierarchie
    • třídy automatů a gramatik
    • determinismus a nedeterminismus

Logika - jazyk.

Formule.

Sémantika.

Tautologie.

Rozhodnutelnost.

Splnitelnost.

Pravdivost.

Dokazatelnost.

Normální tvary výrokových formulí.

  • Věta o ekvivalenci. (zdroj: Štepánkův slajd 8 z VL3.pdf) (Jesliže jsou podformule A1..An fle A ekvivalentní s A'1..A'n a A' vytvořím záměnou těchto podformulí, je i A ekvivalentní s A')
  • Důkaz rozborem případů. (zdroj: Štepánkův slajd 15 z VL3.pdf) ( T mn. flí a A,B,C fle pak T,(A v B) |- C právě když T,A|-C a T,B|-C )
  • CNF a DNF. (zdroj: Štepánkův slajd 20 z VL3.pdf) (klauzule = disjunkce literlů, pak CNF je konjunkce klauzulí a DNF je disjunkce konjunkcí literálů)
  • Věta o normálních tvarech. (zdroj: Štepánkův slajd 22 z VL3.pdf) (Ke každé formuli lze sestrojit ekvivalentní formuli v CNF nebo DNF)

Prenexní tvary formulí predikátové logiky.

Automaty - Chomského hierarchie.

Třídy automatů a gramatik.

Determinismus a nedeterminismus.

  • Nedeterministický konečný automat. (zdroje: Bartákův slajd 4 z lecture03.pdf / wikipedie)
  • Deterministický zásobníkový automat rozeznává jen deterministické BK jazyky (podmnožina BK jazyků)
  • Turingův stroj: DTS = NTS
  • Konečný automat: DKA = NKA

Algoritmy a datové struktury

Zkompilovaná verze textu ze SVN státnicových otázek (pozor, nemusí být nutně aktuální).

Základní algoritmy - třídění.

Vyhledávání.

  • Lineární vyhledávání. (zdroj: wikipedie)
  • Binární vyhledávání. (zdroj: wikipedie)
    • Interpolační vyhledávání. (zdroj: wikipedie)
  • Hledání k-tého největšího prvku. (zdroj: wikipedie)

Algoritmy vyhledávání v textu.

Kombinatorické algoritmy.

  • Lineární programování a simplexová metoda. (zdroj: Berkeley)
  • Rychlá Fourierova transformace. (zdroj: Berkeley)

Grafové algoritmy - nejkratší cesta.

  • Dijkstrův algoritmus. (zdroj: wikipedie)
  • Bellman-Fordův algoritmus. (zdroj: wikipedie)
  • Floyd-Warshallův algoritmus. (zdroj: wikipedie)
slidy ze složitosti
skripta diskrétní mat. z všb

Minimální kostra.

Prohledávání grafů.

Barvení grafů.

Časová a prostorová složitost algoritmů.

NP-úplnost.

Něco málo je popsáno na posledních slajdech na tomto odkazu (Čepek-ADS): [2] A o něco více na (zdroje: Čepkovy slajdy Složitost I od str.48)

Shrnutí složitosti algoritmů na WolframMathWorld

Metoda rozděl a panuj.

Lineární struktury.

  • Pole.
  • Množina.
  • Spojový seznam.
    • Dvousměrný spojový seznam.
  • Zásobník.
    • Oboustranný zásobník.
  • Fronta.
    • Oboustranná fronta.
    • Prioritní fronta.

Stromové struktury.

Haldy.

Hašování.

(zdroj: Skripta Dat.Struktury - Koubek)

  • Hašovací funkce. (zdroj: wikipedie)
  • Hašovací tabulka. (zdroj: wikipedie)
  • Hašování se separovanými řetězci
  • Hašování s uspořádanými řetězci
  • Hašování s přemísťováním
  • Hašování se dvěma ukazateli
  • Srůstající hašování (LISCH, EISCH, LICH, EICH, VICH)
  • Hašování s lineárním přidáváním
  • Dvojité hašování
  • Univerzální hašování
  • Perfektní hašování

Databáze

Zkompilovaná verze textu ze SVN státnicových otázek (pozor, nemusí být nutně aktuální).

Podstata a architektury DB systémů. Konceptuální, logická a fyzická úroveň pohledů na data.

  • Architektura DB systémů. (zdroj: wikipedie, Architektury DB)
  • Architektura DB systémů a ostatně vše kolem databází (zdroj: [3])
  • Konceptuální, logická a fyzická úroveň pohledů na data. (zdroj: wikipedie)

Algoritmy návrhu schémat relací.

Normální formy.

Referenční integrita.

Transakční zpracování.

Uzamykací protokoly.

  • Protokoly řízení konfliktů. (zdroj: wikipedie)
  • Plán, sériový plán. (zdroj: wikipedie)
  • 2-fázové zamykání. (zdroj: wikipedie)
  • Striktní 2-fázové zamykání. (zdroj: wikipedie)
  • Rigorózní 2-fázové zamykání. (zdroj: wikipedie)
  • Konzervativní 2-fázové zamykání. (zdroj: wikipedie)

Zablokování.

ER-diagramy.

  • ER-diagramy. (zdroj: wikipedie)
  • Entita.
  • Vztah.
  • Atribut.
  • Slabé entitní typy.
  • Integritní omezení (kardinality).
  • Dědičnost (ISA-vztah).
  • Druhy dědičnosti (partial / exclusive, total / overlapping).

Metody návrhů IS.

  • Asi obecné informace o návrhu tabulek.

Základy SQL.

Indexy.

  • Index. (zdroj: wikipedie).
  • Manipulace s indexy v SQL.

Triggery.

  • Trigger. (zdroj: Kopeckého slajdy na Databázové aplikace)
  • Manipulace s triggery v SQL.

Uložené procedury.

Uživatelé.

  • Manipulace s uživateli. (zdroj: SQL Zoo)

Uživatelská práva.

Vícevrstevné architektury.

(zdroj: Slidy VUTBR)

Srovnání architektur: http://www.sei.cmu.edu/str/descriptions/clientserver.html

Vazba databází na internetové technologie.

  • Niesom istý, ale možno tým je myslené niečo takéto (zdroj: fit.vutbr)

Programovací jazyky a překladače

Zkompilovaná verze textu ze SVN státnicových otázek (pozor, nemusí být nutně aktuální).

Principy a implementace objektově orientovaných jazyků a jazyků s blokovou strukturou.

  • Třída.
  • Dědičnost.
  • Polymorfismus.
  • Obalení.
  • Virtuální funkce. (zdroj: Bednárkuv slide [4] a [5])

Běhová podpora vyšších programovacích jazyků.

Yaghobove slidy
  • Statická podpora a dynamická podpora.
  • Rozdělení paměti.
  • Stav paměti před spuštěním.
  • Konstruktory, destruktory globálních proměnných.
  • Volací konvence.

Oddělený překlad, sestavení, řízení překladu.

slidy k přednášce PRG029 - Programování v C a C++

Makroprocesory, skriptovací jazyky.

Neprocedurální programování.

  • Neprocedurální, logické a funkcionální programování.
  • Prolog.
  • Haskell.
  • Lisp.

Struktura překladače, lexikální, syntaktická analýza.

  • Lexikální analýza (token, pattern, lexém) (slidy Principy překladačů)
    • Pomocí konečného automatu
      • Chyba lexikální analýzy nastává když je ukončeno v nepříjmacím stavu (špatný vstup)
      • Řešení: ignorovat chybu, domyslet správn správný vstup
    • LA zdlouhavá -> Bufferování vstupu
    • Pro přenositelnost stačí měnit jen v LA
    • výstup - token (=vstup do syntaktické analýzy (=terminál))
    • pattern - regulární výraz, popisuje množinu řetězců pro určitý token
    • lexém (lexikální element) - odpovídá nějakému patternu nějakého tokenu
TokenLexémregulární výraz
whilewhilewhile
relop<,<=,=,<>,>,>=\<|\<=|=|\<>|>|>=
uint0, 123[0-9]+
  • Syntaktická analýza.
    • Pomocí zásobníkového automatu (BKG)
    • Zjišťuje, zda jsou slova na vstupu ze vstupního jazyka
    • Staví derivační strom, odstraňuje nejednoznačnosti jazyka (dangling else).
  • Sémantická analýza.
  • Generování mezikódu.
  • Optimalizace mezikódu.
  • Generování kódu.
  • Obsluha chyb.
  • Druhy jazyků (LR(0), LR(1), LR(k), SLR, LALR, GLR, LL(1), LL(k)).
slidy k přednášce principy překladačů
skripta k podobnému předmětu na slu.cz

Interpretované jazyky

(slidy Principy překladačů (9))

  • Překlad do kódu abstraktního stroje.
  • Abstraktní stroj může běžet na různých OS (=přenositelnost)
  • Je to ale pomalejší
  • Překlad JIT (Just-in-time)
  • Dynamická alokace jen s garbage collectorem
  • Dnes typicky Java

Generické programování a knihovny

Návrhové vzory.

  • Diplomová práce na téma návrhové vzory [6]

Architektura počítačů a operačních systémů

Zkompilovaná verze textu ze SVN státnicových otázek (pozor, nemusí být nutně aktuální).

Architektury počítače

Procesory, multiprocesory

Sběrnice, protokoly

Vstupní a výstupní zařízení

Architektury OS

História OS

Monolitický systém (Linux, windows), virtuálne stroje (Java, AS400), Mikrokernel

slidy (Yaghob)
slidy z Mississippi College
Wikipedia - operační systém
Wikipedia - Jádro

Vztah OS a HW, obsluha přerušení

Druhy prístupu k HW (port CPU, memory-mapped)

Druhy zariadení (blokové / znakové)

Prístup (sekvenčný / náhodný)

Synchrónnosť (disk vs. sieťovka)

Zdieľanie (sieťovka vs. tlačiareň) + spooling

Rýchlosť, smer dát (RO/RW...)

V sw: abstrakcia, jednotné pomenovanie, mount, obsluha chýb

Prerušenie, polling, DMA

Vrstvy I/O (hw -> obsluha prerušenia -> ovládač -> IO subsystém -> userspace IO)

Obsluha prerušenia (uloženie kontextu cpu, potvrdenie radiču, obsluha prerušenia, preplánovanie, obnova kontextu)

slidy (Yaghob)

Procesy, vlákna, plánování

Definície, vlastnosti, rozdiely.... (win vs. lin)

Stavy procesu, súvislosť s prerušeniami

Plánovanie ((ne)preemptívne) - ciele, kritériá, priority

Plánovacie algoritmy: FIFO, Round robin, Viacero front so spätnou väzbou; SMP, Realtime; Win. vs Linux

slidy (Yaghob)

Synchronizační primitiva, vzájemné vyloučení

Aktívne vs. pasívne čakanie, podmienky;

Aktívne: Petersnove riešenie, TSL

Pasívne: Zámky, monitory, semafory, správy (mutexy)

Obedujúci filozofovia, Problém ospalého holiča

slidy (Yaghob)

Zablokování a zotavení z něj

Druhy prostriedkov (odnímateľné? ...), práca s nimi, Coffmanove podmienky,

Riešenie zablokovania: Pštrosí algoritmus, Detekcia a zotavenie, vyhýbanie sa, prevencia

slidy (Yaghob)

Organizace paměti, alokační algoritmy. Principy virtuální paměti, stránkování, algoritmy pro výměnu stránek, výpadek stránky, stránkovací tabulky, segmentace

Hierarchia (veľkosť vs. rýchlosť)

Swapping, Preklad adries

Algoritmy prideľovania: first fit, best/worst fit, buddy systém

Virtuálna pamäť, stránkovanie (viacúrovňové)

TLB, (inverzné) stránkovanie, segmenty (stránkovanie+segmenty), použité tabuľky

Výpadky => výmena: Optimálna stránka, NRU, FIFO, druhá šanca, Hodiny, LRU, random [7]

slidy (Yaghob)

Systémy souborů, adresářové struktury

Vlastnosti súborov, pomenovanie, štruktúra (lineárne vs. stromy vs. sekvenčné)

Prístup k súborom (sekvenčný, priamy, memory mapping)

Operácie so súbormi (copy, move...)

Adresáre (hierarchia: stromy, DAG, obecný graf)

Alokácia miesta pre súbory

NTFS, INODE, ext2...

slidy (Yaghob) / Technická univerzita Ostrava

Plánování pohybu hlav disků

FCFS, SSTF, LOOK, CLOOK

RAID (pěkné vysvětlení RAIDů je na [8])

slidy (Yaghob)

Bezpečnost

Ceile útokov, útočníci, autentikácia, vnútorné útoky (vírusy, trojany...), kryptografia (hash, crc, šifrovanie)

slidy (Yaghob)

Sítě a internetové technologie

Zkompilovaná verze textu ze SVN státnicových otázek (pozor, nemusí být nutně aktuální).

ISO/OSI vrstevnatá architektura

TCP/IP.

Bezpečnost, firewally.

Spojované a nespojované služby, spolehlivost

Modulace, kódování

Broadband Druhy kódování Manchester kód Modulácia Modulačná rýchlosť Prenosová rýchlosť Šírka pásma Shannonuv teorém

Topologie sítí

HW a SW technická zařízení pro propojování sítí.

Bezpečnost

  • IPSec (zdroj: earchiv Jiřího Peterky) (Pozor! zdroje od profesora Peterky nejsou dostačující, pokud vás zkouší pan Galamboš!)

FUQS (frenquently unexpected questions) od p. Galambose:
- Jaký port používá IPSEC? - žádný, funguje nad síťovou vrstvou.
- Jak uzel A pošle uzlu B packet, když mezi nima stojí gateways, musí uzel A se nějak domlouvit s gateway, aby gateway zajistila IPSEC? - ne, prostě se gateway pošle natvrdo IPSEC packet a gateway podle hlavičky rozpozná, co má dělat.
- jiný zákeřňáky... doporučuju si přečíst slidy p. Galaboše z jeho stránek!(Soubor bohuzel uz neexistuje, zajimavy text jsem nasel tady:
An Illustrated Guide to IPsec ) (edit [4.9.2008]: súbor existuje, akurát je nutné ho zťahovať zo strojov v doméne mff.cuni.cz)
- pri googleni som našiel video z prednášky o IPSec(ČVUT 15.11.2003), možno to niekomu uľahčí učenie

  • principy fungování AH, ESP
    • transport mode
    • tunnel mode
  • firewall

Internetové a intranetové protokoly a technologie

značkovací jazyky (XML, HTML)

Citováno z „http://wiki.matfyz.cz/index.php?title=Bakalářská_státnice_-_Informatika_-_Základy_informatiky_-_obor_Programování&oldid=19240“