Informatyka UJ forum

exeman

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 :)

Spectro

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 ;) .

exeman

Dobra, dziękówa Spectro ;]
A mam pytanie, jak interpretować t-konfigurację (v, k, r[t]) ?

Spectro

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ą.

exeman

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?

Skrobocik

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

Tak mi się coś wydaje ;)

Fen

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

Spectro?

exeman

Wlasnie ja tez chyba - wszyscy chyba, a nikt nie wie dokladnie :P To jak spectro? :P

Fen

"chyba" to ostatnio modne słowo... chyba :P

Spectro

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).

Yoter

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

Spectro

Stasiu

help... Nie bylo mnie na tych cwiczeniach i dalej nie wiem jak sie do tego zabrac :( To zad. z I kolokwium:

Spectro

@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).

exeman

Stasiu

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:

Spectro

Stasiu

Wielkie dzieki Spectro :D

Krisowski

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?

Spectro

Krisowski

Spectro

Krisowski

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ą:

aaa

[deleted]

Krisowski