Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Informační technologie > TEORETICKÉ ZÁKLADY INFORMATIKY > Flashcards

TEORETICKÉ ZÁKLADY INFORMATIKY Flashcards

1
Q

MNOŽINY - základ

A
  • 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:
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

MNOŽINY - základ

A
  • 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:
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

MNOŽINY - základ

A
  • 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í:
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

MNOŽINY - Kartézský součin

A
  • 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ř:
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

MNOŽINY - Relace

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

DATA A ALGORITMY

A
  • Ú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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

VÝROKOVÝ A PREDIKÁTOVÝ KALKUL VE FORMULACI ALGORITMŮ A DAT - Výroková logika

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

VÝROKOVÝ A PREDIKÁTOVÝ KALKUL VE FORMULACI ALGORITMŮ A DAT - Pravdivostní tabulka

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

VÝROKOVÝ A PREDIKÁTOVÝ KALKUL VE FORMULACI ALGORITMŮ A DAT - Úplný systém logických spojek

A
  • Negace, konjukce, disjunkce
    - Negace a konjukce
    - Negade a disjunkce
    - Negace a implikace
    - Shefferova spojka
    - Piercova spojka
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

VÝROKOVÝ A PREDIKÁTOVÝ KALKUL VE FORMULACI ALGORITMŮ A DAT - Shefferova a Piercova spojka

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

VÝROKOVÝ A PREDIKÁTOVÝ KALKUL VE FORMULACI ALGORITMŮ A DAT - Způsob zápisu výrazů

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Normální formy výrokových formulí

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Predikátová logika

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Arita

A
  • 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í
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

GRAFY V PRÁCI INFORMATIKA

A
  • 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’.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Vlastnosti grafů

A

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.

17
Q

Grafy - pojmy

A
  • 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)
    Aplikace stromů
    - 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
18
Q

ALGORITMY A VYČÍSLITELNOST

A
  • 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.
19
Q

SYSTÉMOVÁ VĚDA

A
  • 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
20
Q

KYBERNETIKA A TEORIE INFORMACE

A

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 …
21
Q

FORMALIZACE V INFORMATICE

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

Informační technologie (10 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions