http://ii.drx.pl/ 2026-05-23T19:00:11+02:00 http://ii.drx.pl/ http://ii.drx.pl/lib/images/favicon.ico text/html 2013-12-16T19:40:44+02:00 http://ii.drx.pl/matematyka_dyskretna:lista10m?rev=1387219244&do=diff Zadanie 1. Zadanie 2. a Nie istnieje, z lematu o uściskach dłoni. b Nie istnieje, ponieważ jeżeli popatrzymy na wierzchołek o stopniu 4, to on ma krawędź z każdym innym. W tym momencie mamy ciąg stopni 1,1,1,1,4. Nie możemy stworzyć 2 krawędzi, aby jeden wierzchołek miał stopień o 2 większy, nie poruszając stopni innych wierzchołków. Nie zrobimy też cyklu, bo to graf prosty. text/html 2009-12-20T15:23:45+02:00 http://ii.drx.pl/matematyka_dyskretna:lista11m?rev=1261319025&do=diff Zadanie 1. Zadanie 2. http://ii.yebood.com/viewtopic.php?t=4696 jako zadanie 1 Zadanie 3. Zadanie 4. Zadanie 5. Zadanie 6. Zadanie 7. http://ii.yebood.com/viewtopic.php?t=4625 jako zadanie 4. Zadanie 8. http://ii.yebood.com/viewtopic.php?t=4625 jako zadanie 5 text/html 2014-01-15T18:10:24+02:00 http://ii.drx.pl/matematyka_dyskretna:lista12m?rev=1389805824&do=diff Zadanie 1. Zadanie 2. Zadanie 3. <http://pl.wikipedia.org/wiki/Sortowanie_topologiczne#Algorytmy> Zadanie 4. Zadanie 5. Zadanie 6. Zadanie 7. Zadanie 8. Zadanie 9. Zadanie 10. Zadanie 11. Zadanie 12. Zadanie 13. Zadanie 14. Zadanie 15. text/html 2009-10-21T00:44:44+02:00 http://ii.drx.pl/matematyka_dyskretna:lista2m?rev=1256078684&do=diff Zadanie 1. Dla powały analogicznie; wychodzi n+1. Zadanie 2. Zadanie 3. Zadanie 4. a) dla i stosując metodę iteracyjną, mamy: ...... b) c) dla i znowu wystarczy trochę rozwinąć: ... Zadanie 5. a) text/html 2009-11-09T09:10:11+02:00 http://ii.drx.pl/matematyka_dyskretna:lista3m?rev=1257754211&do=diff Zadanie 1. Indukcja: Baza: OK. Krok: Dla parzystych: Dla nieparzystych: I co jest śmieszne, pokazaliśmy, że ze wzoru z sumą wynika związek rekurencyjny, a teraz pokażemy, że ze związku wynika wzór z sumą. Indukcja: Baza: OK. Krok: Dla n nieparzystych: Dla n parzystych: Załóżmy, że istnieje spełniające zależność rekurencyjną i . To znaczy, że istnieje takie , że . Weźmy więc takie i sprawdzmy wartość funkcji… text/html 2009-11-09T09:09:01+02:00 http://ii.drx.pl/matematyka_dyskretna:lista4m?rev=1257754141&do=diff Zadanie 1. def gcd(a,b): if b == 0: return a return gcd(b,a%b) def lcm(a,b): if a < 1 or b < 1: raise ValueError return (a/gcd(a,b))*b Nie mnożymy najpierw tylko najpierw dzielimy przez i potem mnożymy przez . Tym sposobem nigdy nie przetrzymujemy w zmiennej wartości większej od a lub b. text/html 2009-11-12T02:05:05+02:00 http://ii.drx.pl/matematyka_dyskretna:lista5m?rev=1257987905&do=diff Zadanie 5 Dowód z Dyskretnej Wrighta, za pomocą zasady szufladkowej Dirichleta: Pokażemy, że jeśli są całkowite, niekoniecznie różne, to suma jest wielokrotnością . Rozważmy funkcję zastosowaną do elementów zbioru .... Ponieważ , zasada szufladkowa pokazuje, że dwóm różnym liczbom i ze zbioru przyporządkowana jest ta sama wartość w . Skoro , to mamy , a zatem różnice i są wielokrotnościami liczby n. Jedna z tych różnic ma postać , co jest szukaną przez nas sumą będącą wielokrotno… text/html 2009-11-12T01:28:27+02:00 http://ii.drx.pl/matematyka_dyskretna:lista6m?rev=1257985707&do=diff Zadanie 1. Po lewej stronie równości mamy wybranie reprezentacji z n osób(może być od 1 do n osób) - to przedstawiamy przez . przedstawia wybranie osobowej reprentacji z osób. to możliwości wybrania szefa. Po prawej stronie: możliwości wybrania szefa i to moc zbioru potęgowego jakiegoś zbioru o mocy , czyli ilość podzbiorów ludzi bez szefa. text/html 2009-11-25T00:04:46+02:00 http://ii.drx.pl/matematyka_dyskretna:lista7m?rev=1259103886&do=diff Zadanie 1. Zadanie 2. Dla trywialnie zachodzi. Dla : Zadanie 3. . . Wygląda na to, że . Sprawdziłem na przypadków bazowych, teraz sprawdzę dla kroku. Zadanie 4. Zadanie 5. Zadanie 6. . Układamy anihilator . Więc postać zwarta to . Wyliczmy stałe. text/html 2013-12-03T22:16:37+02:00 http://ii.drx.pl/matematyka_dyskretna:lista8m?rev=1386105397&do=diff Zadanie 1. (gdyby chcieć policzyć to na palcach, można każdy z tych ułamków dla większych n przybliżyć jako 1) Zadanie 2. Przypomnę notację: oznacza funkcję tworzącą . , gdzie . --- Troche komentarza do metody szukania „wybiórczych” ciągów. Oczywiście można strzelić i trafić, ale można do tego podejść również bardziej metodycznie. Zwłaszcza, że tutaj mamy równoodległe elementy, a być może nie chcemy, żeby tak było, czy coś tam.… text/html 2010-01-28T07:32:32+02:00 http://ii.drx.pl/matematyka_dyskretna:lista9m?rev=1264660352&do=diff Zadanie 1. Legenda: w - wolf (wilk) c - cabbage (kapusta) g - goat (koza) Zadanie 2. <http://img101.imageshack.us/img101/6497/61717053zc2.jpg> Zadanie 3. <http://img101.imageshack.us/img101/6497/61717053zc2.jpg> Zadanie 4. Z handshake lemma wiemy, że suma stopni wierzchołków musi być parzysta. Wiemy też, że jak jakiś wierzchołek ma stopień to musi istniec n wierzchołków o stopniu conajmniej jeden(to sie odpowiednia zwiększa, jak mamy wiecej stopniowych wierzchołków.