Forum Informatyka UJ forum Strona Główna Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
 
 FAQFAQ   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy   GalerieGalerie   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Pytania dot. MD - przygotowania na poprawke.
Idź do strony 1, 2  Następny
 
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 2 rok / 3 semestr - Matematyka Dyskretna
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1601
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Wto 17:26, 13 Lut 2007    Temat postu: Pytania dot. MD - przygotowania na poprawke.

Mam pytan kilka odnosnie MD:

1. O co chodzi z zagadnieniem "multiplikatywność modulo n", którą Robson wymienił w swojej rozpisce?

2. Co to jest zredukowany zbiór reszt - grupa z funkcji Eulera?

Z góry dzięki za support :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Wto 21:23, 13 Lut 2007    Temat postu: Re: Pytania dot. MD - przygotowania na poprawke.

1. Domyślam się, że Robsonowi chodziło o grupy multiplikatywne mod n, które są parą zredukowanego zbioru reszt i mnożenia - (ZZR, *).

2. ZZR to zbiór liczb całkowitych dodatnich mniejszych od n względnie pierwszych z n ;) .
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1601
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Wto 22:30, 13 Lut 2007    Temat postu:

Dobra, dziękówa Spectro ;]
A mam pytanie, jak interpretować t-konfigurację (v, k, r[t]) ?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Wto 23:03, 13 Lut 2007    Temat postu:

v - ilość elementów w zbiorze X
b - ilość interesujących nas podzbiorów (bloków) zbioru X (pomocniczo)
k - liczność każdego z podzbiorów (bloków) S1, S2, ..., Sb
r[t] - ilość wystąpień każdego podzbioru t-elementowego zbioru X jako podzbioru zbiorów S1, S2, ..., Sb.

Jeżeli istnieje zestaw bloków S1, S2, ..., Sb, to mamy t-konfigurację :) .

Konfiguracja (v, k, r) jest 1-konfiguracją.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1601
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Śro 13:43, 14 Lut 2007    Temat postu:

Dzieki Spectro raz jeszcze, jednakże widze, że chętny jesteś do myślenia, zatem specjalnie dla Ciebie znalazłem kolejne pytanie :P

Jak interpretować grupę diheralną? Tak na chłopski rozum D6 to jest co? Możemy to traktować poprostu jak sześciokąt foremny?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Śro 15:25, 14 Lut 2007    Temat postu:

Tu chyba chodzi o trójkąt, bo wzory są D_2*n

Tak mi się coś wydaje ;)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fen
zielony żul



Dołączył: 22 Lut 2006
Posty: 946
Przeczytał: 0 tematów

Skąd: Bochnia

PostWysłany: Śro 16:02, 14 Lut 2007    Temat postu:

@Skrobocik... masz chyba rację, ale może ktoś by to mógł wszystko ładnie i przejrzyście wyjaśnić :)

Spectro?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1601
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Śro 16:05, 14 Lut 2007    Temat postu:

Wlasnie ja tez chyba - wszyscy chyba, a nikt nie wie dokladnie :P To jak spectro? :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fen
zielony żul



Dołączył: 22 Lut 2006
Posty: 946
Przeczytał: 0 tematów

Skąd: Bochnia

PostWysłany: Śro 16:11, 14 Lut 2007    Temat postu:

"chyba" to ostatnio modne słowo... chyba :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Śro 16:44, 14 Lut 2007    Temat postu:

Jeżeli n >= 3, to grupa dihedralna D_2*n jest grupą symetrii n-kąta ;) .

2*n dlatego, że zawiera 2*n elementów ;) . Czyli: n obrotów (w tym identyczność - obrót o 0) i n symetrii osiowych (jeżeli n nieparzyste, to wszystkie osie przechodzą przez wierzchołek i przeciwległą krawędź; jeżeli n parzyste, to n/2 osi przechodzi przez przeciwległe krawędzie i n/2 przez przeciwległe wierzchołki).
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Yoter
zielony żul



Dołączył: 19 Lis 2005
Posty: 1033
Przeczytał: 0 tematów

Skąd: Gościeradów

PostWysłany: Śro 16:44, 14 Lut 2007    Temat postu:

D_2*n to grupa obrotów i symetrii n-kata foremnego. chyba. grupa obrotów jest tutaj przy okazji grupą cykliczną. chyba.

EDIT: ubiegł mnie :-k


Ostatnio zmieniony przez Yoter dnia Śro 16:53, 14 Lut 2007, w całości zmieniany 1 raz
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Śro 16:50, 14 Lut 2007    Temat postu:

Yoter napisał:
grupa obrotów jest tutaj przy okazji grupą cykliczną. chyba.

Na pewno :) . Jest ona generowana przez obrót o 2*PI/n .
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Stasiu
zielony żul



Dołączył: 16 Lis 2005
Posty: 919
Przeczytał: 0 tematów

Skąd: krk

PostWysłany: Sob 15:26, 17 Lut 2007    Temat postu:

help... Nie bylo mnie na tych cwiczeniach i dalej nie wiem jak sie do tego zabrac :( To zad. z I kolokwium:
Kod:
Rozloz na czynniki pierwsze (3^15)+1 = 1434908


EDIT: w zadaniach na stronie znalazlem ogolniejszy przyklad:
Kod:
Podaj rozkład
(a) (b^n) − 1
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Sob 15:57, 17 Lut 2007    Temat postu:

@Stasiu:
Korzystasz z twierdzenia:

Jeżeli p - pierwsze i p|b^n+1, to:
1) p|b^d+1, gdzie d|n i 1<=d<n
LUB
2) p = 1 (mod 2*n).

W praktyce:
Najpierw rozważasz dzielniki:
3^1+1 = 4 = 2 * 2,
3^3+1 = 28 = 2 * 2 * 7,
3^5+1 = 244 = 2 * 2 * 61.
Zauważasz (np. przy pomocy kalkulatora), że 2^2 = 4, 7 i 61 dzielą 3^15+1.

1434908/(2^2*7*61) = 8401

Pozostałe dzielniki przystają do 1 (mod 2*15=30).
Sprawdzasz po kolei 31 (działa: 8401/31 = 271), 61 (drugi raz nie działa), 91, 121, 151 - 3 ostatnie nie działają, zatem wynosimy, że 271 jest pierwsze.

3^15+1 = 2^2*7*31*61*271


Dla b^n-1 pomocne może się okazać inne, podobne twierdzenie:

Jeżeli p - pierwsze i p|b^n-1, to:
1) p|b^d-1, gdzie d|n i 1<=d<n
LUB
2) p = 1 (mod n) ORAZ jeżeli p>2, n = 2*k+1, k - całkowite nieujemne, to p = 1 (mod 2*n).
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1601
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Sob 17:06, 17 Lut 2007    Temat postu:

Spectro napisał:
Korzystasz z twierdzenia:
Jeżeli p - pierwsze i p|b^n+1, to:
1) p|b^d+1, gdzie d|n i 1<=d<n
LUB
2) p = 1 (mod 2*n).


Spectro: w 1 ma byc dla kazdego takiego dzielnika, czy ze istnieje jeden taki dzielnik ?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Stasiu
zielony żul



Dołączył: 16 Lis 2005
Posty: 919
Przeczytał: 0 tematów

Skąd: krk

PostWysłany: Sob 17:59, 17 Lut 2007    Temat postu:

czyli jesli mamy:
(2^13)-1 = 8191
to:
13 jest pierwsza, wiec jedynym dzielnikiem ktory spelnia (1) jest 1
=>
p | (2^1) - 1 => p | 1 (czyli nic nam to nie daje)

czyli mamy n = 13 = 2*k+1, p > 2 (2)
=>
p = 2(mod 2*n)
p1 = 27 (nie dzieli 8191)
p2 = 53 (nie dzieli 8191)
p3 = 79 (nie dzieli 8191)
p4 = 105 (> sqrt(8191) )
=>
(2^13)-1 jest pierwsza?

EDIT: i ja mam jeszcze jedna prosbe:
Kod:
Rozwiaz układy kongruencji
(a) x = 5mod 4
x = 7mod 11

Ktos podalby rozumowanie krok po kroku? Z gory wielkie dzieki.

EDIT2: ile osob pisze kolosa we wt.? moze jakos w poniedzialek sie spotkamy na ii i jeszcze cos porozkminiamy?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Nie 14:01, 18 Lut 2007    Temat postu:

exeman napisał:
Spectro: w 1 ma byc dla kazdego takiego dzielnika, czy ze istnieje jeden taki dzielnik ?

Istnieje co najmniej jeden :) . Popatrz na przykład.

Stasiu napisał:
(2^13)-1 jest pierwsza?

Tak, rozumowanie prawidłowe.

Stasiu napisał:
]Ktos podalby rozumowanie krok po kroku? Z gory wielkie dzieki.

Spróbujemy na 2 sposoby rozwiązać układ:
x = 5 = 1 (mod 4)
x = 7 (mod 11)

I. Mamy układ równań x = k_i (mod m_i) dla i = 1, ..., n oraz NWD(m_1, ..., m_n) = 1. Na postawie chińskiego tw. o resztach istnieje dokładnie jedno rozwiązanie modulo m_1*...*m_n.
Wyliczamy M_i = (m_1*...*m_n)/m_i dla każdego i. Znajdujemy takie liczby a_i oraz b_i, że a_i*m_i + b_i*M_i = 1. Wtedy x = b_1*k_1*M_1 + ... + b_n*k_n*M_n (mod m_1*...*m_n).

M_1 = 11, M_2 = 4
(a_1, b_1) = (3, -1), (a_2, b_2) = (-1, 3)
x = (-1)*1*11 + 3*7*4 = 73 = 29 (mod 44)

II. Mamy układ równań x = k_i (mod m_i) dla i = 1, ..., n. Istnieje dokładnie jedno rozwiązanie modulo NWW(m_1, ..., m_n), jeżeli dla każdego i, j ze zbioru {1, ..., n}, i !=j, zachodzi: NWD(m_i, m_j) | k_i-k_j. Wpp. rozwiązań nie ma.
Niech K_1 = k_1, M_1 = m_1. Dla i od 1 do n-1 rozwiązujemy równanie:
M_i*x + K_i = k_(i+1) (mod m_(i+1))
W rezultacie otrzymujemy: x = a (mod m_(i+1)).
x = M_i*a + K_i = K_(i+1) (mod M_(i+1) = NWW(M_i, m_(i+1)))
Po n-1 krokach otrzymujemy x = K_n (mod M_n = NWW(m_1, ..., m_n))

11*x + 7 = 1 (mod 4) => 3*x = 2 (mod 4) => x = 2 (mod 4)
x = 11*2 + 7 = 29 (mod 44)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Stasiu
zielony żul



Dołączył: 16 Lis 2005
Posty: 919
Przeczytał: 0 tematów

Skąd: krk

PostWysłany: Nie 16:18, 18 Lut 2007    Temat postu:

Wielkie dzieki Spectro :D
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Krisowski
pijak



Dołączył: 05 Mar 2006
Posty: 218
Przeczytał: 0 tematów

Skąd: z nikąd

PostWysłany: Pon 19:48, 19 Lut 2007    Temat postu:

Czy klika o liczności n ma liczbę chromatyczną X(K) = n?
Czy jeśli graf ma liczbę chromatyczną X(G) = n to zawiera klikę o liczności n?
O co chodzi w problemie Ramseya z listy Robsona?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Pon 21:22, 19 Lut 2007    Temat postu:

Krisowski napisał:
Czy klika o liczności n ma liczbę chromatyczną X(K) = n?

Tak. Każdy z wierzchołków sąsiaduje z n-1 innymi wierzchołkami, więc musi mieć kolor odróżniający go od innych.

Krisowski napisał:
Czy jeśli graf ma liczbę chromatyczną X(G) = n to zawiera klikę o liczności n?

Nie. Weź pięciokąt (foremny). Liczba chromatyczna - 3. Gdzie klika 3-elementowa?

Krisowski napisał:
O co chodzi w problemie Ramseya z listy Robsona?

"Wzkaż najmniejszą liczbę naturalną r(m, n), dla której każdy graf o r(m, n) wierzchołkach zawiera (jako podgraf) klikę m-elementową lub antyklikę n-elementową."

Wiemy, że r(3, 3) = 6. Ale dla ogólnych wartości m i n możemy tylko podać górne oszacowania...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Krisowski
pijak



Dołączył: 05 Mar 2006
Posty: 218
Przeczytał: 0 tematów

Skąd: z nikąd

PostWysłany: Wto 13:52, 20 Lut 2007    Temat postu:

Cytat:
liczenie wzoru "skroconego" ze wzoru rekurencyjnego

Co to właściwie oznacza?
Co to jest równanie stowarzyszone?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Wto 14:34, 20 Lut 2007    Temat postu:

Krisowski napisał:
Co to właściwie oznacza?

Po prostu chodzi o zamianę wzoru w postaci rekurencyjnej na wzór bezpośredni ;) .

Krisowski napisał:
Co to jest równanie stowarzyszone?

Równanie stowarzyszone (inaczej: charakterystyczne) to równanie powiązane ze wzorem rekurencyjnym. Wzorowi: u_(n+k) + a_1*u_(n+k-1) + ... + a_k*u_n = 0 odpowiada równanie: t^k + a_1*t^(k-1) + ... + a_k = 0.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Krisowski
pijak



Dołączył: 05 Mar 2006
Posty: 218
Przeczytał: 0 tematów

Skąd: z nikąd

PostWysłany: Wto 15:17, 20 Lut 2007    Temat postu:

Dzięki, dobrze wiedzieć, że to coś o czym mam jakieś pojęcie :)

Wie ktoś jakie są funkcje tworzące dla:
en - ilość podziałów o parzystej liczbie składników;
on - ilość podziałów o nieparzystej liczbie składników ?

Gdzieś znalazłem, że qn = en - on ma funkcje tworzącą:
Kod:
Q(x) = 1 - x - x^2 + x^5 + x^7 - x^12 - x^15 + ...
ale nie mogę znaleźć funkcji tworzących dla en i on :P

Robson napisał:
Jakies tam zależności miedzy podziałami (na parzysta liczbe a nieparzystą itp.)
Jakie jeszcze mogą być te zależności?
Robson napisał:
przykłady przekształcen funkcji tworzących w inne
... i jeszcze to :) .
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
aaa
pijak



Dołączył: 21 Lis 2006
Posty: 448
Przeczytał: 0 tematów


PostWysłany: Wto 16:24, 20 Lut 2007    Temat postu:

[deleted]

Ostatnio zmieniony przez aaa dnia Sob 3:21, 17 Lis 2007, w całości zmieniany 1 raz
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Krisowski
pijak



Dołączył: 05 Mar 2006
Posty: 218
Przeczytał: 0 tematów

Skąd: z nikąd

PostWysłany: Wto 18:43, 20 Lut 2007    Temat postu:

Pandunia napisał:
z en o on wiem tyle ze prawie zawsze sa sobie rowne i tylko w nielicznych przypadkach trzeba costam z nimi kombinowac. tak samo zaznaczylem na egzaminie.

Wydaje mi się, że tych przypadków jest mimo wszystko nieskończenie wiele. Tam było, że:
Kod:
en - on
= (-1)^m, dla n = 1/2m(3m+-1); m >= 1
= 0, w przeciwnym przypadku
Tutaj nie można więc chyba powiedzieć, że prawie zawsze (bo prawie to mówi, że dla wszystkich poza co najwyżej skończoną liczbą). Jak się mylę, to niech mnie ktoś poprawi :D .
Powrót do góry
Zobacz profil autora
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 2 rok / 3 semestr - Matematyka Dyskretna Wszystkie czasy w strefie EET (Europa)
Idź do strony 1, 2  Następny
Strona 1 z 2

 
Skocz do:  
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach

fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
Regulamin