zoradene prednasky

Návrat na detail prednášky / Stiahnuť prednášku / Univerzita Komenského / Fakulta matematiky, fyziky a informatiky / Diskrétna matematika 1

 

Skuska (dm.doc)

Subject: DM 14.1.99

 

Zdraaavstvujte!

 

Neviem ci uz niekto poslal diskretnu matiku z 14.1.99 (moj mail server died),

ale ako sa hovori, "Ako sa do hory vola, matka mudrosti", idem na to:

 

1. Dokazte, ze pocet kombinacii s opakovanim k-tej triedy z n prvkov je rovny

n+k-1 nad k, zostrojte bijekciu medzi komb. s opak. k-tej triedy z n prvkov a k

tej triedy bez opakovania z n+k-1 prvkov.

 

2. n! > (n/e)     Matematickou indukciou (to je zadanie, nie moj postup)

 

3.

 

n

Suma ((-1)^k-1)/k (n) = 1 + 1/2 + ... + 1/n

k=1               (k)

 

4. |A| = n; X je podmnozina A, Y je podmnozina A; Najdite pocet dvojic (X, Y)

takych, ze plati |(X-Y) zjednotenie (Y-X)| = 1 (pre zaujimavost je to

symetricka diferencia, ze?)

 

5. Vyslovte a dokazte C-B vetu. (otazky typu: "Ako su definovane mnoziny C a B

su tu nemiestne a nedoporucujem klast ich na skuske ;)

 

6. Najdite najv. koeficient (a+b+c)^10 ; (a+b+c+d)^14

 

 

--------------------------------------------------------------------

 

Takze co bolo dnes na diskeretnej matematike ked uz mame taky pekny datum.

 

1. Nech A je mnozina |A|=n a X<=A a Y<=A najdite pocet usporiadnenych dvojic

(X,Y) takych ze plati A prienik B = 0

 

2. Dokazte             ( n )n

                n!<= 2 (---)

                       ( 2 )

3. Zostrojte zobrazenie z <0,1> na (0,1)

 

4. a) Kolkymi sposobmi mozeme rozdelit n rovnakych predmetov medzi k ludi

  b) to iste ale kazdy musi dostat r (specialne r=1)

 

5. Dokazte ze ak A<>0 tak neexistuje zobrazenie f:A->0

 

6. Nech k patri N a B je taka mnozina ze |B|=n potom pocet kombinacii bez

opakovania k-tych tried prvkov mnoziny B je rovny

 

           1  k-1         ( n )

          --- |-| (n-j) = (   )

           k! j=0         ( k )

 

 |-| symbolyzuje tieco ako sumu ale nasobenie ( pi ?? )

 

 

Celkom lahke. A teraz co som dostal na 3-hodinovu ustnu odpoved.

 

1. Bijekciu medzi komibaciami s opakovanim k-tej triedy z n roznych prvkov a

kombinaciami bez opakovania k-tej triedy z n+k-1 roznych prvkov.

 

2. n - Francuzov m - Anglicanov a zvysok si domyslite

 

3. T(n) - pocet postupnosti z 0 a 1 dlzky n takych ze ziadne dve 1 nestoja

vedla seba.

Dokazat: T(n)=T(n-1)+T(n-2)

vyjadrit T(n) pomocou kombinacnych cisiel

 

 

--------------------------------------------------------------------

 

 

dna 14.1.99 boli tieto priklady:

 

1. dokaz, ze pocet komb. s opak k-tej triedy z n prvkov je

   / n+k-1\

   [      ]

   \   k  /

 

  plus zostroj bijekciu  medzi komb. s opak. k-tej triedy z n prvkov

a komb. bez opak. k-tej triedy z n+k-1 prvkov.

 

2. dokaz matem.induk.:

     n!>(n/e)^n

 

3. dokaz, ze :    n

                ---            

                \               / n  \

                /    (-1)^k /k  [    ]   = 1+1/2+1/3+ ... +1/n

                ---             \ k  /

                k=0

 

    alebo nieco take

 

4. A je mnozina a plati [A]=n  nech X,Y su podmnoziny A. Kolko je

uspor. dvojic (X,Y) takych, ze plati:

 

    [ (X-Y) v (Y-X) ] = 1

v=zjednotenie

 

5. vyslov a dokaz C-B vetu (to nie je rozdiel mnozin C,B to je

Cantor-Bernsteinova veta, dobre?) a tiez tu lemu k tomu

 

6. aky bude najvacsi koef. vo vyrazoch:

     a)   (a+b+c)^10

     b)   (a+b+c+d)^14

-----------------------------------------------------------------------

Dnes som stravil asi 6 hodin v dobre chladenej XI (akv.) u pana docenta

Rozhodol sa ze dnes da premierove priklady - to znamena ze az na jeden

take este asi neboli

Tu su:

 

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

 suma=--------.----------- = ------------

  k=1 (k-1)!k! ((n-k)!)^2    (n!(n-1)!)^2  

 

2. (dost lahky nepamatam si zadanie) n tice z 1 a 0 kde nemozu byt dve  1

vedla seba.  Napis vzorec pre T(n)= pocet n-tic plus dokaz ze

T(n+1)=T(n)+T(n-1)

 

3. Nieco o tranzitivnom uzavere

 

4. (n/k)^k < (n nad k) < (3*n/k)^k

 

5. nieco okolo permutacii a ich urcovanie pomocou cyklov

 

6. Klasika pre romantikov: Mame n Anglicanov a m Francuzov. Kolkymi

sposobmi ich mozeme postavit do radu ked pri sebe musia stat aspon dvaja

krajania.

 

 

-----------------------------------------------------------------------

Cafte !!

 

Vcera 7.1. boli na skuske z diskretnej matiky tieto priklady:

 

1. Dokazte, ze ak B{} tak  ani  mnozina zobrazeni z A do B nie je {}.

  {} - je prazna mnozina.

2. Dokazte:

    ----   /  n \

  4*\           |          |  =          n    (n/2)+1           n*Pi

    /           |  4k  |  =         2  + 2       *cos ----

    ----   \         /                            4

      k

 

3. Dokazte tu lemu, co sa pouziva pri dokaze Cantor-Bernsteinovej vety.

  Ta s tymi mnozinami A1,A2,B1,B2.

 

4. Najdite minimalnu hodnotu suctu:

      s

    -----  / ni \

    \           |          |          pricom   n =        n1 + n2 + .........+ ns

    /           |  k   |

    -----  \         /

     i=1

 

5. Zistite, ci je kvantifikovany vyrok tautologia pre lubovolne vyr. formy

  a,b....  presne znenie si uz nepamatam....

  Najdete to v tych prikladoch, co nam dal Toman....

 

6. Nech A je podmn. B(n,l) a B mnozina vsetkych vektorov z B(n,k)

  porovnatelnych aspon s jednym vektorom v A. Dokazte, ze

                   |A|          |B|              B(n,i) obsahuje tie vektory z {0,1}^n,

                   --- <= ---              ktore obsahuju prave i jednotiek;

                   /n\          /n\              ak a=(a_1,...,a_n), b=(b_1,...,b_n),

                   \l/          \k/              tak a<=b, ak a_i<=b_i, pre vsetky i;

                                      a,b su porovnatelne, ak a<=b alebo b<=a

 

 

Inac skuska bola hrozne od veci.....

 Pisomka od 9:00 do 11:00 (asi). Skoro cely cas bol mimo....

 Potom zacal opravovat pisomky . Na "ustnej" si nas postupne volal dnu,

 a dal ratat tie veci, co sme na pisomke nevedeli....

 (Dal ratat aspon dva - stvrty a siesty)..

 

 Vcelku radim na pisomke napisat co najviac...(mnozstvo, nemusi byt vsetko

 spravne), nech to vyzera, ze toho mate vela.... On sa na riesenia skoro

 ani nepozeral....

 

 Treba vediet ratat priklady z tych 6-tich papierov.(Hlavne sumy komb. cisel);

 

Uspesnost:

  7/15  (mohla by byt aj lepsia)

 

To najlepsie na koniec:

  Odchadzali sme zo skusky nieco po pol piatej. (Vela z nas tam

  teda bolo 7 hodin)

---------------------------------------------------------------------------

------

Subject: Dm  6.2.!!!!

 

 Neviem, ci to je ono, ale dns na skuske Tominovi trcali dajake papiere s

datumom 6.2.1998 a nejakymi prikladmi; co som zachytil (nebolo to moc

citatelne:

                         m

 1.  Dokaz:    (n+m)  = suma (n+k-1)

                ( m )  = k=0  (  k  )

 

 2. Zadanie nebolo citatelne, ale nieco:

                   

                ( 2^(1/2)+ 3^(1/4) )^100  ; tajny tip, urci cleny s

racionalnymi koeficientami.

 (Ten vztah v ludskej reci - odmocnina z 2 + stvrta odmocnina z 3 a to cele na

100).

 

 Inac dnes mal dobru naladu uplne trapne priklady, spravili aj taki, co neboli

ani raz na prednaske a nevedeli vobec teoriu (napr. Vasicek, Vrbovsky)

 Najtazsi bol asi: mate n rovnakych predmetov rozdelit medzi k ludi, ked kazdy

ma dostat minimalne r predmetov. Kolko je sposobov? (r>0; kr<n)

 [(n-1)+k(r-1)]!

 --------------- =>to je riesenie.

 (k-1)! (n-kr)!

 Potom spec. pripad r=0 a r=1, dokaz, ze neexistuje najdi zobrazenie: A->B,

 ak A<>{} a B={}, potom dokaz, ze kombinacii bez

opakovania je n nad k, a najdi proste zobrazenie <0;1> -> (0;1).

 

 zatial cauko, uzivajte si pripravu, ja uz mam volno...

 

                                                Vr.

------

Subject: dm 28/1

 

Nazdar spoluziaci !!!

 

Dnes boli na pisomke z diskretnej tieto priklady:

 

1. Nech A je mnozina. |A|=n. X <= A  a  Y <= A. Najdite pocet

  usporiadanych dvojic (X,Y) takych ze plati

 

       |(X-Y) U (Y-X)|=1

 

2. Dokazte ze plati n!<=2(n/2)^n

 

3. Zostrojte sproste zobrazenie <0,1> na (0,1)

 

4. a) kolkymi sposobmi mozme rozdelit n rovnakych predmetov medzi k ludi ?

  b) to iste ale pozadujeme aby kazda osoba dostala minimalne r predmetov

     (0<r a kr<n) ... aspon myslim ze to tak bolo...

 

5. Dokazte ze ak A<>0 tak neexistuje zobrazenie f:A->0

 

6. Nech K<=N a nech B je taka mnozina ze |B|=n. Potom pocet kombinacii bez

  opakovania k-tej triedy z prvkov mnoziny B je rovny ...

  (ten ...sialeny vzorec je v poznamkach pri vete o kombinaciach bez opakovania).

 

Potom na ustnej som dostal tieto temy: 1. rovnost zobrazeni (vsetko okolo toho)

                                       2. priklad: Kolkymi sposobmi mozme do matice

                                          m x n zapisat cisla 1 a -1 tak, aby sucin

                                          cisel bol v kazdom riadku i stlpci +1 ???

                                          (vysledok je 2^((n-1)(m-1)) ).

 

Kua, chuapi, mam to za 3 !!! Ale som rad ze je to(man) za mnou...

CAUTE !!!

 

                                                        Peter

 

P.S.: Sorry vsetci co to uz mate spravene, ze vas s tymto otravujem, ale este

     je plno ludi co to este nemaju a tak si mozte vy*rat oko!!! :-))))))

 

------

Subject: Diskretna matika.

 

1. Urcte pocet kombinacii s opakovanim a najdite bijekciu medzi

kombinaciami s opakovanim z n prvkov a kombinaciami bez opakovania z n+k-1

prvkov.                  

2. dokazte MI       (  n  )n

                n!>( --- )

                   (  e  )

3.dokazte sumu - 6. priklad z tych 8 sum co boli na jednom tom papieri,

ktore nam dal Toman.

4.Nech A je neprazdna,|A|=n, nech X,Y su podmn. A, nech X prienik Y=prazdna

mnozina, kolko je vsetkych usp.dvojic (X,Y) ? {3 na n}

5.Cantor-Bernsteinova veta a ta lema k nej.

6.aky bude najvacsi koeficient vo vyraze

 a.)          10

       (a+b+c)

 

 b.)            14

       (a+b+c+d)

 

Vela stastia !

              Brano.

------

Subject: Re: Diskr.mat. 14.1. Toman

 

Drahy priatelia,

 

 na tejto skuske sa zrejme Toman rozhodol, ze ma ustve - skusal ma takmer 5

hodin. Priklady, ktore som mal na ustnej casti (nieco je podobne ako na

pisomnej)

 

1. Dokazte, ze 4*suma n nad 4k = 2^n + 2^(n/2)+1 * cos(n*pi)/4

 

2. Mame n Anglicanov a m Francuzov. Kolkymi sposobmi ich mozme rozostavit, aky

nebol ziaden Anglican ani ziaden Francuz osamoteny - tj. stoji vedla neho este

jeden sukmenovec.

 

3. Tranzitivny a reflexivno-tranzitinvy uzaver relacie, dokazy

 

4. Dokaz, ze ak B nie je prazdna mnozina, potom ani mnozina zobrazeni z A do B

nie je prazdna

 

5. Ak je A neprazdna mnozina a B prazdna, tak neexistuje zobrazenie z A do B

 

6. Aky je pocet kombinacii s opakovanim k-tej triedy z n prvkov

 

7. Najdi bijekciu medzi kombinaciami s op. k-tej triedy z n prvkov a

kombinaciami bez op. k-tej triedy z n+k-1 prvkov.

 

   A to bolo vsetko.

                                                Doctor

 

------

Subject: Diskr.mat. 8.1.98 ustna cast

 

Posielam vam teraz pre zmenu, co som dostal od pana Tomana v ustnej casti

skusky:

 

Dokaz:

n

---

\

/   (-1)^k (1/(k+1)) (n nad k) = (1/(n+1))    (da sa dokazat priamo)

---

k=0

 

n

---

\

/   ((-1)^(k-1))/k (n nad k) = 1+1/2+...+1/n  (na toto treba indukciu)

---

k=1

 

No a potom dava nejake doplnujuce veci k pisomke, napr. na pisomke sme

dokazovali, ze prazdne zobrazenie je zobrazenie, a on mi dal este navyse

dokazat, ze je bijektivne (celkom primitivny dokaz :)

 

A potom nasleduju rydzo teoreticke otazky:

 

Definuj kombinacie s opakovanim (cez zobrazenia, samozrejme).

Definuj rozklad mnoziny.

V akom su vztahu rozklad mnoziny a relacia ekvivalencie, vyslov zakladne vety a

dokaz (tie vety - ide o dve vety: o rozklade indukovanom relaciou a o relacii

indukovanej rozkladom).

 

No a potom nasleduje uz iba zapis do indexu (pripadne nie)...

 

        Zdravim

 

                Emil

------

Subject: Diskr.mat. 8.1.98 Toman

 

Tieto priklady boli na pisomke z diskretnej matiky 8.1.98 s Doc. Tomanom:

 

1. Dokazte, ze plati 0!=1

 

2. Zostrojte proste zobrazenie mnoziny A na mnozinu B, ked

  A={(x,y) patri do RxR, x^2+y^2<=1},B=<-1,1>x<-1,1>

 

3. Dokazte, ze plati (n nad k)=(n-2 nad k-2)+2*(n-3 nad k-2)+...+

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

 

4. Nech k,n1,...,nk patria do N+; n1+...+nk=n

  Nech |A|=n,|B|=k a B={b1,...,bk}

  Dokazte: Ak Pn1,...,nk je pocet tych surjekcii A na B, ze plati

  |f^-1({bj})|=nj, j=1,...,k, tak

 

  Pn1,...,nk = n!/(n1!.n2!. ... .nk!)

 

5. Zistite, ci nasledujuci kvantifikovany vyrok je tautologia pre lubovolne

  vyrokove formy a(x), b(x):

  Existuje x[a(x)=>b(x)]=>[Pre vsetky x a(x)=>Existuje x b(x)]

 

6. Dokazte, ze pocet kombinacii s opakovanim k-tej triedy z n roznych prvkov je

  (n+k-1 nad k).

 

        Vela stastia

 

                Zdravim

 

                        Emil

------

Subject: Diskretna zimny s. 96/97 (Toman)

 

Na zaciatok hadam staci, co sa pytal priatel Toman vlani na skuske (pisomka)

 

 

1)   Dokazte, ze plati

      k

     ---

     \   / n \ /   m   \  =  / m + n \

     /   \ r / \ k - r /  =  \   k   /

     ---

    r=0

2)   Najdite maximalnu hodnotu suctu

      s

     ---

     \   / n  \                        pri podmienkach

     /   \ ki /                        0 <= k1 < k2 < ... < ks <= n

     ---                                1 <= s <= n + 1

     i=1

3)   Dokazte, ze karteziansky sucin troch mnozin A = { E }, B = { E },

     C = { { E } } nie je asociativny.        [ E je prazdna mnozina ]

4)   Nech X je mnozina, Fi je niektory rozklad mnoziny X, T je relacia

     ekvivalencie na X. Nech Fi(T) je rozklad indukovany relaciou T a

     T(Fi) relacia ekvivalencie indukovana rozkladom Fi. Dokazte, ze

     Fi = Fi(T(Fi)) a T = T(Fi(T)) !

5)   Zostrojte proste zobrazenie mnoziny A na mnozinu B, ked

     A = { (x, y) parti R^2, x^2 + y^2 <= 1 }  a B = <-1, 1> x <-1, 1>.

6)   Nech f: X -> X. Potom

     a)  f je surjekcia <=> existuje take g: X -> X, ze f @ g = Ix (identita)

     b)  f je injekcia <=> existuje take g: X -> X, ze g @ f = Ix