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
Prednášky sú zverejnené v súlade s ustanovením § 33 ods. 1 písm. c) zákona č. 618/2003 v znení neskorších prepisov a teda výhradne na informačné účely. Prosíme Vás aby ste všetky porušenia autorských práv bezodkladne ohlásili administrátorovi. Podmienky používania
