MATEMATYKA DYSKRETNA

2010/2011

 

Zakres:

1. Rachunek zdań ; Rachunek zbiorów
 
2. Rachunek predykatów ;  Schematy wnioskowania
 
3.Funkcje całkowitoliczbowe ;  Kombinatoryka
 
4. Rekurencje ; Postać zwarta schematu rekurencyjnego 
 
5. Schemat Hornera ;  Kongruencje
 
6. Grafy – definicje, klasyfikacje, reprezentacje, właściwości
 
7. Grafy – algorytmy na grafach

 

Literatura:

 

http://wazniak.mimuw.edu.pl/index.php?title=Strona_g%C5%82%C3%B3wna

Ross K.A., Wright C.R.B.: Matematyka dyskretna, PWN, Warszawa 1996.
Sysło M.M.: Algorytmy, WSiP, Warszawa 1997.
Lipski W.: Kombinatoryka dla programistów, WNT, Warszawa 1982.
Wilson R.J.: Wprowadzenie do teorii grafów, Warszawa 1998.
Bryant V.: Aspekty kombinatoryki, WNT, Warszawa 1997.
Ziembiński Z., Logika praktyczna, PWN, Warszawa 2000.

 

MATEMATYKA DYSKRETNA

Wymiar: 2 1 0 0 0 

Wymagania: matematyka na poziomie szkoły średniej

Zaliczenie  przedmiotu:  Ocena  z  ćwiczeń  audytoryjnych  wystawiona  na  podstawie  trzech 
testów i aktywności na ćwiczeniach

Założenia programowe: Zapoznanie z podstawowymi obiektami i strukturami matematyki 
dyskretnej,  przydatnymi  do  wysłuchania  dalszych  pozostałych  przedmiotów  poświęconych 
projektowaniu  i  analizie  algorytmów  wspomagania  decyzji,  a  także  ich  dalszych 
komputerowych implementacji.

Wykład:

1.  Podstawy  logiki  i  teorii  mnogości.  –  Elementy  teorii  zbiorów  –  zbiory,  alfabety, 
rachunek  zbiorów,  funkcje.  Zastosowania  –  maszyna  Turinga.  Funkcje  całkowitoliczbowe: 
powała i podłoga. Zastosowanie – szacowanie długości słowa maszynowego. 

2. Podstawy logiki i teorii mnogości. – Logika pierwszego rzędu. Rachunek zdań. Reguły 
wnioskowania  (modus  ponens,  zasada  rezolucji).  Zastosowania  w  strukturach  systemów 
ekspertowych. 

3. Podstawy logiki i teorii mnogości. – Dowody formalne, pojęcia poprawności i pełności 
systemu logicznego. Teorie formalne. 

4.  Asymptotyka  funkcji  liczbowych.  –  Zastosowania  –  szacowanie  złożoności 
obliczeniowej. Problemy decyzyjne i optymalizacyjne. Problemy łatwe i trudne. Zastosowania 
- zasada dziel i zwyciężaj.

5.  Elementy  teorii  liczb  –  Podzielność  liczb  naturalnych  –  algorytm  Euklidesa. 
NWP, NWW.  Operator modulo.  Liczby pierwsze i rozkład  liczb  na czynniki pierwsze. 
Zastosowania – kryptografia. Liczby doskonałe. Równanie diofantyczne. 

6.Elementy  kombinatoryki  –  Zasada  gołębnika.  Zasada  włączania  i  wyłączania. 
Generowanie  obiektów  kombinatorycznych.  Permutacje,  kombinacje,  wariacje. 
Zastosowania – szacowanie złożoność obliczeniowej.
 
7.  Elementy  kombinatoryki  –  Definicje,  algorytmy  i  zależności  rekurencyjne. 
Rozwiązywanie  zależności  rekurencyjnych  –  przez  podstawianie  i  za  pomocą 
równania charakterystycznego. Zastosowania - symbol Newtona, trójkąt Newtona.

8.  Elementy  kombinatoryki  –  Kongruencje.  Zastosowania  –  na  jaka  cyfrę  kończy 
się  liczba  5

100

?  Systemy  liczbowe.  Schemat  Hornera.  Zastosowania  –  szybkie 

potęgowanie.

9.  Elementy  teorii  grafów  –  Relacje  i  ich  reprezentacje.  Grafy  symetryczne  i 
skierowane.  Charakterystyki  -  drogi,  cykle,  pętle,  itd.  Właściwości  i  klasyfikacje 
grafów: drzewa, grafy dwudzielne, grafy pełne, grafy planarne, itp.

10.  Elementy  teorii  grafów  –  Badanie  właściwości  grafów.  Grafy  Eulera  i 
Hamiltona.  Izomorfizm  grafów.  Zastosowania  –  wybrane  ilustracje  problemów 
łatwych i trudnych. Strategie zachłanne.

11  Elementy  teorii  grafów.  Macierzowe  reprezentacje  grafów  –  macierz 
incydencji, macierz stowarzyszona. Zastosowania – badanie właściwości grafów.

12  Elementy  teorii  grafów.  Algorytmy  na  grafach  –  drzewa  rozpinające.  Zastosowania  – 
wyznaczanie
 sieci instalacji elektrycznej.

13 Elementy teorii grafów. Algorytmy na grafach – zadania najkrótszych dróg. Zastosowania – 
wyznaczanie najkrótszej drogi (metoda podziałów i ograniczeń).

14. Elementy teorii grafów –Grafy AND/OR. Zastosowania – planowanie działań (np. montażu). 

Ćwiczenia
Ćwiczenia  polegają  na  rozwiązywaniu  zadań  opracowanych  do  poszczególnych  partii  materiału  z   
wykładu. 
Są to głównie ćwiczenia rachunkowe, ale w wielu przypadkach sprowadzają się do „giełdy” pomysłów 
nowych  (niestandardowych)  rozwiązań  oraz  skojarzeń  i  pomysłów  związanych  z  praktycznym 
wykorzystaniem 
zdobytych umiejętności.

Literatura:

Ross K.A., Wright C.R.B., Matematyka dyskretna, PWN, Warszawa 1996.

Sysło M.M., Algorytmy, WSziP, Warszawa, 1997

Lipski W., Kombinatoryka dla programistów, WNT, Warszawa, 1982

Wilson R.J., Wprowadzenie do teorii grafów, PWN, Warszawa, 1998.

Ziembiński Z., Logika praktyczna, PWN, Warszawa 2000.

Zaliczenie

:

 

•MAX{„Z”,”0”} , gdzie:

                                   Ind.Akt.Studenta

•IF((#1 + #2 + #3)/3  3)  THEN („Z” = 3 + Bonus);    Bonus = 

    * 0.5

                                                                                                   (MAX Akt. 
Grupy)/4

Test  (przykład)

1. Uprość wyrażenie: (p  p)  (p  p)    ?

2. Oblicz wartość formuły:  (q  p)    ?   , dla q = p = 1

3. Wyznacz 

pierwszych 

pięć 

elementów 

zbioru: 

{5/n 

| 

nN} 

= 

{     ,     ,      ,      ,     }

4. Czy prawdą jest, że:  (A \ B) \ C  =  A \ (B \ C)

5.    Czy prawdą jest, że z faktów a  i  b wynika fakt  g?

R1: IF  b  THEN  h

R2: IF  b  i  h  THEN  f

R3: IF  a  i  b  THEN  c

R4: IF  c  i  h  THEN  g

Wykład 1

1.Elementy teorii zbiorów 

•rachunek zdań,

•sprzeczności i tautologie, reguły wnioskowania (reguła modus ponens),

•zastosowania w strukturach systemów ekspertowych,

•zbiory i działania na zbiorach, 

•rachunek predykatów, zasada rezolucji,

Rachunek zdań

ZDANIA, SPÓJNIKI, FORMUŁY

Poniższe napisy nie są formułami 

p     q


Ten napis na pewno nie jest formułą,

(p  q))

Poniższe napisy są formułami 

p   (r  q)
q
p  q

 p    p    p
 (p    p)    p      p    (p    p)

Oznaczenia

N – zbiór liczb naturalnych (bez zera)

N

0

 - zbiór liczb naturalnych z zerem

Z – zbiór liczb całkowitych

Z

+

- zbiór liczb całkowitych dodatnich

Q – zbiór liczb wymiernych

R – zbiór liczb rzeczywistych

x  A – x należy do zbioru A (x jest elementem zbioru A)

x  A – x nie należy do zbioru A

A  B – zbiór A jest podzbiorem zbioru B (zbiór A zawiera się w zbiorze B)

A  B - zbiór A nie jest podzbiorem zbioru B

A  B – iloczyn zbiorów

A  B – suma zbiorów

A \ B – różnica zbiorów

A  B – różnica symetryczna zbiorów

Ø = { } - zbiór pusty

|A|- moc zbioru A (liczba elementów zbioru A)

 - znak sumy

 - znak iloczynu

x – dla każdego x

x – istnieje x

! x – istnieje jedno x

  – ...nieprawda, że... (negacja)

  – ...lub... (alternatywa)

  – ...i... (koniunkcja)

 – ...jeżeli, to... (implikacja)

 – ...wtedy i tylko wtedy... (równoważność)

A   - A jest zdefiniowane jako...

 x  - największa liczba całkowita niewiększa niż x

 x  - najmniejsza liczba całkowita niemniejsza niż 

x

SPÓJNIKI ZDANIOWE

Zapis 

Nazwa 

Symbol

..nieprawda, że.. 

negacja 



...lub... 

alternatywa 



...i... 

koniunkcja 



...jeżeli...to... 

implikacja 



...wtedy i tylko wtedy gdy…

równoważność 



                    HIERARCHIA 
SPÓJNIKÓW

  ;    ;    ;    ;  

p



p

0

1

1

0

 

 0

  1

0

 0

  1

1

 1

 1

   

  0

 1

  0

  0

 0

  1

  0

 1



0

1

0

1

1

1

0

1

a  b    a  b

Sprawdź które z następujących formuł są 
tautologiami

 

 

 
 

Sprawdź:

    (a  b)  (b  c)  (c  a)  b  ,

    ((p  q)  p)   (p  

q)

    ((p  q)  p)   (p  q

)

   P R A W A

Przemienności

p  q   q  p

,

p  q   q p

Łączności

p  (q  r)   (p  q)  r ,

p  (q  r)   (p q)  r

Rozdzielności mnożenia względem dodawania

(p  q)  r    p  r  q  r

Rozdzielności dodawania względem mnożenia

(p  q)  r    (p  r)  (q  r)

De Morgana

 (p  q)   p  q ,   (p  q)   p   q

Powtórzeń

p  p  p … p   p ,

p   p  p … p   p

PRAWA (TAUTOLOGIE, SPRZECZNOŚCI)

Zdania złożone, które są zawsze prawdziwe, niezależnie od 
wartości logicznych
zmiennych zdaniowych p, q nazywamy tautologiami.

p  p  1            ;     (p  p)  q)   q

Zdaniem sprzecznym (sprzecznością) jest zdaniem złożonym, 
które jest zawsze
fałszywe.

p  p  0               ;   (p  p)  0

(p  p)  p    

  p  (p p)    

( p  p)  p    p  ( p  p) 

 
 

1 
p    

p  1

0 p

 p  1

 

 

 p

1

p (p  p)(A  p)   (p  A)

A

0         1               0        0         1
1         1                1       1          1

((a  b)  (a  d))  (b  d)    

    a  b  d

((a  (b  d))  (b  d)

p  p p … p   p

(a  (b  d))  (b  d) ,

a   b  b  d

(a  (b  d))  (b  d)

,

(p  r)   p  q

(a  b  d)  ( (b  d)  (b  d))

 ,

a  b  d

 

,

   x  x   

1

(p  q)  r    (p  r)  (q  r)

(p            q  )          
r

1. Podaj przykład wartościowania zmiennych tak aby poniższe formuły były 

wartościowane na 0

 

p   (q  r)
(p   q)  r
(p  q)

2. Podaj przykład wartościowania zmiennych tak, aby poniższe formuły były 

wartościowane na 1 

(p  q)
(p  q)
(q  q)  (p  q)

3. Udowodnij następujące równoważności 

 

 

 

 

 

ZBIORY

Zbiór liczb naturalnych: 1, 2, 3 , 4 , 5 , ...

N = {1, 2, 3 , 4 , 5 , ...}

Zbiór liczb wmiernych: 1/2, 2/3 , 4/4 , 5/6 , ... W = {1/2, 2/3 , 4/4, 

5/6 , ...}

Zbiór liczb niewmiernych: 2, , e ,... -

 W

Zbiór liczb rzeczywistych 

-

R

Zbiór liczb całkowitych 

-

C

N  C  W  R ;

 W  C

;

 W  R

        Suma

A  B = C  ;

C = {c  A  c  B}

        Iloczyn

A  B = C  ;

C = {c  A  c  B}

        Różnica

A \ B = C  ;

C = {c  A  c  B}

Różnica symetryczna
         A  B = C 

;  C = { c  A  B  c  A  B } = { c  A \ B  c 

 B \ A }

Zbiór pusty  

A =     a [a  A ]

Inkluzja dwóch zbiorów

( A  B )  a [ a  A   b  B ]

Zbiory liczbowe
N - zbiór liczb naturalnych N ={1,2,3,4,}
Z - zbiór liczb całkowitych Z 
={0,±1,±2,±3,±4,}
Q - zbiór liczb wymiernych Q=
  
  
: m Z, n Z, n 0
n
m
R – zbiór liczb rzeczywistych
Rys. 1.1 Relacje midzy zbiorami N, Z, Q, R
N Ì Z Ì Q Ì R

A

A’

1

a  A  a 1  a  A

A’ = 1 \ A

N  W

;     (W  N )

;

W  W =  ;

N \ W = 

Zbiór potęgowy P(S) zbioru S – zbiór wszystkich podzbiorów 

zbioru S.

S={a,b} ; P(S) = { , {a}, {b} , {a,b}}

|S| = 2 ,

|P(S)| = 2

n

|P()| = ??? ,

|P({1})| = ???

Przestrzeń  (zbiór pełny)  1

Dopełnienie A’ zbioru A przestrzeni  1

{

5n | n  N}     =   {5, 10, 15,…}

{4n + 3 | n N}  =   {           }

1.Wypisać po kilka elementów z następujących zbiorów: 

{nN: n jest podzielna przez 5} 

{2

n

 : n  N }

{1/n : n=1,2,3,4} 

{ x  R : x=k/n oraz k  {1,2} i n  {1,2,4,8} } 

2. Jaka jest liczba elementów podanych poniżej zbiorów? 

{n  N : n

2 

= 2}, 

{x  Q: x

2 

= 2},  {x  R: x

2 

= 2} 

{n  N: n jest liczbą pierwszą , niewiększą niż 10} 

{n  N: n jest potęgą 2} 

{x  Z: |x| <10}, {x  R: |x| <10} 

         {n  N : n jest liczbą parzystą i liczbą} 

3. 

Niech U={n  N: n < 20} będzie ustalonym uniwersum i niech A i B 

będą jego    podzbiorami takimi, że A= {2n+1: n  N i n < 6},

 B = 

{3n+2: n  N i n < 6}. 

Wyznacz elementy zbiorów  A  B,  A  B,  A\B,  B\A, 

A \ B  A  B

A

B

1. A  B = 


A \ B = A

,   A  B = 

,    A  

2. A  
B

    A \ B =  ,   A  B = A

,        A

A \ B =

,



,   A  B =

 

A

B

B

3. A  B  

A

Sprawdź:

A  B  A  B

A  B  A  B

Niech A = {1,2,3,4,8,16}, B = {2,4,6,8,10} ,  C = 

{1,3,7,15}. 

Wyznacz:

A \ C 

B  (C  B)

A  B

(B  A)  (A  C)

A  B 

`

C \ (B \ A)

B  C

A  (B  C)

Iloczyn kartezjański zbiorów ( produkt )

Dla dowolnych zbiorów A, B iloczynem kartezjańskim nazywamy 
zbiór
wszystkich par uporządkowanych (a, b) takich, że a  A i b  B

A  B={(a,b) : a  A  b  B

}

Produkt dowolnej skończonej rodziny zbiorów

S

1 

 S

2 

 S

3 

... S

n

 = { (s

1

, s

2

, s

3

, ..., s

n

) : s

k

 S

k

 dla k = 

1, 2, 3, ..., n }

PRZYKŁAD

{a}  {b} = {(a,b)}

{3}  {a,b} = {(3,a), (3,b)}

{1,2}  {a,b} = {(1,a), (1,b), (2,a), (2,b)}

Wprowadzimy oznaczenia dla pewnych szczególnych 
podzbiorów zbioru R, nazywanych przedziałami. 

Dla a,b  R gdzie a < b, określamy:

{ x  R : a < x < b } = (a,b) 

– przedział otwarty

{ x  R : a   x   b } = [a,b] 

– przedział domknięty

{ x  R : a   x < b } = [a,b) 

– przedział 

prawostronnie otwarty

{ x  R : a < x   b } = (a,b] 

– przedział 

prawostronnie domknięty

Alfabet  to skończony zbiór S , którego elementami są symbole zwane 
literami
alfabetu S .

Słowem danego alfabetu S nazywamy dowolny skończony ciąg liter 
tego zbioru S

Zbiór wszystkich słów zbudowanych z elementów zbioru S oznaczamy 
S *.
S* jest zbiorem nieskończonym.

Dowolny podzbiór zbioru S* nazywamy językiem nad alfabetem S .

Słowo puste  -     (ciąg nie zawierający liter );     analogia do 
zbioru pustego.

PRZYKŁAD

Jeżeli  = { a,b }, to S *= {, a, b, aa, bb, abb, aaa, babb, 

... }

Jeżeli  = { a }, to S *= {, a, aa, aaa, aaaa, ... }

Jeżeli  = { 0, 1, 2} , to *= {, 0, 1, 2, 00, 01, 02, 11, 12, 

20, 21, 22, 000, ... }

Jeżeli  = { a,b } i dł(w) oznacza długość słowa w zbiorze 

*, to

A = { w   *: dł(w) = 2 } = { aa, ab, bb, 

ba }

Wnioskowanie

Modus ponens

a  b

a, a  b

                                                                           b

Zasada rezolucji

(a  b  b  c)  (a  c)

a  b, b  c

b  c

Objawy        Diagnoza                   
Terapia

Dowody           Wyrok                        Kara

A i B przyprostokątne,    IF A i B przyprostokątne  THEN

C

2

 = A

2

 + B

2

p – dzisiaj jest niedziela
q – mam wolny dzień
r – jadę na ryby

Jeżeli prawdą jest p  q , oraz jeżeli prawdą jest, że q   
r,

Zatem:

w każdą niedzielę p  

                   bo              p, p  q 

      q 

q , q   r
        r

 

jestem na rybach  r. 

C

2

 = A

2

 + B

2

Fakty: a, b

Baza 

wiedzy:

R1. a  c  d

R2. a  b  c

R3. b    d    g

R4. c    g    h

h? 

g

d

R3

a

b

R2 c 

h

R1

R4

Udowodnij że nie jesteś 
wielbłądem!

R

1 

: a  b   c     d

R

2 

: d  c     f

R

3 

: f  d   x    h

h? 

Spójność:  (a,L)   (c,3)  (d,H) ,  (~(a,H))   (c,3)  (d,H)

Niesprzeczność: (a,L)   (c,3)  (d,H) , 

(a,L)   (c,3)  (d,L)

Pochłanianie: 

(a,L)   (c,3)  (d,H) ,  (a,L)  (b,D)  (c,3)  

(d,H)

          

 (c,3)  (d,H) ,  (a,L)  (c,3)  (d,H)

Zapętlenie:  (a,L)    (c,5)    (d,H)  ,  (d,H)    (f,2)  ,  (f,2)    (g,4)   

(c,5)

(a, L)

(d, H)

(f, 2)

(c, 5)

(g, 4)

Początkowa baza

 faktów: e, f

Wnioskowanie: c?

Nr kroku

Ewolucja

Bazy faktów

Reguły

Baza reguł

1

2

3

4

5

3

2

1

Baza faktów końcowa: a, b, c, d, e, f  

Fakt c wynika z faktów: e, f

Baza faktów: BF = {e,f} 

Baza reguł: BR = {

}

e

f

d

b

a

c

R

3

R

1

R

5

R

2

Przykłady

P(Janek,Zosia) = [Janek jest bratem Zosi] ,   P(V,x,y,z) = [V 

= x*y*z]

xR [x + 0 = x] , xN [x = x*x] , xN [x < 0] , xR [x < 

0] , 

x  zbiór kotów [x pije mleko] , x  zbiór szpaków [x jest 

ptakiem]

x  zbiór dzieci y  zbiór rodziców [x  jest dzieckiem y] 

Rachunek predykatów

 jeden talerz  student

,

 student  jeden talerz

Niech P(x) = [x = x*x] która z tez jest prawdziwa:

 

 x  R P(x) 

, 

 x  R P(x)

 x {0,1} [x  x  0] 

,

x {0,1} [x  x  1]

Predykaty

P(x) 

         P(x) = [ x = 3] , P(x) = [Q(x) U(x)] , [pije mleko] , 

[jest zielone], 

P(x

1

,x

2

,...,x

n

)  P(x,y,z) = [x + y = z] , P(x,y) = [x > y] , [jest 

dzieckiem],

Bardziej formalnie:

Predykatem  lub  funkcją  zdaniową  nazywamy  wyrażenie  W(x),  w  którym 
występuje zmienna x i które staje się zdaniem prawdziwym lub fałszywym, gdy w 
miejsce x podstawimy wartość zmiennej x.

Rachunek  predykatów  został  stworzony  poprzez  rozszerzenie  rachunku  zdań  o 
kwantyfikatory ogólny i szczególny: „dla każdego”  oraz „istnieje takie, że” .

Rachunek  predykatów  przyjmuje  założenie  o  monotoniczności  logiki.  Oznacza  to, 
że  jeżeli  po  przyjęciu  zbioru  aksjomatów  wykazywana  hipoteza  jest  poprawna 
(czyli  jest  twierdzeniem),  to  po  dodaniu  nowego  aksjomatu  wynik  ten  nie  może 
ulec zmianie. Założenie to nie pozwala na uwzględnienie wyjątków powodujących, 
że  zbiór  aksjomatów  staje  się  zbiorem  sprzecznym,  co  w  niektórych  przypadkach 
ogranicza możliwość zastosowania omawianego rachunku.

Przykład 

 x[jest_ptakiem(x)  potrafi_latac(x)]

jest_ptakiem(struś)

¬ potrafi_latac(struś)

Twierdzenie „dla wszystkich x, jeżeli x jest ptakiem, to x potrafi latać” jest nie do 
końca poprawne ponieważ występują pewne odstępstwa od niego.
Otóż,  struś  jest  ptakiem  i  nie  potrafi  latać.  Bazę  wiedzy  należałoby  uzupełnić  o 
nowy aksjomat:
  ¬  potrafi_latac(struś).        Uwzględnianiem  takich  przypadków  zajmuje  się  logika 
niemonotoniczna.

Sprawdzanie prawdziwości 

x P(x)  - „jeden zaprzecza wszystkiemu“

x P(x)   - „jeden wystarcza“

( x P(x))   x [P(x)]

Przykład

( x  R [x < x + 1]   x  R [x  x + 1]

( y Q(y))   y [Q(y)]

Przykład

             ( x  y [y > x])   x ( y [y > x])   x  y ( [y > x])   x  

y [y  x]]

Niech U’ = {1,2,3} , U” = {4,5,6,7}   sprawdź 
prawdziwość: 

 X  U’  y  U” [y > x]

 x  U’  y  U” [y > x]

 X  U’  y  U” [y > x]

 x  U’  y  U” [y > x]

! xR [x*6 = 0]

 x  R  y R ! z  R [x + y = z]

 x {1,2,3} P(x)  P(1)  P(2)   P(3) ,

(x P(x)   x P(x))    (x P(x)   x Q(x))

       x P(x)   x P(x)    x Q(x)       x P(x)   x P(x) 

    x P(x)   

x Q(x)

0

0

0

1

1

0

0

1

1

1

0

1

0

1

0

0

1

1

1

1

1

0

0

1

0

1

1

1

0

( x P(x)    x P(x))     ( x P(x)    x Q(x))

    ( A   A )

   ( B    C )

   ( A   A )

   (B    C )

1



?????

( x P(x)    x P(x))      ( x P(x)    x Q(x))

Sprawdź

Twierdzenie o dedukcji (zasada rezolucji) 

Jeżeli formuły {A1, A2,…, An} nie są sprzeczne, to formuła B jest 

ich  konkluzją  (tzn.  wynika  inferencyjnie  z  formuł  A1,  A2,…,  An) 

wtedy  i  tylko  wtedy,  gdy  formuły  {  A1,A2,…,An,  ¬B}  są 

sprzeczne.

Każdy człowiek jest śmiertelny.

 x : Cz(x)  Śm(x)

Marek jest człowiekiem.

Cz(M)

Czy Marek jest śmiertelny?

Śm(M)?

 x : Cz(x)  Śm(x)

Cz(x)   Śm(x)

Cz(M)

   Cz(M)

Śm(M)?

Śm(M)

Cz(x)    Śm(x)       ,   Cz(M)

Śm(M)

Śm(M)  ,  Śm(M)



Cz(x)  Śm(x)

,       Cz(M)

Śm(M)

Śm(M)

x:=M



Zasada rezolucji

(a  b  b  c)  (a  c)

a  b, b  c

a  c

Każdy człowiek jest śmiertelny.

 x : Cz(x)  Śm(x)

Marek nie jest człowiekiem.

Cz(M)

Czy Marek jest śmiertelny?

Śm(M)?

 x : Cz(x)  Śm(x)

Cz(x)   Śm(x)

Cz(M)

Cz(M)

  Śm(M)?

 

Śm(M)

Cz(x)    Śm(x)

,    Cz(M)

Cz(M)  Śm(M)    ,  Śm(M)

Cz(x)  Śm(x)

,  Cz(M)

x:=M

Cz(M)  Śm(M)

Cz(M)  Śm(M) Śm(M)

Cz(M) 

Cz(M) 

Według kodeksu cywilnego jeżeli x jest mężem y to y jest żoną x. 

Korzystając z

tego  faktu  oraz  przyjmując,  że  x  to  Linda,  a  y  to  Bil,  należy 

przekonać Bila, że Linda jest jednak jego żoną, czemu on gorąco 

zaprzecza. W zapisie predykatowym mamy zatem:

Żona(Linda, Bil)

¬Żona(x,y)  Mąż(y,x)

¬Mąż(Bil, Linda)

Rozważmy system ekspertowy, którego baza wiedzy zawiera m reguł, 

a maksymalna liczba faktów wynosi n.

Przyjmijmy najgorszy przypadek, w którym baza wiedzy zawiera tylko 

jeden fakt. Oznacza to, że należy wygenerować pozostałych n-1 faktów. 
W przeszukiwaniu bazy reguł należy sprawdzać wszystkie kombinacje 

faktów każdorazowo rozszerzonej bazy faktów. 

Oznacza to, że każda z n reguł musi być „sprawdzona” kolejno dla 

kombinacji 1 po 1, 2 po 1 i 2 po 2, 3 po 1 i 3 po 2 oraz 3 po 3, aż do 

kombinacji  z  n-1 po 1, itd.

Tak więc sprawdzeniami objętych jest m2

1

 + m2

2 

+…+m2

n-1  

przypadków. Wykorzystywana jest tutaj zależność:

  Niech  m  =  500  reguł  oraz  n  =  101  faktów.  Oznacza  to  konieczność 

dokonania ok. 2

100

 sprawdzeń. 

Przyjmując,  że  rok  ma  31  536  000  sekund,  tzn.  ok.  310

7

  sekund, 

zakładając  wykorzystanie  komputera  umożliwiającego  wykonywanie 

1000 sprawdzeń na jedną nanosekundę, a zatem posiadając możliwość 

dokonywania rocznie

 3 10

7

 10

9 

10

3

 = 3 10

19

 sprawdzeń, 

samo  sprawdzanie  (wyszukiwanie)  postawionej  hipotezy  w  najgorszym 

przypadku trwałoby 10

30

/(3 10

19

) 

 

10

11

 lat. 

Zauważmy bowiem, że 2

100 

 10

30

, 

ponieważ 2

10 

 10

3

, 

więc 2

10 

2

10 

2

10

... 2

10

  10

3 

10

3

10

3

... 10

3

 = 10

310

  10

30

.

10

10

x{P(x)  {y[P(y)  P(f(x,y))]  ~y[Q(x,y)  P(y)}}

Krok 1 x{~P(x)  {y[~P(y)  P((f(x,y))]  ~y[~Q(x,y)  

P(y)]}}

Krok 2 x{~P(x)  {y[~P(y)  P((f(x,y))]  y[Q(x,y)  

~P(y)]}}

Krok 3 

x{~P(x)  {y[~P(y)  P((f(x,y))]  z[Q(x,z)  

~P(z)]}}

Krok 4 x{~P(x)  {y[~P(y)  P((f(x,y))]  [Q(x,z)  

~P(z)]}}

Krok 5 x y{~P(x)  {[~P(y)  P((f(x,y))]  [Q(x,z)  

~P(z)]}}

Krok 6 i 7

[~P(x)  ~P(y)  P((f(x,y))]  [~P(x)  Q((f(x,g(x))]  [~P(x)  

~P(g(x))]
 

A  (B  C)  (D  E)  (A  B  C)  (A  D)  (A  E)

Krok 8 

~P(x) ∨ ~P(y) ∨ P((f(x,y))  
~P(x) ∨ Q((f(x,g(x))
~P(x)∨ ~P(g(x))

Krok 9 

~P(x

1

) ∨ ~P(y

1

) ∨ P((f(x

1

,y

1

))

~P(x

2

)∨ Q((f(x

2

,g(x

2

))

~P(x

3 

)∨ ~P(g(x

3

))

Dana jest formuła postaci:

 x[P(x) ( y[P(y)  P(f(x,y))]  ¬  y[Q(x,y)  P(y)])]

1. Podczas pierwszego kroku usuniemy symbol implikacji, 

wykorzystując znane przekształcenie A B  ( ¬ A)  B.

 x[ ¬ P(x)  ( y[ ¬ P(y)  P(f(x,y))]  ¬  y[ ¬ Q(x,y)  P(y)])]

2. W tym kroku przemieszczamy wszystkie zewnętrzne znaki negacji 

do wewnątrz w celu przypisania ich wyłącznie formułom atomowym. W 
przypadku kwantyfikatora ogólnego korzystamy z własności   ¬  x[A]   
x[ ¬ A].

  x[ ¬ P(x)  (  y[ ¬ P(y)  P(f(x,y))]    y[ ¬ ( ¬ Q(x,y)  

P(y))])]

Korzystając z prawa de Morgana ¬ (A  B)  ( ¬ A)   ( ¬ B) 

otrzymujemy

  x[ ¬ P(x)  ( y[ ¬ P(y)  P(f(x,y))]    y[Q(x,y)   ¬ P(y)])]

3. Eliminujemy kwantyfikator szczegółowy  poprzez wprowadzenie 
odpowiednich stałych w miejsce zmiennych będących w zasięgu 
kwantyfikatora.

 x[ ¬ P(x)  ( y[ ¬ P(y)  P(f(x,y))]  z[Q(x,z)  ¬ P(z)])]

Następnie usuwamy kwantyfikator szczegółowy . Powołując się na 
zasadę: Jeżeli kwantyfikator szczegółowy jest w zasięgu kwantyfikatora 
ogólnego to należy wprowadzić funkcję uzależnioną od zmiennej 
kwantyfikatora ogólnego.
wstawiamy funkcję g(x) w miejsce zmiennej z

 x[ ¬ P(x)  ( y[ ¬ P(y)  P(f(x,y))]  (Q(x,g(x))  ¬ P(g(x)))]

4. W tym kroku przemieszczamy kwantyfikator ogólny  na zewnątrz formuły 
złożonej.
 x y[ ¬ P(x)  (( ¬ P(y)  P(f(x,y)))  (Q(x,g(x))  ¬ P(g(x)))]
Korzystając z zasady: Jeżeli wszystkie zmienne są w zasięgu kwantyfikatora 
to możemy z niego zrezygnować pamiętając, że każda zmienna w formule 
została wyprowadzona za pomocą kwantyfikatora ogólnego.
pozbywamy się kwantyfikatorów ogólnych

¬ P(x)  (( ¬ P(y)  P(f(x,y)))  (Q(x,g(x))  ¬ P(g(x)))

5. W tym miejscu należy tak przekształcić formułę, aby funktory 
koniunkcji były zewnętrzne względem funktorów alternatywy. 
Korzystamy z własności A  (B  C)  (A  B)  (A  C)

{ ¬ P(x)  ¬ P(y)  P(f(x,y))}  [{ ¬ P(x)  Q(x,g(x))}  { ¬ P(x) 

 ¬ P(g(x)}]

6. Z ostatniego wyrażenia po usunięciu symbolu koniunkcji otrzymujemy 
postać klauzulową

i) ¬ P(x)  ¬ P(y)  P(f(x,y))

ii) ¬ P(x)  Q(x,g(x))

iii) ¬ P(x)  ¬ P(g(x)

Wykład 2

Elementy teorii liczb

•funkcje całkowitoliczbowe: powała i podłoga,

•podzielność liczb – algorytm Euklidesa,

•równanie diofantyczne,

•NWD, NWW, operator modulo,

•liczby pierwsze i rozkład liczb na czynniki, liczby doskonałe,

Ciągi - funkcje zmiennej naturalnej

a

n

 = n

;

 a

1

 = 1 , a

2

 = 2 , a

3

 = 3

 ,

 . . . 

a

n

 = n

2

;

a

n

 = 2

n  

,

a

n

 = n!

Funkcje całkowitoliczbowe

Podłoga

xR 

,    x  = max{nC : n x}   

  = 3;

-  = -4

Powała

xR 

,     x  = min{nC : n x}   

  = 4;

  = -3

Funkcje całkowitoliczbowe

Podłoga

xR 

,   x  = max{nC : n x}   

  = 3;

-  = -4

Powała

xR 

,   x  = min{nC : n x}   

  = 4;

  = -3

1   x = x  x = x  xC

;

x  x  x

2   x - x = 1   xR 

3   - x = - x 

;

x = - - x

 4   x = n   n  x < n+1

 5   x = n   x – 1 < n  x

 6   x = n  n – 1 < x  n

 7   x = n  x  n < x+1

Dane  n  N  

Ile potrzeba zarezerwować bitów pamięci dla zapisania  n  w komputerze?

         (2002)

10

 = 2 10

3

 + 0 10

2

 + 0 10

1

 + 2 10

0

(101001)

2

 = 1 2

5 

+ 0 2

4

 + 1 2

3

 + 0 2

2

 + 0 2

1

  + 1 2

0

    32                  8                               1

2

5 

= 32  41 < 64 = 2

6

       Zatem liczba   n  zapisana  na  m  bitach spełnia nierówność

2

m-1  

    n     <      2

m 

2

m-1  

     n     <     2

m 

   / log

2

            x = n   n             x       <     n+1

     m-1          log

2

n  <      m

log

2

n = m-1

a 

zatem

m = log

2

n +1

Przykład

n = 7

;

log

2

7 = 2 (bo 2

2 

 = 4  a  2

3 

 = 8 ) zatem   m  = 2 + 1 = 

3

Właściwość: 4    x = n   n  x <n+1

 

m-1   log

2

n <     m

Algorytm  Euklidesa 

(por.:  Sysło  M.M.,  Algorytmy,  WSiP,  Warszawa,  1997,  Sysło  M., 

Piramidy, szyszki I inne konstrukcje algorytmiczne. WsiP, Warszawa, 1998.)

Liczba    k    jest  największym  wspólnym  dzielnikiem    m    i    n,    tzn.  NWD(m,n),  jeśli 

dzieli  m  oraz  n  

i jest największą liczba o tej właściwości.

Algorytm Euklidesa znajduje NWD(m,n).

NWD(n,m) = max{kN : k dzieli n   k dzieli  m }

NWD(48,6) =  6  ,   NWD(26,15) = 1

NWD(n,m) 

Niech  n  m

n/m = q + r        ; n = q m  + r         ;                r = n - q m  ;    0   r    m-1

NWD(n,m)  =  NWD(m,r)

NWD(24,12)   ; 24 = 2 x 12  +  0  ; NWD(12,0) 

NWD(37,35)   ; 37 = 1 x 35  +  2   ; NWD(35,2) = NWD(17,1) 

  

NWD(n,m) 

Niech  n  m

n/m = q + r        ; n = q m  + r         ;                r = n - q m  ;    0   r    m-1

NWD(n,m)  =  NWD(m,r)

; NWD(37,35)   ;  37 = 1 x 35   +   2

NWD(721,448)  

n

= q  x  m + r

721 =

1 x 448 +  273

448 =

1 x 273 +

175

273 =

1 x 175 +

98

175 =

1 x 98 +

77

98 =

1 x 77 +

21

77 =

3 x 21 +

14

21 =

1 x 14 +

7

14 =

2 x 7 

+  0

NWD(721,448) = 7

NWD(35,2)    ;  35 = 2 x 17    +   1        ;     
NWD(17,1) 

Równania diofantyczne

A

2 

 

 + B

2

   = C

2 

3

2 

 

 + 4

2

   = 5

2  

 trójkaty pitagorejskie

 

                                          

    

A

n 

 

 + B

n

  = C

n

Przykład

Dane  są  naczynia  o  pojemności    m    i    n.    Czy  korzystając  z  nich    można 

napełnić zbiornik o pojemności  k  ? Jeżeli tak to w jaki sposób? 

Niech m, n  N  ,   x, y  Z  ;

 k = x m  + y n 

5 x  + 7 y  = 3

;

 15 = 4 x  + 10 y     ;

 3 = 6 x  + 18 y

 

NWD(7,5) = 1

 NWD(10,4) = 2

 NWD(18,6) =6

Rozwiązanie istnieje gdy  k  jest wielokrotnością   NWD(m,n).

15 = 4 x  + 10 y

nie ma rozwiązania, bo  2 = NWD(4,10),

3 = 5 x  + 7 y  

rozwiązanie istnieje, bo  1 = NWD(5,7).

Najmniejsza wspólna wielokrotność:  

NWW(m,n)

NWW(m,n) = min{k: k jest podzielne przez  m    k jest podzielne przez m}

NWW(12,9) = 3   bo ;

12 = 3 3 2

;

9 = 3 3

            m n

12 9

NWW(12,9)    = ----------------   = ------   = 36
                          NWD(12,9)

    3

Liczby pierwsze

nN jest liczbą pierwszą jeśli  n  jest podzielne tylko przez  1  i  n.

Liczb pierwszych jest nieskończenie wiele.

Każdą liczbę naturalną można przedstawić w postaci

           

 H = 2

l1

 3

l3

 5

l5

 7

l7

 11

l11

 13

l13

 .........

l

1

, l

3

 , l

5

 , . ..   – nieujemne liczby całkowite

Niech    p

1

, p

2

, p

3

, ..., p

k

  wszystkie liczby pierwsze

Euler

M = p

1

* p

2

* p

3

* ...* (p

k

  + 1)  - liczba pierwsza

O

1

 = 2 

O

2

 = 2 +1 = 3

O

3

 = 2 3 +1 = 7

O

4

 = 2 3 5 + 1 = 43

ale  O

4

 = 2 3 5 43 + 1 = 1807 = 13*139

2

k

Fermat

L

k

 = 2       +   1

k = 1, 2 , 3 , 4  - liczba pierwsza

ale dla k = 5 nie jest liczbą pierwszą

n mod m , Mod(n,m) ,  MOD(n,m)       

-          reszta z dzielenia n 

przez m

7 mod 3 = 1

;

1 mod 7 = 1

;

7 mod 7 = 0

n  div  m  ,  Div(n,m)    ,    DIV(n,m)     

            - 

całkowita    część 

wyniku dzielenia

7 div 3 = 2 ;

1 div 7 = 0 ;

7 div 7 = 1

Liczba doskonała

Liczba  doskonała  jest  liczbą  naturalną  gdy  jest  równa  sumie 

wszystkich swoich dzielników właściwych, tzn. takich które są 

od niej mniejsze.

6 = 1 + 2 + 3

28 = 1 + 2 + 4 + 7 + 14

Wykład 3

Elementy kombinatoryki

• zasada gołębnika, 

• zasada włączania i wyłączania, 

• permutacje, kombinacje, podziały liczb,

• algorytmy generowania obiektów kombinatorycznych,

Zasada Gołębnika

(Zasada szufladkowa DIRICHLET’A)

Niech:

m  obiektów oraz   n  pudełek

jeżeli  n < m, to przynajmniej dwa obiekty są w jednym pudełku

Niech   |A| - moc zbioru A ; 

np. A = {a,b,c,d,e} ; |A| = 5

Jeżeli skończony zbiór  S  jest podzielony na  k  zbiorów, to co najmniej jeden z tych 

zbiorów  ma |S|/k  lub więcej elementów.

Zastosowania:

W każdej grupie  n  osób są przynajmniej  2  osoby, które znają tę samą liczbę 

osób.

Dany zbiór A = {

a

1

, a

2

,...,a

9

} taki, że suma jego elementów  = 90.

a)   trzy takie elementy zbioru A, że ich suma  30.

b)   cztery takie elementy zbioru A, że ich suma  40.

a)

(a

1

 + a

2

 + a

3

) 

+          (a

4

 + a

5

 + a

6

)         +    (a

7

 + a

8

 + a

9

) = 

90

   < 30

 < 30

 > 30

   < 30

 = 30

 > 30

b

)

a

1

    

a

2

a

3

a

4

a

5

a

6

a

7

a

8

a

9

a

2

    

a

3

a

4

a

5

a

6

a

7

a

8

a

9

a

1

a

3

    

a

4

a

5

a

6

a

7

a

8

a

9

a

1

a

2

a

4

    

a

5

a

6

a

7

a

8

a

9

a

1

a

2

a

3

4 x 90 = 360   zatem  360/9 = 40

a

1 

+ a

2 

+ a

3 

+ a

4

 lub  a

2 

+ a

3 

+ a

4 

+ a

5

 lub  .......        40

Zasada włączania i wyłączania

Należy  „włączyć”  (dodać  do  siebie  liczności  poszczególnych  zbiorów), 

następnie  „wyłączyć”  (odjąć  liczność  przecięć  po  dwa  zbiory),  potem 

„włączyć” (dodać liczności wszystkich przecięć po trzy zbiory), itd.

| A  B  C |  = |A| + |B| + |C| - |A  B| - |A  C| - |B  C| + |A 
 B  B|

Ilustracja

A = {a,b} ;

B = {1,2}

;

C = {x,y}

|A  B  C |  =  6 = 2 + 2 + 2 – 0 – 0 – 0 + 0 = 6

A

B

C

Zastosowanie

Ile jest liczb między 1  a  999 nie podzielnych, ani przez 5, ani przez 7?

/
7

/
5

1, 2, ... , 999

999 - „/5”  -  „/7” +  „/5 7”  =  999  -   999/5   -  999/7  +  
999/35  =
  

=  999  -  199  - 142  + 28 = 686

Ile liczb naturalnych ze zbioru S = {1,2,3,...,1000} dzieli się przez 

 3  lub

5  lub przez obie te liczby jednocześnie?

Niech D

3

 = {nS : n dzieli się przez 3}

  D

5

 = {nS : n dzieli się przez 5}

   D

3 



 

D

5

 = {nS : n dzieli się przez 15}

D

3

 = {3mS : 1  m  333}

| D

3 

| 

=  1000/3  = 333

D

5

 = {5mS : 1  m  200}

| D

5 

| 

=  1000/5  = 200

| D

3 



 

D

5 

| =  1000/15  = 66

Zatem

| D

3

  D

5

| =  | D

3 

| + | D

5 

| - | D

3 



 

D

5 

| = 333 + 200 – 66 = 467

Permutacje

 
- funkcje na zbiorze liczb naturalnych {a

1

,a

2

, ...,a

n

}

Liczba permutacji

P

n

 = n! = n (n-1) (n-2) ...1 = 1 2 3 ...n

0! = 1

{A , B , C}

   A           B                
          C

    B               C               A       C          
     A               B
    C               B               C       A          
     B               A

Urzędnik  zapomniał  hasła  do  swoje  aktówki.  Hasło  jest  liczbą  7  cyfrową  złożoną  z 

cyfr od 1 do 7. Cyfry w haśle nie powtarzają się. (Ostatnie 3 cyfry wybierane są ze 

zbioru  {3,4,7})  Ile  możliwości  w  najgorszym  przypadku  trzeba  sprawdzić  aby 

otworzyć zamek?

{3,4,7}     -   (3,4,7) , (4,7,3) , (7,4,3) , (3,7,4) , (4,3,7) , (7,3,4)

Wariacje

- bez powtórzeń

Dany zbiór A = {a

1

,a

2

, ...,a

n

}. 

Wariacja – k-elementowy ciąg nie powtarzających się obiektów zbioru A.

Liczba k-elementowych wariacji zbioru A,  n = |A| .

V

n

k 

= n (n-1) (n-2) ... (n – k+1))

  n!

n (n-1) (n-2) ...(n-k+1) (n- k) (n-k-1)..2 1

V

n

k 

=

 =

(n-k)!

(n-k) (n-k-1) ...2 1

= n(n-1)...(n-k+1)

A = {a,b,c}

; k = 2 ;

(a,b) , (a,c) , (b,c) , (b,a) , (c,a) , (c,b)

W urnie jest 10 kul ponumerowanych od  1  do  10. Losujemy kolejno i bez zwrotu  5  

kul.  Po  każdym  losowaniu  zapisujemy  jej  numer.  Ile  jest  wszystkich  możliwych 

wyników losowania?

V

n

k 

= n (n-1) (n-2) ... (n – (k-1)) ; V

10

5 

= 10 9 8 7 6

Wariacje

- z powtórzeniami

Rzucamy  10  razy monetą. Ile jest możliwych wyników tego 

doświadczenia?

Liczba k- elementowych wariacji z powtórzeniami 

W

n

k 

= n n n n ...n = n

k

  k

 

{O,R} , {O,R},..., {O,R}  

2

n

Na ile sposobów można rozmieścić  2  kule (czarna i białą) w  3  szufladach?

I

II

III

0

b

c

0

c

b

0

c-b 0

0

0

c-b

b

c

0

c

b

0

c-b 0

0

b

0

c

c

0

b

Kombinacje

Dany zbiór A = {a

1

,a

2

, ...,a

n

}. 

Kombinacja – k-elementowy podzbiór zbioru A.

Liczba k-elementowych kombinacji ze zbioru A,  n = |A| .

n!  n

    

    C

n

k       

=                = 

      k!(n-k)!      k

     3         3!

   =              =    3     ,      {3,2,1}

, k = 2

;    (1,2) , (1,3) , 

(2,3)
     2       2! 1!

Łatwo zauważyć, że:

n!

V

n

k 

=                  = k! C

n

k

(n-k)!

Na  ile  sposobów  można  wybrać  8    kart  z  talii  24  kart  jeżeli  kolejność  nie 

jest ważna? 

Ile z tych układów 8- kartowych zawiera  2  asy.

C

20

6 

C

4

2

Na ile sposobów można rozmieścić  6  osób  w  3  różnych pokojach  2  osobowych?

C

2

6 

C

2

4 

C

2

2

Własności kombinacji

a)

n

 n

=

k

n - k

b)

n

 n

=

0

 n 

c)

n

 n

=

1

n - 1

Trójkat Pascal’a

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

Dwumian Newton’a

n

n

n

      n

(a + b)

n 

=  

      a

n 

 +          a

n-1 

b   +    ...   +              a b

n-1     

+          b

n

0

1

                  n-1

       n

  

n     

n

(a +b)

n 

=          a

n-i

 b

i

 

 i=0   

i

Ciąg Fibonacciego Leonardo Fibonacci (1175 - 1250)).

1,  1,  2,  3,  5,  8,  13,  21,  34,  55,  89,  144,  233,  377,  610,  987,  1597, 

2584, 4181,... 

               F

1

  = 1

;

F

2

 = 1 ;

F

n

 = F

n-1

 + F

n-2 

 dla n > 2

   Pary

   1                  1                  2                  3                 5                8

 
   Okresy       1                  2                  3                  4                 5                
6

M

M

M

M

M

M

M

R

R

R

R

R

R

R
R

R

R

R

M

R

Złota 

proporcja

 

2/1  = 2  ; 3/2 =  1.5 ;  5/3 =  1.667 ; 8/5 = 1.6 ; 13/8 = 1.625    
21/13 = 1.615 ; 34/21 = 1.619 ; 55/34 = 1.618  . . .

≈ 1,618033989

  

współczynnik „złotych proporcji”

rozwiązanie równania: 

a

x

a-x

a              x

a

2

a  

  =  

;

a

2 

– a x  = x

2 

                         -      - 1 = 0

x          a – x

x

2 

x

a
x

=

front Partenonu

        F

n+1

                         5  + 1

    =

= 

             = 1,618033989.....

              F

n

 

2

1             1  + 5   

      1  - 5

            F

n

 =

      5           2

                 2

n

n

 
a

x

a –
x 

Wykład 4

Elementy kombinatoryki 

• algorytmy i zależności rekurencyjne,
• symbol Newtona, trójkąt Pascal’a
• rozwiązywanie zależności rekurencyjnych – przez podstawianie i za pomocą 

równania charakterystycznego, 

• kongruencje, schemat Hornera

(por.: Sysło M., Piramidy, szyszki i inne konstrukcje algorytmiczne. WSiP, Warszawa, 1998. 

Ross K.A., Wright C.R.B., Matematyka dyskretna, PWN, Warszawa 1996.)

Algorytmy i zależności rekurencyjne

Wieża w Hanoi 

2

n

 - 1

Trzy kręgi 

wymagają  7 przełożeń       bo 2

3

 – 1 = 7

Trzy kręgi  wymagają  7 przełożeń bo 2

3

 – 1 = 7

Jeden krąg - jedno przełożenie

2

1

 - 1

Dwa kręgi - trzy przełożenia

2

2

 - 1

Zależności rekurencyjne

1 , -3 , - 27 , -185 , 

S

n

 = 6S

n-1

 – 9S

n-2

  , n  2   , S

o

 = 1  , s

1

 = -3

S

n

 = 3

n

  - 2n3

n 

    , n  N

0

Sprawdzenie:

n

S

n

 = 6S

n-1

 – 9S

n-2

  

S

n

 = 3

n

  - 2n3

n 

    

0

           1

3

0

  - 2*0*3

0  

=1    

1

          -3

3

1

  - 2*1*3

1 

= -3

  

2

6*(-3)– 9*1      =   -27  

3

2

  - 2*2*3

2 

= -27

  

3

6*(-27)– 9*(-3) =  -185

3

3

  - 2*3*3

3 

= -185

  

4

    . . . 

        . . . 

Trójkat Pascal’a

 n = 4

{a,b,c,d} 

k = 0



1

k = 1

{a}, {b}, {c}, {d}

4

k = 2

{a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}

6

k = 3

{a,b,c}, {a,b,d},{a,c,d}, {b,c,d}

4

k = 4

{a,b,c,d}

1

n!                          n

                                                 C

n

k     

=                         =  

         k!(n-k)!                     k

1

1

1

1

2

1

   1

3

3

1

1

4

6

4

1

 (symbol Newton’a)

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

n

     n                                n        n

(a – b)

n 

=  

      a

n 

      +             a

n-1 

b + . . . +           a b

n-1     

+           b

n

0

     1                              n-1         n

       n        n
(a – b)

n 

=  

 

 

 a

n-i

 b

i

 

  i=0      i

Dwumian Newton’a 

Liczby  Fibonacciego

1     1

2       3 5      8 13 21 34 55 89 144 ...

F

1

  = 1 ;

F

2

 = 1 ;

F

n

 = F

n-1

 + F

n-2 

      dla n > 2

              n                         n

    1 1  + 5            1  - 5   

F

n

 =                                                  

   5  

    2               2

Na płaszczyźnie jest danych  n  okręgów. 

Jaka  jest  maksymalna  liczba  obszarów,  na  które  dzielą  one 

płaszczyznę? 

Wyprowadź 

rozwiązanie 

w 

postaci 

odpowiedniej 

zależności 

rekurencyjnej.

1

2

1

2

4

3

         1 = 2

0

1 + 1 = 2 = 2

1 

            1 + 2 + 1 = 4 = 2

2

 

1 + 3 + 3 + 1 = 8 

= 2

3 

      n      n
                 = 
2

n

      i=0    i

a = b = 
1

n

n

             n

              n

2

n  

=  

      

 

 +                    +   ...   +             

       +          

0

1

            n-1

              n

1 + 4 + 6 + 4 + 1 = 16 = 2

4

       4      n
                 = 
2

4

      i=0    i

n

n

             n

n                    n

2

n  

=  

      

 

 +                    +   ...   +                    +                = (a +   

b) 

0

1

            n-1

n

Zależności rekurencyjne 

– wzory jawne

Metoda przez podstawianie

Przyklad

a

1

, a

2

, a

3

,...,a

i

, a

i+1

,... ;

1 , 2 , 3 , 7 ,15 . 31 . 

...

a

1

=1

a

n

 = 2 a

n-1

 + 1

n>1     ;      a

n

 =2

n

 – 1

;     n>1

a

n

 =  2 a

n-1

 + 1  =   2(2 a

n-2

 + 1) + 1 = 2

2

 a

n-2

 + 2 + 1  =

     = 2

2

(2 a

n-3

 + 1) + 2 + 1 = 2

3

a

n-3

 + 2

2

 + 2

1

 + 2

0 

=

                               

.  .  .

     = 2

k

a

n-k

 + 2

k-1

 + 2

k-2 

+ ... + 2

2 

 + 2

1

 + 2

0 

 =

    

     = 2

n-1

 + 2

n-2 

+ ... + 2

2 

 + 2

1

 + 2

0 

 =     2

n

 – 1

Suma wyrazów postępu geometrycznego 

a

1

, a

2

, a

3

,...,a

i

, a

i+1

,... ; .q = a

i+1

/a

i

 1 - q

n

       S =                 a

1

                    

1 - q

2

n-1

 + 2

n-2 

+ ... + 2

2 

 + 2

1

 + 2

0 

 =   2

n

 – 1

     

 a

n

   +   a

n-1

 +  ...+   a

3

   +a

2

  + a

1

Ponieważ

q = 2

i+1

/2

i 

= 2   

i  

a

1

 = 1

     

zatem      

S

n

 = (1-2

n

)/(1-2) = - (1-2

n

) = 2

n 

-1

Sprawdzenie:

n

a

n

 = 2 a

n-1

 + 1

a

n

 = 2

n

 - 1

1

1

1

2

2*1 + 1 = 3

2

2 

– 1 = 3

3

2*3 + 1 = 7

       2

3 

– 1 = 7

4

2*7 + 1 = 15  2

4

– 1 = 15

5

2*15 + 1 = 31

2

5

– 1 = 31

Przykład

Dana jest zależność rekurencyjna

f(n) = f(n-1) + 3

n

;

n > 1  ; f(1) = 3

Wyznacz postać analityczną

f(n) = f(n-1) + 3

n

;

n > 1  ; f(1) = 3

f(n) = f(n-1) + 3

n

 = (f(n-2) + 3

n-1

) + 3

n

 = 

= ((f(n-3) + 3

n-2

) + 3

n-1

) + 3

n

 = 

=  . .  .=

= 3

1 

 

+ 3

2

 + 3

3

 + 3

4

 + . . . + 3

n-1

 + 3

n

Ponieważ kolejny wyraz f(n) jest sumą postępu arytmetycznego

1 - q

n

         

S =                 a

1

1 - q

q = f(i+1)/f(i) = 3

i+1

/3

i 

= 3

,  a

1

 = 3

Zatem

f(n) = (1- 3

n

)/(1-3)*3 = 3/2(3

n 

– 1)

Sprawdzenie

n

f(n) = f(n-1) + 3

n

f(n) = 3/2(3

n 

– 1)

1

3

3

2

3 + 3

2

 = 12

3/2(3

2

 – 1) = 3/2(8) = 12

3

12 + 3

3

 = 39

3/2(3

3

 – 1) = 3/2(26) = 39

4

39 + 3

4

3/2(3

4

 – 1)

Metoda równania charakterystycznego

Rozważmy ciągi postaci:

s

n

 = a*s

n-1

  +  b*s

n-2

.  a , b  - stałe

 Przypadek a)

a = 0  lub  b = 0

;

 znane są wartości s

0

  i s

1

Jeżeli b = 0  to  s

n

 = a*s

n-1

   dla n  1. 

Zatem s

1

 = as

0

 , s

2

 = as

1

 = a

2

s

o

 ,...

Ostatecznie

s

n

 = a

n

s

o

Przykład

s

n

 = 3s

n-1

 , gdzie  s

0

 = 5   

; 

5, 15, 45, …

ponieważ a = 3  zatem ostatecznie  s

n

 = 3

n

5

 

 ;5, 15, 

45, …

Metoda równania charakterystycznego

Rozważmy ciągi postaci:

s

n

 = a*s

n-1

  +  b*s

n-2

.  a , b  - stałe

Jeżeli a = 0         to      s

n

 = b*s

n-2

     dla n  2. 

Zatem s

2

 = bs

0

 , s

4

 = bs

2

 = b

2

s

o

,...

Ostatecznie

s

2n

 = b

n

s

o 

dla

 

n  N

Podobnie

s

3

 = bs

1

 , s

5

 = bs

3

 = b

2

s

1

,...

Ostatecznie

                   s

2n+1

 = b

n

s

1       

dla 

n  N

Przykład

s

n

 = 3s

n-2

, 

gdzie  s

0

 = 5  i s

1

 = 2  , 

   Ostatecznie   s

2n

 = 3

n

5

 

   i 

s

2n+1

 = 3

n

2

 

 

Przykład

s

n

 = 3s

n-2

, 

gdzie  s

0

 = 5  i s

1

 = 2  , 

   Ostatecznie   s

2n

 = 3

n

5

 

         i 

s

2n+1

 = 3

n

2

 

 

Sprawdzenie:

n

s

n

 = 3s

n-2 

s

2n

 = 3

n

5

 

  ,  s

2n+1

 = 3

n

2

 

0

5

            5

2n = 0 

    

n = 0

1

2

2

2n+1 = 1      n = 0

2

15            15

 

2n = 2 

     

n = 1

3

6

 6

2n+1 = 3      n = 1

4

45            45

 

2n = 4 

     

n = 2

5

18

 18

2n+1 = 5      n = 2

…              …                          …                       …                               

  …                               …

        Przypadek b)

a  0  lub  b 0

; znane są wartości s

0

  i s

1

Znana jest zależność

s

n

 = a*s

n-1

  +  b*s

n-2

;   a , b  - stałe 

Rozważmy równanie charakterystyczne

x

2

 – a*x – b = 0

F

n

 = F

n-1

  + F

n-2

równanie jednorodne

x

n

 = x

n-1

  +  x

n-2

równanie charakterystyczne

x

n

 = x

n-1

  +  x

n-2

 / x

n-2

x

2

 = x+  1

F

n

 = A x

1

n

  +  B x

2

n

ogólna postać rozwiązania 

Rozważmy równanie charakterystyczne

x

2

 – a*x – b = 0

W sytuacji gdy równanie to ma dwa różne rozwiązania r

1

 i r

2

 wówczas

s

n

 = c

1

r

1

n

  + c

2

r

2

n

 

 

Gdy s

o

 i s

1

 są dane wówczas przez podstawienie n = 0 i n=1 wyznaczyć 

można  c

1

 i c

2

.

W sytuacji gdy równanie to ma tylko jedno rozwiązanie r

 

 wówczas

s

n

 = c

1

r

n

  + c

2 

n r

n

 

 

Gdy s

o

 i s

1

 są dane wówczas przez podstawienie n = 0 i n=1 wyznaczyć 

można  c

1

 i c

2

.

Rozważmy równanie charakterystyczne

x

2

 – a*x – b = 0

Przykład

s

n 

= s

n-1

 + 2 s

n-2

;

s

0

 = s

1

 = 3

równanie charakterystyczne ma postać x

2

 – a*x – b = 0 zatem

x

2

 –x – 2 = 0

 

 = b

2

 – 4ac = 1 +8 = 9      ;      x

1

 = (-b + )/2a = (1 + 3)/2 = 2 . x

2

 = -1

Postać poszukiwana

s

n

 = c

1

r

1

n

  + c

2

r

2

n

 

 

Zatem s

n

 = c

1

2

n

  + c

2

(-1)

n

 

Wiadomo, że s

0

 = s

1

 = 3

Wyznaczane są:   c

1

 i c

2

Dla n = 0

s

n

 = c

1

2

0

  + c

2

(-1)

0 

= c

1

+ c

2

 = 3

Dla n = 1

s

n

 = c

1

2

1

  + c

2

(-1)

1 

= 2c

1

- c

2

 = 3

         3c

1

 = 6      ,

c

1

 = 2   , c

2

 = 1

Ostatecznie   s

n

 = 2*2

n

  + (-1)

n

Sprawdzenie

n

s

n 

= s

n-1

 + 2 s

n-

2

              

s

n

 = 2*2

n

  + (-1)

n

0

3

2*2

0

 + (-1)

0

 = 3

1

3

2*2

1

 + (-1)

1

 = 3

2

3  +  2*3

2*2

2

 + (-1)

2

 = 9

3

9   + 2*3

2*2

3

 + (-1)

3

 = 15

4

15 + 2*9

2*2

4

 + (-1)

4

Przykład

s

n

 = 4s

n-1

 – 4s

n-2

   , n  2 ;

s

0

 = 1 , s

1

 = 8

równanie charakterystyczne ma postać x

2

 – ax – b = 0 zatem

x

2

 –4x + 4 = 0

 

 = b

2

 – 4ac = 16 - 16 = 0     ;      x

1

 = x

2

 = 4/2 = 2

Postać poszukiwana     s

n

 = c

1

r

n

  + c

2

nr

n

 

   a dokładniej

s

n

 = c

1

2

n

  + c

2

n2

n

 

 

Wyznaczane są:  c

1

 i c

2

Dla n = 0

s

n

 = c

1

2

0

  + c

2

*0*2

0 

= c

1

 = 1

Dla n = 1

s

n

 = c

1

2

1

  + c

2

*1*2

1 

= 2c

1

+ 2c

2

 = 8

             c

1

 = 1 ,    c

2

 = 3

Ostatecznie   s

n

 = 2

n

  + 3*n*2

n

Sprawdzenie

        n

s

n

 = 4s

n-1

 – 4s

n-2

  

 s

n

 = 2

n

  + 3*n*2

n

0

1

2

0

  + 3*0*2

0

 = 1

1

8

2

1

  + 3*1*2

1

 = 8

2

        4*8  -  4*1

2

2

  + 3*2*2

2

 = 28

3

      4*28  -  4*8

2

3

  + 3*3*2

3

 

Kongruencje

x  y (mod m)

kongruencja

;

m - moduł

6  1 (mod 5)

;

12  2 (mod 5) ;

14  4 (mod 5)

Kongruencje nie zmieniają swoich właściwości przy obustronnym 

podnoszeniu do potęgi (pierwiastkowaniu) oraz przy mnożeniu i 

dzieleniu przez inne kongruencje

6  1 (mod 5) / 6

36  6 (mod 5)  1 (mod 5)

6  1 (mod 5) / * (12  2 (mod 5))

72  2 (mod 5)

Zastosowania

Wyznacz największe x  3

15

 podzielne przez 17

3

3 

= 27  10 (mod 17)

27  10 (mod 17)  / * 27  10 (mod 17)  

3

6

  100 (mod 17)    15 (mod 17)

3

6

   15 (mod 17) / * 3

6

   15 (mod 17)

3

12

  225 (mod 17)    4 (mod 17)

3

12

  4 (mod 17)  / *3

3 

 10 (mod 17)

3

15

  40 (mod 17)  6 (mod 17)

Zatem

3

15

 – 6  0 (mod 17)   bo 0 (mod 17)  17 (mod 17)  34 (mod 17), 

itd   

x = 3

15

 – 6

Na jaką cyfrę kończy się liczba 2

100

?

2

10

  4 (mod 10)

1024   4 (mod 10)

2

10

  4 (mod 10) / 

2

2

20

  16 (mod 10)  6 (mod 10)

2

20

  6 (mod 10) / 

2

2

40

  36 (mod 10)  6 (mod 10)

2

40

  6 (mod 10)  / 

2

2

80

  36 (mod 10)  6 (mod 10

2

80

  6 (mod 10) / (2

20

  6 (mod 10) )

2

100

  36 (mod 10)  6 (mod 10)

2

100

  6 (mod 10)

Zatem 2

100

  kończy się cyfrą 6.

91

Schemat Hornera

Dana jest reprezentacja liczby M w systemie przy podstawie a. 

Oblicz jej dziesiętną postać.

M = r

k

a

k 

+ r

k-1

a

k-1 

+ r

k-2

a

k-2

 + ...+ r

1

a

1

 + r

0

M = (r

k

a

k-1 

+ r

k-1

a

k-2 

+ r

k-2

a

k-1

 + ...+ r

1

)a

1

 + r

0

M = ((r

k

a

k-1 

+ r

k-1

a

k-2 

+ r

k-2

a

k-1

 + ...+ r

2

)a+ r

1

)a + r

0

M = (...((r

k

a+ r

k-1

)a

 

+ r

k-2 

)a + ...+ r

1

)a + r

0

Przykład

M = (45)

10

 = (101101)

2

 = 1*2

5 

+ 0*2

4 

+ 1*2

3 

+1*2

2

 + 0*2

1

 + 1*2

0

1*2

5 

+ 0*2

4 

+ 1*2

3 

+1*2

2

 + 0*2

1

 + 1*2

0 

= 1*2

5 

+ 1*2

3 

+1*2

2

 + 1*2

0 

= 

 = 100000 + 1000 + 100 + 1 = 101101

(101101)

2

 = 

= ((((1*2

 

+ 0)2

 

+ 1)2

 

+1)2 + 0)2+

 

1 = ((((1*2

 

)2

 

+1)2

 

+1)2)2+

 

1 =

= (((5) 2 +1)2)2+1 =

= ((11)2)2+1 = 44 + 1 = 45

Zastosowanie

Najszybszy sposób obliczania potęgi x

n. 

Niech n = 45.

Zatem x

45 

= x

((((1*2 + 0)2 + 1)2 +1)2 + 0)2+ 1 

= (((((x

2

)

2

x)

2

)x)

2

)

2

x

Bo  x*x = x

2 

 ;

 x

2

x

2

 = x

2+2 

 ;

 (x

2

)

3 

= x

2*3

Sprawdzenie

x

((((1*2 + 0)2 + 1)2 +1)2 + 0)2+ 1

 = (x

((((1*2 + 0)2 + 1)2 +1)2 + 0)2 

)x =

= (x

(((1*2 + 0)2 + 1)2 +1)2 

)

2 

x =

= ((x

((1*2 + 0)2 + 1)2 +1

)

2

)

2

x =

= (((x

((1*2 + 0)2 + 1)2 

)x)

2 

)

2

x =

= (((((x

(1*2 + 0)2 

)x)

2 

)x)

2 

)

2

x =

= (((((x

(1*2 + 0)

)

 2

x)

2 

)x)

2 

)

2

x =

= (((((x

 (1*2)

)

 2

x)

2 

)x)

2 

)

2

x =

= (((((x

 2

)

 2

x)

2 

)x)

2 

)

2

x 

Przykład

X

22

 = X

16 

X

4 

X

2 

 bo  22 = 2

4

 + 2

2 

+ 2

1 

 = 16 + 4 + 2

X

22

 = (X

8 

X

2 

)

2

X

2

X

22

 = ((X

2

)

4

X

2 

)

2

X

2

W Y K Ł A D - 5

Elementy teorii grafów 

• relacje,

• grafy (symetryczne i skierowane),

• drogi, cykle, rodzaje grafów: drzewa, dwudzielne, pełne,

• macierzowe reprezentacje grafów,

• grafy Eulera i Hamiltona, grafy płaskie

(Wilson  R.J.,  Wprowadzenie  do  teorii  grafów,  PWN, Warszawa,  1998.  Ross K.A., Wright C.R.B., 
Matematyka  dyskretna,  PWN,  Warszawa  1996.  N.  Deo,  Teoria  grafów  i  jej  zastosowania  w 
technice i informatyce. PWN, Warszawa 1980.)

Relacje

R

 

 -  relacja dwuargumentowa na zbiorze  

S

 x 

T

R  S 

x

 T

Przykład 
S = {1,2,3},    T = {a, b} , S x T = {(1,a), (1,b), (2,a), (2,b), (3,a), 

(3,b)}

R = S x T = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}

1

2

3

a

b

1

2

3

Przykład 

S = {1,2,3},

T = {1,2,3} ,

 

S  x  T  =  {(1,1),  (1,2),  (1,3),  (2,1),  (2,2),  (2,3),(3,1), 

(3,2), (3,3)}

R’  = {(1,2),(1,3),(2,3)}   S x T;

a R’ b  a < b

 dla  a S, bT 

R”  = {(1,1),(2,2),(3,3)}   S x T

;

a R” b   a = b  dla  a S, bT

R’’’ = { }   S x T

;

a R’’’ b   a mod 5 = b mod 5 = 4 mod 5

 dla  a S, bT

1

2

3

a

b

Niech   R  S x S 

(relacja R  w zbiorze  S )

Jest  zwrotna

(x,x)  R

,  x  S

Jest  przeciwzwrotna

(x,x)  R

,  x S

Jest  symetryczna

(x,y)  R  (y,x)  R,  x,y S

Jest  antysymetryczna

(x,y)  R & (y,x)  R   x = y

Jest  przechodnia

(x,y)  R & (y,z)  R   (x,z)  R 

Przykład

R’  = {(1,2),(1,3),(2,3)}   S x T;

a R’ b  a < b

 dla  a S, bT 

R”  = {(1,1),(2,2),(3,3)}   S x T

;

a R” b   a = b  dla  a S, bT

Jeżeli  R  S x T  to  R^  T x S  jest relacja odwrotną

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = 

{(a,a), (b,b),

(c,c), (d,d), (a,b)}. Czy relacja ta jest zwrotna.

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,a), 

(b,b),(c,c), (d,d)}. Czy relacja ta jest przechodnia

Jeżeli dana relacja jest symetryczna, zwrotnia i przechodnia, to jest relacją

równoważności, na której definiujemy klasy abstrakcji.

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b), 

(b,c),

(a,a)}. Czy relacja ta jest przeciwzwrotna.

Przykład

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b), 

(b,a),(c,c), (d,c), (c,d)}. Czy relacja ta jest symetryczna.

Przykład

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b), 

(b,c),

(c,d), (d,a)}. Czy relacja ta jest przeciwsymetryczna.

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b), (a,c), 

(b,a)}. Czy relacja ta jest spójna.

Niech będzie dany zbiór X = {a, b, c, d}. Zdefiniujmy relację R = {(a,b), 

(b,a),(c,c)}. Czy relacja ta jest symetryczna.

Relacja jest spójna, jeżeli

x,y S, x ≠ y  (y,x)  R   (x,y)  R

Relacje < i ≤ są relacjami spójnymi w zbiorze liczb rzeczywistych

a

b

c

a

b

c

S = {a,b,c}

;

R’ = {(a,b),(c.b),(a,c)}  ; 

a

b

c

G R A F Y 

Graf

G = (S, R)  

Przykład 

S = {a,b,c}

;

R = {(a,b),(b,a),(b,c),(c.b),(c,a),(a,c)} 

G = (S, R’)

A

D

C

B

C

 

D

B

(1736) Leonard Euler 

 

Problem mostów 

królewieckich

Przejść przez każdy z mostów dokładnie jeden raz i powrócić do punktu 
wyjściowego.

A

  
      6

7

 

     2

  

  3

              1                                                      8

                    

       

                      3                                       5

   

  

    

4

Problem sieci wodnej (W), gazowej (G) i elektrycznej (E). Są trzy domy H

1

, 

H

2

  i  H

3

,  z  których  każdy  musi  być  podłączony  przewodami  do  każdej  z 

trzech sieci. Czy jest możliwe dokonanie takich połączeń bez skrzyżowania 

przewodów?

H

1

H

2

H

3

W

G

E

Krawędzie,  łuki,  wierzchołki,  drogi,  ścieżki,  pętle,  kontury,  obwody, 

cykle, drogi zamknięte. 

Ścieżka (droga) elementarna    -   nie przecina samej siebie.

Graf  spójny  G

-  jeżeli  istnieje  przynajmniej  jedna  ścieżka  (droga) 

miedzy każdą para wierzchołków w G.

Podgraf

G’  G = (X,R) , G’ = (X’,R’);     X’  X ; R’  R

Długość drogi – liczba krawędzi drogi.

Stopień wierzchołka  - liczba krawędzi z nim incydentnych.

Graf regularny – wszystkie wierzchołki sa tego samego stopnia

Charakterystyki grafu

n  -  liczba wierzchołków

e  -  liczba krawędzi

k  -  liczba składowych (spójności)

e    

n – k

r  -  rząd grafu

r = n – k

  -  zerowość grafu

 = e – n + k

Przykład

Rząd grafu  =  liczba gałęzi w każdym dendrycie grafu

Zerowość grafu  =  liczba cięciw w grafie

 

rząd  + zerowość   = liczba krawędzi w grafie

Izomorfizm

Dwa grafy są izomorficzne jeśli zachodzi wzajemnie jednoznaczna 

odpowiedniość między ich wierzchołkami oraz ich krawędziami przy 

zachowaniu relacji incydencji.

Grafy izomorficzne muszą mieć:

• tę samą liczbę wierzchołków

• tę samą liczbę krawędzi

• równa liczbę wierzchołków o danym stopniu

Poszukiwane  jest  kryterium  efektywnego  obliczeniowo  wykrywania 
izomorfizmu!

I z o m o r f i z 
m

N o m e n k l a t u r 
a

Dwa grafy G

1

 i G

2

 są izomorficzne, jeżeli istnieje wzajemna 

jednoznaczna odpowiedniość między wierzchołkami grafu 

G

1

 i wierzchołkami grafu G

2

, taka że liczba krawędzi łącząca 

dwa dowolne wierzchołki w G

1

 jest równa liczbie krawędzi 

łączących odpowiadające im wierzchołki w G

2

.

Grafy dwudzielne, grafy pełne, drzewa

Graf dwudzielny

Graf pełny

Drzewo

Graf dwudzielny 

– wierzchołki którego można pokolorować dwoma barwami. 

Graf pełny  

-  każdy wierzchołek którego jest połączony (krawędzią lub łukiem) z 

pozostałymi 

        wierzchołkami

Drzewo

  -  graf spójny bez obwodów (drzewo genealogiczne, rzeka, drzewo 

decyzyjne, itp.)

Właściwości drzewa:    
    

•między każdą parą wierzchołków istnieje tylko jedna droga

•drzewo o  n  wierzchołkach ma  n-1 krawędzi

Drzewo binarne  

-  dokładnie jeden wierzchołek jest stopnia drugiego a 

pozostałe stopnia 

              trzeciego lub pierwszego.

poziom  0

poziom  1

poziom  3

poziom  4

Właściwości drzew binarnych:

-  liczba  wierzchołków      n    w  drzewie  binarnym  jest  zawsze 

nieparzysta.

- liczba krawędzi w drzewie jest równa  

p = (n+1)/2, 

- p – liczba wierzchołków wiszących

1/2(p  +  3(n-p-1)+2)  =  n-1   

-    liczba  krawędzi  w 

drzewie

Własności drzew (dla grafu T mającego n-wierzchołków):

• T nie zawiera cykli, ilość krawędzi = n-1 
• T jest grafem spójnym, każda krawędź jest mostem. 
• Każde dwa wierzchołki T połączone są dokładnie jedną drogą. 
• T nie zawiera cykli, ale po dodaniu dowolnej nowej krawędzi otrzymujemy graf 

z dokładnie jednym cyklem. 

Grafy  platońskie

A

A

A

A

B

D

C

B

D

C

B

D

C

B

D

C

Drzewa o wierzchołkach zaetykietowanych 

Liczba drzew zaetykietowanych o n wierzchołkach 

(n2)  

wynosi  

n

n-2

.

A

A

B

D

C

B

D

C

C

A

B

D

Łatwo zauważyć, że liczba drzew niezaetykietowanych o czterech 
wierzchołkach wynosi 2.

Dendrytem grafu spójnego  G  nazywamy drzewo będące jego 
podgrafem i zawierającym wszystkie wierzchołki grafu G.

Graf niespójny  o  k  składowych ma las dendrytów składający się z   k  
drzew.

Każdy graf spójny ma przynajmniej jeden dendryt.

Cięciwą nazywamy krawędź grafu  G  która nie należy do danego 
dendrytu.

Przykład

REPREZENTACJE  MACIERZOWE

Macierz sąsiedztwa 

A

(n x n) 

,

Macierz incydencji  

M

(n x m)

  

grafu o  n  wierzchołkach i  m  krawędziach

 a

i,j

 - liczba krawędzi łączących wierzchołek  „i”  z wierzchołkiem „j”

m

i,j

 = 1 jeśli i-ty wierzchołek jest incydenty z j-tą krawędzią

   3                  b             
4

1           a                
    2

      c               d                 
 e

m

i,j

 = 0 w przeciwnym wypadku

 1       2            3

           4

 

1

    0         1     

 1     0

 2    

1         0    

 1    1

A    =     

 3    

1         1       0     1

 

4

     0         1         1     0

   a      b

   c        d      e

    1    

1       0       1          0       0

    

 2   

1        0       0          1       1

M    =             

 3    

1       1       1          0       0

     

4

    0       1        0         0       1

Grafy Eulera  (przechodzenie przez krawędzie)

Grafem Eulera nazywamy graf składający się z drogi Eulera. 

Drogą Eulera nazywamy drogę zamknięta przechodzącą dokładnie jeden raz 
przez każdą krawędź z grafu G.

Graf jest grafem Eulera wtedy i tylko wtedy gdy  wszystkie wierzchołki  G  są 
stopnia parzystego.

A

D

C

B

Graf  spójny  mający  dokładnie  dwa  wierzchołki 
stopnia

 nieparzystego, ma drogę Eulera

.

Obwód Hamiltona    (przechodzenie przez wierzchołki)

Obwodem Hamiltona w grafie spójnym jest droga zamknięta. Która przechodzi 

przez każdy wierzchołek grafu G dokładnie jeden raz.

Obwód  Hamiltona  w  grafie  o    n  wierzchołkach  składa  się  z    n   
krawędzi.

Problem komiwojażera. 

Całkowita liczba różnych obwodów 

Hamiltona  w  grafie  pełnym  o    n    wierzchołkach: 
(n-1)/2!

Grafy planarne

Graf  planarny  to  graf  który  można  narysować  na  płaszczyźnie  bez  przecięć  –  to 

znaczy  tak  aby,  żadne  dwie  krawędzie  nie  przecinały  się  na  rysunku  poza 

wierzchołkiem z którym są incydentne. 

Grafy

 K

3,3 

 

i  

K

5

  

są nieplanarne.

Dany  graf  G  jest  planarny  wtedy  i  tylko  wtedy  gdy  nie  zawiera 

podgrafu homeomorficznego z grafem K

3,3  

i  K

5

 .

Dany graf G jest planarny wtedy i tylko wtedy gdy jest ściągalny 

do  podgrafu K

3,3  

lub do podgrafu  K

5

 .

Problem 
kolorowania

Shell

       Esso

Gulf

       BP

Shell

   lub

Gulf

Graf jest k - kolorowalny jeżeli każdemu wierzchołkowi można przypisać jeden z k 

kolorów, w taki sposób że żadne dwa wierzchołki sąsiednie nie mają tego samego 

koloru.

W Y K Ł A D - 6

Elementy teorii grafów 
- przeszukiwanie grafów
- algorytmy na grafach (zadania najkrótszych dróg): algorytm Fleury’go, 
                                                                           algorytm Kruskala, algorytm 
Prima, algorytm Dijkstry
(Ross K.A., Wright C.R.B., Matematyka dyskretna, PWN, Warszawa 1996.)

Problem wyznaczania najkrótszej trasy: znaleźć taka ścieżkę, prowadzącą od węzła  i  

do węzła  j, by suma wartości przebywanych połączeń była jak najmniejsza. Wyznacz 

najkrótsza ścieżkę łączącą węzły  A  i  J.

PRZESZUKIWANIE GRAFÓW (metoda podziału i ograniczeń)

Dane są naczynia o pojemności odpowiednio 4 i 3 litra. Czy można z ich pomocą 

odmierzyć pojemność 2 litrów? Wszystko to przy założeniu, że naczynia te nie są 

cechowane, a możliwe działania obejmują nalewanie do pełna (bądź opróżnianie) 

lub przelewanie z jednego naczynia do drugiego.

A

J

Algorytm Dijkstry

Jaka jest długość najkrótszej drogi łączącej dwa wierzchołki w danym grafie 

skierowanym?  Jeśli  graf  skierowany  ma  wagi,  to  jaka  jest  waga  minimalna 

lub maksymalna takiej drogi?)

   Przykład

     v

2

          7

    v

4

     2

      v

6

 3                                                  7                        9

         v

1

                                  

    2                                   5                                    4

    9

                                                                 1                                  8

        

v

3

                 4                   v

5

             v

7