TEORETICKÉ ZÁKLADY INFORMATIKY Flashcards
MNOŽINY - základ
- Množina - souhrn objektů/prvků
- Určení množiny je možné dvěma způsby:
- Výčtem prvků - M={1,2,3}
- Vlastností - M = {nϵN | n < 4} (stejná množina jako výše)
- Počet prvků množiny značíme: |M| = 2
- Prázdná množina se zapisuje jako:
- Určení množiny je možné dvěma způsby:
MNOŽINY - základ
- Funkční symboly:
- A V B - sjednocení
- A ∧ B - průnik
- Pravidlem je, že každý podmnožina je podmnožinou sama sebe. Prázdná množina je podmnožinou každé množiny (I té prázdné)
- Potenční množina - značí se P(A). Tvoří se z množiny všech podmnožin určité množiny.
Doplňek množiny - Rozdíl prvků v množině A, a libovolné podmnožiny A. - Předikátové symboly:
MNOŽINY - základ
- Jsou taktéž nadefinované následující množiny:
- N - přirozená čísla; 1, 2, 3, … nekonečno
- Q - recionální čísla; desetinná čísla jež lze vyjádřit ve zlomku
R - reálná čísla; čísla, jež lze znázornit na číselné ose
C - komplexní čísla; uspořádaná dvojice reálných čísel.
Platí:
MNOŽINY - Kartézský součin
- Kartézský součin (A x B) - množina všech uspořádaných dvojic takových, že první prvek patří do první množiny a druhý do druhé množiny - např:
MNOŽINY - Relace
Relace - libovolná podmnožina kartézského součinu
- Mezi vlastnosti relací patří:
- Reflexivita (sama se sebou)
- Symetrie
- Antisymetrie
- Tranzitivita
- Úplnost
- Zobrazení - relace, kde ke každému prvku z množiny A existuje jediný prvek z množiny B, který je s ním v relaci
DATA A ALGORITMY
- Údaj - hodnota získaná měřením/pozorováním/zaznamenáváním reálné skutečnosti
- Data - Jakékoliv vyjádření skutečnosti, které můžeme uchovat, interpretovat, zpracovat či posílat nazývýme daty. Zdroj pro informace. Sama o sobě jsou data nehmotná, ale musí být uchovávana skrze hmotné médium.
- Informace - Kombinace dat a jejich intepretace. Snižují neznalost. Míra tohoto snížení neznalosti je závislá na tom, kdo danou informaci
- Algoritmus - Algoritmus je přesný postup, který se využívá pro řešení nějaké úlohy. V oblasti programování se jím myslí teoretický princip řešení problému.
- Znalosti - ucelený komplex informací o nějaké objektivní realitě; výsledek poznávacího procesu
- Syntaxe - Struktura a způsob zápisu
Sémantika - Význam
VÝROKOVÝ A PREDIKÁTOVÝ KALKUL VE FORMULACI ALGORITMŮ A DAT - Výroková logika
- Výrok - tvrzení, o němž je smysluplné prohlásit, zda je pravdivé či nikoliv
- Složený výrok - Výrok, který je tvořen souvětím, tj. Více výroky spojenými logickými spojkami
- Jazyk výrokové logicky:
- Výrokové proměnné - písmena abecedy, např. p = venku prší
- Logické spojky
- Negace - obrácení pravdivosti
- Disjunkce - nebo
- Konjukce - a zároveň
- Implikace - z toho plyne
- Ekvivalence - právě tehdy když
- Závorky - pro zápis priority
- Tautologie - vždy pravdivý výrok
Kontradikce - Vždy nepravdivý výrok
VÝROKOVÝ A PREDIKÁTOVÝ KALKUL VE FORMULACI ALGORITMŮ A DAT - Pravdivostní tabulka
VÝROKOVÝ A PREDIKÁTOVÝ KALKUL VE FORMULACI ALGORITMŮ A DAT - Úplný systém logických spojek
- Negace, konjukce, disjunkce
- Negace a konjukce
- Negade a disjunkce
- Negace a implikace
- Shefferova spojka
- Piercova spojka
VÝROKOVÝ A PREDIKÁTOVÝ KALKUL VE FORMULACI ALGORITMŮ A DAT - Shefferova a Piercova spojka
VÝROKOVÝ A PREDIKÁTOVÝ KALKUL VE FORMULACI ALGORITMŮ A DAT - Způsob zápisu výrazů
- Infixový - Operátor mezi operandy
- Prefixový - Operátor před operandy
- Z infixového na prefixový zápis lze převod provést pomocí stromového rozkladu
- Postfixový - Operátor za operandy
- Z infoxového na postfixový lze převod provést pomocí algoritmu slepé koleje
Z postifxu na infix - pomocí zásobníkového automatu
Normální formy výrokových formulí
- DNF - Disjuktivní normálová forma - Disjunkce konjukcí (v závorkách jsou konjukce)
- KNF - Konjuktivní normálová forma - Konjukce disjunkcí (V závorkách jsou disjunkce)
Predikátová logika
- Pokud potřebujeme zkoumat vlastnosti víc než jediného objektu - potřebujeme se ptát, zda danou vlastnost má z dané množiny:
- Alespoň jeden prvek
- Každý prvek
- Tento zápis se nazývá predikát. Po dosazení vhodné hodnoty do tohoto zápisu bychom měli získat smysluplný výrok.
Arita
- Arita - četnost; určuje počet operandů/parametrů či argumentů
- Podle arity se rozlišují operátori:
- Unární (negace, faktorial)
- Binární (+-)
- Ternární
GRAFY V PRÁCI INFORMATIKA
- Graf - umožňuje vizuální reprezentaci vztahů v různých množinách prvků
- Využití: např. problém obchodního cestujícího, GIS, teorie her, management, dopravní sítě.
- V rámci informatiky jsou grafy potřebné pro řízení projektu nad IS, prozkoumání prvních návrhů aplikačního software, pro zkoumání ERD, výsledků datové analýzy, DFD, výsledků procesní analýzy …
- Usnadňují vyhledávání, řazení, kódování
- Pokud x=y, h je smyčka
- Uzel, který není incidentní s žádnou hranou se nazývá izolovaný
- Neorientovaný graf - ke každé hraně h existuje protisměrná hrana h’.
Vlastnosti grafů
Bipartitní
Nemá žádný uzel se smyčkou.
Pojmem bipartitní graf nebo sudý graf se v teorii grafů označuje takový graf, jehož množinu vrcholů je možné rozdělit na dvě disjunktní množiny tak, že žádné dva vrcholy ze stejné množiny nejsou spojeny hranou.
- Bipartatitní je takový graf, kdy mezi uzly nevznikne cyklus s lichým počtem hran (pokud například A je propojeno s B a B propojeno s C a C propojeno s A, graf již není bipartitní - lichý počet hran v cyklu)
Diskrétní
- Graf bez hran.
Jednoduchý
- U jednoduchého grafu není smyčka z jednoho prvku na ten samý prvek. Tento graf také neobsahuje žádné násobné hrany.
- (na rozdíl od prostého, nesmí mít smyčku)
Konečný
- Má konečný počet uzlů a hran
- Nekonečný graf může být zapsán pouze zápisem (například s množinou čísel)
Les
- Vždy neorientovaný graf
- Více grafů, které jsou stromy (?)
Multigraf
- Multigraf je graf, kde jsou u nejméně dvou uzlů vícenásobné hrany (pokud není graf jednoduchý, prostý diskrétní, je multigrafem)
Orientovaný
- Hrany v grafu musí mít směr
Ohodnocený
- Ohodnocený graf je takový graf, kde hrany jsou ohodnoceny realnými čísly
Prostý
- Prostý je graf pokud není multi-grafem či pokud není diskrétní;
- Každý uzel má mezi dalšímu uzly max. jednu hranu
- (na rozdíl od jednoduchého, může mít smyčku)
- Graf může být prostý i jednoduchý pokud nemá násobné hrany a nemá smyčky.
Rovinný
- Pro rovinný graf existuje znázornění v 2D, kdy se žádné dvě hrany nekříží
SOUVISLÝ
- U souvislého grafu se lze ze všech uzlů dostat do uzlů zbývajících
- Pokud u neorientovaného grafu platí tato podmínka, stává se graf pouze “souvislý (ne slabě, silně).
Slabě
- V případě grafu orientovaného pokud zanedbáme směr hran, je graf slabě souvislý.
Silně
- V případě orientovaného grafu, kdy se bere v potaz směr hran, je graf silně souvislý.
Strom
- Je bez cyklu a z každé hrany se dá dostat do ostatních (je souvislý).
- Existuje varianta stromu, která se jmenuje “binární strom.” U něj má každý uzel maximálně dva následníky.
Úplný
- U tohoto grafu z každého uzlu vede do dalšího uzlu hrana.
Grafy - pojmy
- Eulerovský tah - Tah, který obsahuje každou hranu právě jednou
- Hamiltonovská cesta - Cesta procházející každým uzlem právě jednou (problém obchodního cestujícího)
- Komponenta - Maximální souvislý podgraf nesouvislého grafu
- Popis grafů - lze provést pomocí matic (matice sousednosti - uzly x uzly; matice incidence - uzly x hrany)
- Binární vyhledávací strom - hodnoty v levém podstromu jsou menší než v kořeni; v pravém jsou větší než v kořeni
- Řazení - rodič má větší hodnotu než-li potomciGrafové algoritmy
- Prohledávání grafu:
- Do šířky - FIFO - fronta
- Do hloubky - LIFO - zásobník
- Hledání nejkratší cesty - u každého uzlu uchovávana délka nejkratší cesty a předchozí uzel
- Djikstrův algoritmus - pro pro grafy s nezáporným ohodnocením hran - udržuje si zpracované a nezpracované uzly
- Bellman-Fordův algoritmus - připouští hrany se záporným ohodnocením; založen na prohledávání do šířky
- Hledání minimální kostry - Kruskalův algoritmus
ALGORITMY A VYČÍSLITELNOST
- Teorie vyčíslitelnosti - vědní obor, jež zkoumá algoritmitickou řešitelnost problémů
- Dělí problémy na algoritmické řešitelné či neřešitelné
- Používá se zde Turingův stroj - konečný automat bez paměti s nekonečnou páskou (jedná se o zjednodučený model počítače)
- Má jasnou formální definici umožňující dokazovat řešitelnost či neřešitelnost problémů
Cílem je ukázat, že existují problémy neřešitelné pomocí počítače.
SYSTÉMOVÁ VĚDA
- Obor zabývající se systémy
- Zahrnuje několik vědních disciplín:
- Systémové teorie (obecná teorie systémů, kybernetika)
- Systémové aplikace (systémová analýza asyntéza, systémové inženýrství, operační výzkum)
- Pomocné disciplíny (teorie množiny, teorie grafů, teorie algoritmů, teorie her)
- Pojem systém se používá pro studium složitých reálných problémů. Vyjadřuje množiny prvků ve vzájemné interakci
- Obecná teorie systémů - využívána jako základní metodologický nástroj ve všech ostatních disciplínách systémové vědy
- Zkoumá vlastnosti systému (statické, dynamické, kauzalní)
- Vztah ke kybernetice, teorii řízení a teorii informace
- Teorie systémů je součástí teoretické kybernetiky
- Dělení systémi:
- Jednoduché / složité
- Uzavřené / otevřené - otevřené mají vazbu s prvky mimo systém
- Statické / dynamické - dynamický mají definovaný stav, který se může v čase měnit
- Deterministické / stochastické / neurčité (fuzzy)
- Deterministické - Zákonitosti vymezující chování systému jsou jednozačně určeny
- Stochastické - Proměnné se chovají náhodně
- Fuzzy - Funkce nelze vyjádřit jakoukoliv zákonitostí
- Adaptivní / neadaptivní
- Reálné / abstraktní / metasystémy
- Popis systému:
- Slovně
- Blokové diagramy
- Grafy
- Matice
- Množiny
- Rovnice
- Systémová analýza - zjišťování struktury a chování systému; výsledkem jsou modely
- Systémová syntéza - Tvorba složitých systémů na základě poznatků analýzy
- Zahrnuje několik vědních disciplín:
KYBERNETIKA A TEORIE INFORMACE
Kybernetika
- Věda o výměně dat v živých organismech a ve strojích
- Věda o sběru, přenosu a zpracování informace
- Informatika byla dříve chápána jako podmnožinou pojmu kybernetika
Teorie informace - Zatímco informatika zkoumá informace z kvalitativního hlediska, teorie informace se zaměřuje na kvantitativní hledisko - Jde především o množství informace ve zprávě a jeho měření, kódování a děkódování zpráv a přenos zpráv - Informační entropie - míra neurčitosti která se odstraňuje přijetím zprávy; vyjadřuje množství informace obsažené ve zprávě - Při měření množství informace ve zprávě využíváme poznatků z pravděpodobnosti - čím větší pravděpodobnost, tím menší informace - Jednotky informace jsou b, B, kB, MB …
FORMALIZACE V INFORMATICE
- Převod vět z přirozeného jazyka do formalizovaného jazyka logiky
- Na začátku převádíme větu bežného jazyka na výrokovou či predikátovou formuli
- Během formalizace se věta rozloží na části, které se spojí logickými spojkami.
