Informatyka UJ forum

pawell

Czy moze ktos ma kolokwium z tamtego roku to drugie z WDM.. bo moze byc calkem przydatne podczas przygotowan... ;] Ewentualnie moze ktos je pisal i mialby ochote sie wypowiedziec co tak mniej wiecej ( lepiej wiecej ;) ) bylo...
Z góry dzięki za odpowiedz... Pozdro...

flower

tak mniej wiecej to nie pamietam, wiem ze bylo zdecydowanie wiecej zer niz z pierwszego :) ale grunt to sie nie przejmowac :)

enjoy :*

pawell

hehe no o tym ze wiecej zer to zdazylem sie dowiedziec... ;] A co do przejmowania sie to tez zrozumialem ze tutaj trzeba patrzec na wszystko z przymruzeniem oka bo inaczej czlowiek nie wyrobi ... ;] chociaz co ja tam jeszcze wiem o studiowaniu ... ;]

kg86

nie dolujcie mnie :P

oinopion

A tak w ogóle, to jaki jest zakres materiału na drugim kolosie? Teraz uczę się wszystkiego po kolei, ale może toza dużo? ;)

flower

pewnie funkcje i posety, czyli niemal wszystko :)

ostoj

najprawdopodobniej funkcje, porzadki i teoria mocy

Paweł Str. · Gość

Na pewno było takie zadanie:
pokazać, że dla każdej bijekcji f na zbiorze skończonym isnieje takie n, że f^n==identyczność, gdzie f^n oznacza n-krotne złożenie f ze sobą;
oraz stwierdzić, czy to twierdzenie jest prawdziwe dla zbiorów nieskończonych.

Madras

Ciekawe, czy można stwierdzić, że bijekcja na zbiorze skończonym jest permutacją i napisać, że na algebrze było dowodzone, że każda permutacja jest skończonego rzędu ;D.

muciu

Wydaje mi się że nie trzeba sięgać do algebry, bo rozwiązanie w brew pozorom nie jest takie trudne:
skoro f-jest bijekcją to
a) f(x_0)=x_0 (dla jakichś el. dziedziny)
b) albo f(x_0)<>x_0.
jeżeli wezmiemy przypadek a), to wartosc kolejnych iteracji funkcji dla el. dziedziny posiadających włąsność (a) bedzie zawsze stala i rowna f^i(x_0)=x_0 dla kazdego i, jezeli wezmiemy przypadek b), to wartosc kolejnych zlozen funkcji dla danego x_0 bedzie rózna od siebie i od x_0 (poniewaz funkcja jest bijekcja), ale dziedziną jest zbior skonczony, zatem kiedys wróci na element x_0. Wystarczy wziąść takie n_0, że f^(n_0)(x_0)=x_0 /wiemy ze takie istnieje :):)/ i taką operację nalezy wykonać dla kazdego elementu dziedziny. By dokończyc dowód, wystarczy wziąść nww(n_0,...,n_k) i ... gotowe: f^nww(n_0,...,n_k)=id.
Moze dowód zaczerpnięty z algebry jest łatwiejszy, ale ... ;-)

ostoj

a ze sie tak zapytam gdzie i kiedy byl dowod z algebry? bo jakos patrze w notatki z wykladow, notatki z cwiczen i chyba niedowidze...

Madras

No to może i nie było ;]. Ale gdzieś mi się coś takiego o uszy obiło...

ostoj

no chyba ze robiliscie to na cwiczeniach i nie macie cwiczen z dr forys :)

Madras

Mamy z dr Foryś... Ale chyba akurat to stwierdzenie padło na ćwiczeniach z WdM'u ;]. Poza tym przez indukcję nie jest trudno to udowodnić ;].

Paweł Str. · Gość

To, co zrobiliście, to właśnie mniej więcej ten dowód, jaki robiliśmy na algebrze (i który zrobiłem na kolokwium).

Pozostaje pokazać, że to nie działa dla nieskończonych.

Btw. mgr Jakub Kozik podawał (już po fakcie) taki dowód - brzydszy, bo niekontstruktywny, ale jednak dowód:

Niech dla każdego n f^n!=I.

Zatem nie może być takich m,n m!=n, że f^m==f^n. Wtedy bowiem (załóżmy, że m>n) f^(m-n) byłoby identycznością (trzeba tu wykazać pewne ciekawe własności składania bijekcji).

camensky

jakby kogos interesowalo kolokwium z 2003 to podaje link, bo zeszlorocznego chyba nigdzie nie ma.

[link widoczny dla zalogowanych]

Madras

http://www.matinfuj.fora.pl/viewtopic.php?p=31&#31 ;P

muciu

ostoj

nie, bo nie wygenerujesz x0, a to ma byc suriekcja z racji bijektywnosci
ale jako kontrprzyklad moze chyba posluzyc funkcja:
f(0)=2^0=1
f(1)=2^1=2
f(2)=2^2=4
f(4)=2^4=16
f(16)=2^16=x
f(x)=2^x
......
a tym ktore nie zostaly wykorzystane jako argument przyporzadkowac te ktore nie zostaly wykorzystane jako wartosc i zrobic to przyporzadkowanie po kolei jak leci

camensky

ok sorry, tak myslalem ze gdzies juz to padlo... tak na wszelki wypadek zapodalem :)

Gość

Moim zdaniem najprostszy przykład:

f(0)=1
f(n)=n-2 dla n parzystych
f(n)=n+2 dla n nieparzystych
"nieskończony łańcuch rowerowy".
Jeżeli ktoś nie widzi, to polecam rozrysować to w ten sposób, że nieparzyste liczby ma się w jednej linii, parzyste w drugiej i połączyć strzałkami.

Znowu podam rozwiązanie, które zaprezentował J.Kozik:
f(n)=g-1(g(n)+1), gdzie g(n) to bijekcja między naturalnymi a całkowitymi (N->Z). Wiemy, że ona istnieje. W praktyce, jeżeli użyje się "typowej" bijekcji, dostanie się to, co zaprezentowałem.

Przykład ostoja wydaje mi się dobry.