Súvisiace stránky: Státnice, <Bakal%25C3%25A1%25C5%2599sk%25C3%25A1_st%25C3%25A1tnice_-Informatika-Z%25C3%25A1klady_matematiky>, <Bakal%25C3%25A1%25C5%2599sk%25C3%25A1_st%25C3%25A1tnice-Informatika-Z%25C3%25A1klady_informatiky-obor_Obecn%25C3%25A1_informatika>, <Bakal%25C3%25A1%25C5%2599sk%25C3%25A1_st%25C3%25A1tnice-Informatika-Z%25C3%25A1klady_informatiky-_obor_Spr%25C3%25A1va_po%25C4%258D%25C3%25ADta%25C4%258Dov%25C3%25BDch_syst%25C3%25A9m%25C5%25AF>

{{Not_complete}}

Základy teoretické informatiky

Zkompilovaná verze textu ze <Koordinace> (pozor, nemusí být nutně aktuální).

Požadavky:http://www.mff.cuni.cz/studium/bcmgr/ok/i3a6.htm

  • 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.

  • Jazyk VL. (zdroj: <Petr%20Štěpánek> 35 z VL0.pdf)

  • Jazyk PL. (zdroj: <Petr%20Štěpánek> 2 z PL0.pdf)

  • <obecne%20rozdeleni%20symbolu%20a%20znaku%20logiky>

Formule.

  • Formule VL. (zdroj: <Petr%20Štěpánek> 36 z VL0.pdf)

  • Term PL. (zdroj: <Petr%20Štěpánek> 4 z PL0.pdf)

  • Formule PL. (zdroj: <Petr%20Štěpánek> 6 z PL0.pdf)

  • Podterm, podformule, volné a vázané proměnné, otevřené a uzavřené formule. (zdroj: <Petr%20Štěpánek> 8-10 z PL0.pdf)

Sémantika.

  • Pravdivostní ohodnocení preměnných VL. (zdroj: <Petr%20Štěpánek> 38 z VL0.pdf)

  • Pravdivostní hodnota formule VL. (zdroj: <Petr%20Štěpánek> 41 z VL0.pdf)

  • Interpretace jazyka PL. (zdroj: <Petr%20Štěpánek> 12 z PL0.pdf)

  • Ohodnocení proměnných PL. (zdroj: <Petr%20Štěpánek> 14 z PL0.pdf)

  • Interpretace termu PL. (zdroj: <Petr%20Štěpánek> 14 z PL0.pdf)

Tautologie.

  • Pojem tautologie. (zdroj: <Petr%20Štěpánek> 43 z VL0.pdf, skripta strana 16)

  • Tautologický důsledek. (zdroj: <Petr%20Štěpánek> 44 z VL0.pdf)

Rozhodnutelnost.

  • Množina kódů vět teorie. (zdroj: <Petr%20Štěpánek> 12 z PL5.pdf)

  • Rozhodnutelnost a nerozhodnutelnost. (zdroj: <Petr%20Štěpánek> 12 z PL5.pdf)

  • Nerozhodnutelnost PL (Church). (zdroj: <Petr%20Štěpánek> 6 z PL5.pdf)

Splnitelnost.

  • Splnitelné množiny formulí. (zdroj: <Petr%20Štěpánek> 43 z VL0.pdf)

Pravdivost.

  • Pravdivá formule VL. (zdroj: <Petr%20Štěpánek> 41 z VL0.pdf)

  • Tarskeho definice pravdy. (zdroj: <Petr%20Štěpánek> 16-18 z PL0.pdf)

  • Logicky pravdivá formule PL. (zdroj: <Petr%20Štěpánek> 20 z PL0.pdf)

Dokazatelnost.

  • Formální systém VL. (zdroj: <Petr%20Štěpánek> 47 z VL0.pdf)

  • Schémata axiomů. (zdroj: <Petr%20Štěpánek> 50 z VL0.pdf)

  • Odvozovací pravidlo (modus ponens). (zdroj: <Petr%20Štěpánek> 51 z VL0.pdf)

  • Důkaz, dokazatelnost. (zdroj: <Petr%20Štěpánek> 52 z VL0.pdf)

  • Důkaz, dokazatelnost z předpokladů. (zdroj: <Petr%20Štěpánek> 54 z VL0.pdf)

  • Věta o dedukci. (zdroj: <Petr%20Štěpánek> 55 z VL0.pdf)

  • Bezespornost. (zdroj: <Petr%20Štěpánek> 72 z VL0.pdf)

  • Věta o bezespornosti a splnitelnosti. (zdroj: <Petr%20Štěpánek> 81 z VL0.pdf)

  • Věty o úplnosti. (zdroj: <Petr%20Štěpánek> 86 z VL0.pdf)

  • Věta o kompaktnosti VL. (zdroj: <Petr%20Štěpánek> 89 z VL0.pdf)

  • Axiomy pro kvantifikátory PL. (zdroj: <Petr%20Štěpánek> 35 z PL0.pdf)

  • (Odvozovací) pravidlo generalizace pro PL. (zdroj: <Petr%20Štěpánek> 36 z PL0.pdf)

  • Věta o korektnosti. (zdroj: <Petr%20Štěpánek> 10 z PL2.pdf)

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

  • Věta o ekvivalenci. (zdroj: <Petr%20Štěpánek> 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: <Petr%20Štěpánek> 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: <Petr%20Štěpánek> 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: <Petr%20Štěpánek> 22 z VL3.pdf) (Ke každé formuli lze sestrojit ekvivalentní formuli v CNF nebo DNF)

Prenexní tvary formulí predikátové logiky.

  • Prenexní tvar formule. (zdroj: <Petr%20Štěpánek> 3 z PL1.pdf) (fle, kde jsou všechny kvantifikáory na začátku a zbytek je otevřená formule)

  • Věta o prenexních tvarech. (zdroj: <Petr%20Štěpánek> 5 z PL1.pdf) (Ke každé fli lze sestrojit fle v prenexním tvaru, která je s ní ekvivalentní)

  • Prenexní operace. (zdroj: <Petr%20Štěpánek> 7 z PL1.pdf)

Automaty - Chomského hierarchie.

  • Přepisovací (produkční) systém. (zdroj: <Roman%20Barták> 4 z lecture06.pdf)

  • Odvození (derivace). (zdroj: <Roman%20Barták> 4 z lecture06.pdf)

  • Formální (generativní) gramatiky. (zdroj: <Roman%20Barták> 6 z lecture06.pdf)

  • Chomského hierarchie. (zdroj: <Roman%20Barták> 7 z lecture06.pdf)

  • Nevypouštěcí gramatiky a převod na ně. (zdroj: <Roman%20Barták> 9-11 z lecture06.pdf)

Třídy automatů a gramatik.

  • Definice všech 4 tříd gramatik. (zdroje: <Roman%20Barták> slajd 7 z lecture07.pdf / wikipedie)

  • Definice konečného automatu. (zdroje: <Roman%20Barták> slajd 9 z lecture01.pdf / wikipedie)

  • Definice zásobníkového automatu. (zdroje: <Roman%20Barták> slajd 2 z lecture08.pdf / wikipedie)

  • Definice Turingova stroje. (zdroje: <Roman%20Barták> slajd 4 z lecture11.pdf / wikipedie)

  • Převody mezi nimi. (zdroj: wikipedie)

  • L0(rekurzivně spočetné jazyky) = turingův stroj

  • L1(kontextové jazyky) = lineárně omezený automat (NTS s omezenou páskou)

  • L2(bezkontextové jazyky) = nedeterministický zásobníkový automat

  • L3(regulární/pravé lineární jazyky) = konečný automat

Determinismus a nedeterminismus.

  • Nedeterministický konečný automat. (zdroje: <Roman%20Barták> 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 <Koordinace> (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): http://ktiml.mff.cuni.cz/%7Ecepek/ADS-KS.ppt 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 <Koordinace> (pozor, nemusí být nutně aktuální).

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

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 <Koordinace> (pozor, nemusí být nutně aktuální).

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

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

:: <Jakub%20Yaghob> 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

<table align="center" border="1"> <tr><td width="50">Token</td><td width="150">Lexém</td><td width="150">regulární výraz</td></tr>

<tr><td width="50">while</td><td width="150">while</td><td width="150">while</td></tr> <tr><td width="50">relop</td><td width="150"><,<=,=,<>,>,>=</td><td width="150"><|<=|=|<>|>|>=</td></tr>

<tr><td width="50">uint</td><td width="150">0, 123</td><td>[0-9]+</td width="150"></tr> </table>

  • 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

  • Generické programování (zdroj: wikipedia.cz)

  • Šablony (zdroj: slajdy OOP)

  • Metaprogramovanie (požiadavka Yaghoba - ukážka na príklade faktoriálu) - strana 12: http://tjn.fjfi.cvut.cz/~virius/prednes/prezen/SabMeta.pdf

Návrhové vzory.

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

Zkompilovaná verze textu ze <Koordinace> (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 http://en.wikipedia.org/wiki/Page_replacement_algorithms

:: 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 http://www.netcorp.cz/storage_systems/raid_description.htm)

:: 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 <Koordinace> (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)

  • principy fungování AH, ESP

    • transport mode

    • tunnel mode

  • firewall

Internetové a intranetové protokoly a technologie

značkovací jazyky (XML, HTML)