Teorie ICT

Úvod

• Tomáš Vaníček• Stavební fakulta ČVUT, Thákurova 7, Praha

Dejvice, B407• vanicek@fsv.cvut.cz• Na ČZU kancelář 414, stará budova PEF

Obsah přednášek• Množiny, operace s množinami, kardinalita, fuzzy

množiny• Relace a operace• Logika, jazyk PROLOG• Formální jazyky• Konečné automaty, regulární jazyky• Jiné formální modely výpočtu• Výpočetní složitost algoritmů• Grafy• Analýza konkrétních algoritmů: grofové algoritmy,

třídění, hledání extrémů, heuristiky

Literatura

• Vaníček,J., Papík,M., Pergl,R., Vaníček,T.: Teoretické základy informatiky, Kernberg Publishing, 2007

• Vaníček,J., Papík,M., Pergl,R., Vaníček,T.: Mathematical Foundation of Computer Science, Kernberg Publishing, 2008

Teorie množin

• Množina je dobře definovaný soubor prvků • Otázka, zda prvek náleží množině, či ne, musí

být jednoznačně zodpověditelná.• Prvek x náležímnožině A, x A.• Objekt může být prvkem množiny, nebo ne.• Objekt nemůže být prvkem množiny vícekrát.

Třídy a množiny

• Množiny mohou být prvky jiných množin• Russelův paradox• Mathematika potřebuje pracovat s přesně

definovanými pojmy.• Pro pevné základy matematiky je nutná

axiomatická teorie množin.

Rovnost množin, podmnožiny

• Dvě množiny jsou si rovny, pokud mají stejné prvky.

• Množina bez prvků se nazývá prázdná: ø• Množina A je podmnožinou mnoožiny B,

pokud každý prvek A je i prvkem B.• Množina A je vlastní podmnožinou množiny B,

pokud je A podmnožinou B a A není rovno B.

Describing of sets

• By enumeration of elemnts– A={1,2,3}– B={Prague, Vienna, Budapest, Bartislava}– C={1,2,1,2,3,4,1}={1,2,3,4}={1,3,4,2}

• By distinctive predicate A={x|P(x)}– A={x|x N, x<4}– B={x|x is capital of central European country}

• By using already defined set – C={x N| x<4}

Common set notations• Z… Set of Integers• Z+ … Set of positive integers

• N… Set of nonnegative integers (natural numbers)• Q… Set of rational numbers• R… Set of real numbers• C… Set of complex numbers• R+, R-, Q+,…

Operace s množinami

• Sjednocení• Průnik• Doplněk• Symetrická diference• Potenční množina

Uspořádaná dvojice

• Uspořádaná dvojice (a,b) je množina {{a,b},a}. a je první prvek dvojice.

• Uspořádaná n-tice (a1,a2,…,an) může být zavedena pomocí indukce:– Pro n=2 je to uspořádaná dvojice (a1,a2)– Pro n>2 it je to uspořádaná dvojice obsahující

uspořádanou (n-1)-tici (a2,…,an) a prvek a1.

Kartézský součin

• Kartézský součin A x B je množina všech uspořádaných dvojic (a,b), kde A je z množiny A a b je z množiny B.

• Kartézský součin konečného systému množin A1xA2x…xAn je množina všech n-tic (a1,…,an) kde ai je z Ai.

Zobrazení• Zobrazení z množiny A do množiny B: pro

některé prvky A existuje přesně jeden obraz v B.• Zobrazení (totální) množiny A do množiny B: Pro

všechny prvky A existuje přesně jeden obraz v B.• Zobrazení z množiny A na množinu B (surjekce):

Každý prvek z B má svůj vzor v A, m(a)=b

Zobrazení

• Prosté zobrazení (injektivní)): pro různé vzory a1,a2 dostaneme různé obrazy b1,b2.

• Bijekce (vzájemně jednoznačné zobrazení) je prosté zobrazení A na B.

Mohutnost množin

• Dvě konečné množiny A,B mají stejnou mohutnost, pokud existuje vzájemně jednoznačné zobrazení A na B.

• Mohutnost množiny A se značí card(A), |A|, moh(A)

• Pokud card(A)≤card(B), pak existuje prosté zobrazení A do B.

• Pokud card(A)≥card(B), pak existuje zobrazení A na B.

Mohutnost nekonečných množin

• Dvě nekonečné množiny A,B mají stejnou mohutnost, pokud existuje vzájemně jednoznačné zobrazení A na B.

• card(N) = card(Z) = card(Q) = aleph0• Množina všech (nekonečných) posloupností

0,1 (L) má větší mohutnost než aleph0.• card(L)=card(R).• card(2M)>card(M)

Mlhavost• Možné příčiny nejistoty:– Stochastický charakter jevu (zítra bude pršet).– Kvantová nejistota (teplota vody v umyvadle je 10

stupňů)– Mlhavost pojmů (jsem vysoký člověk)

Fuzzy množiny• Klasická teorie množin : prvek do množiny patří, nebo

nepatří.• Exisstuje charakteristická funkce množiny A A, MA.– MA = 1, pokud x A, MA = 0, pokud není x A.

• Fuzzy množina je určena svou charakteristickou funkcí μA z univerza U na interval <0,1> – μA (x)= 1, pokud x je určitě v A.– μA (x)= 0, pokud x určitě není v A.– μA je mezi 0 a 1, pokud nevíme jistě, zda x je v A, nebo

není.

Fuzzy množiny

• Nosič A: supp(A)={xU|μA (x) > 0}.

• Jádro A: supp(A)={xU|μA (x) = 1}.

• Výška fuzzy množiny: sup(supp(A)).• Normální fuzzy množina: Výška je rovna 1.• α-hladina fuzzy množiny A {xU|μA (x) ≥ α}.

• Α-řez fuzzy množiny A {xU|μA (x) = α}.

Operace s fuzzy množinami

• A je podmnožina of B: μA (x) ≤ μB(x)

• B je doplněk of A: μB(x) = 1 - μA(x)

• C je (standardní) sjednocení A a B: μC(x)=max(μA(x), μB(x))

• C je (standardní) průnik A a B: μC(x)=min(μA(x),μB(x))

Fuzzy čísla

• Nechť a≤b≤c≤d jsou 4 reálná čísla, která splňují:– μA(x)=0 , pro x<a and x>d

– μA(x)=1 , pro x mezi b a c

– μA(x) je rostoucí mezi a a b.

– μA(x) je klesající mezi c a d.

• Takovou množinu A nazýváme fuzzy interval.• Pokud b=c nazýváme tuto množinu fuzzy číslo.