Mój asystent
Zalogowany jako: Jeżyk ( Wyloguj )
Panel kontrolny · Zobacz nowe posty · Mój Asystent · Moi przyjaciele · 0 nowych PW
Nai - egzamin?, Pytanie tendencyjne ;) |
Jul 2 2006, 09:51 PM
Post
#36
|
|
Sierżant Grupa: pjwstk.edu.pl Domain Users Postów: 319 Dołączył: 11-October 04 Skąd: Radom/WaWa Nr użytkownika: 987 |
nie tylko Ty
|
|
|
Jul 2 2006, 11:27 PM
Post
#37
|
|
Szeregowy Grupa: pjwstk.edu.pl Domain Users Postów: 17 Dołączył: 8-December 05 Nr użytkownika: 1,742 |
Samo pokrycie macierzy nie jest raczej trudne wiec alg zachlannego nie bede opisywal.
Zacznijmy wiec od alg wychladzania. Musimy zdefiniowac funkcje celu : podzbior slownikow o jak nak najmniejszej ilosci (slownikow) i jak najwiekszej zawartosci (jak najwiecej jezykow, badz wszystkie o ile to mozliwe). Warto tez powiedziec na jakiej przestrzeni dzialamy. Dzialamy na gotowym zbiorze rozwazan. Nazwijmy go moze zborem X. Zawiera on wszystkie rozwiazania naszego problemu ,zarowno te dobre jak i kompletnie niedorzeczne. Rozwiazaniami sa zbiory slownikow. Teraz nalezy zdefiniowac sasiedztwo. Sasiedami w tym przypadku sa takie dwa rozwiazania ktore roznia sie o niewiele, w naszym przypadku mozemy zalozyc ze sasiadami sa zbiory slownikow rozniace sie o 1, no gora 2 slowniki Nalezy tez napisac o funkcji przystosowania czyli do czego tak na prawde dazymy w naszym algorytmie. Dazymy do otrzymania jak najmniejszego zbioru slownikow z jak najwieksza iloscia jezykow. Teraz opiszmy jak dzila sam algorytm wychladzania. Na poczatku losujemy jedno rozwazanie z naszego zbioru X, nazwijmy je x0. Nastepnie wsrod sasiadow tego rozwiazania losujemy jakies inne nazwijmy je x1. Teraz jesli x1 (nowo wylosowane) jest rozwiazaniem lepszym od naszego x0(aktualne) to OD RAZU przechodzimy do lepszego. Natomiast jesli x1 jest gorsze to losujemy mozliwosc przejsciado niego (pomimo ze jest gorsze), dajemy mu jakby szanse. Prawdopodobienstwo tego przejscia liczy sie z takiego smiesznego wzoru e do -( |f(x0) -f(x1)| ) /T , gdzie T to tak zwana temperatura. Algorytm ten na poczatku chodzi dosc haotycznie, czesto przechodzi do sasiadow (nawet tych gorszych), jednak wraz z uplywem czasu T jest zmniejszane, powoduje to malenie prawdopodobienstwa przejscia do gorszego sasiada. Po pewnym czasie nie jest juz mozliwe przejscie do gorszego sasiada tylko do lepszego. W miare uplywu czasu dojdziemy do w miare optymalnego rozwiazania naszego problemu. Alg wychladznia zawdzecza swoja nazwe wlasnie temu malejacemu T ktore powoduje ze skoki przestaja byc takie czeste az wlasciwie alg staje w miejscu |
|
|
Jul 2 2006, 11:30 PM
Post
#38
|
|
Szeregowy Grupa: pjwstk.edu.pl Domain Users Postów: 17 Dołączył: 8-December 05 Nr użytkownika: 1,742 |
dodam jeszcze oczywista rzecz mianowice nie napisalem ze jak przejdzie do lepszego to znowu losuje sasiada i teraz to co poprzednio bylo x1 staje sie x0 a nowowylosowany x1... drobiazg
|
|
|
Jul 2 2006, 11:48 PM
Post
#39
|
|
Starszy Szeregowy Grupa: pjwstk.edu.pl Domain Users Postów: 57 Dołączył: 19-October 04 Skąd: Wawa Nr użytkownika: 1,043 Wydział: Informatyka |
jest tylko male ale - czy mozemy zalozyc, ze znamy zbior rozwiazan naszego problemu (wszystkich ustawien ktore pokrywaja zbior) oznaczony przez Ciebie jako X
jesli tak to w porzadku, ale jesli nie (co wydaje mi sie bardziej prawdopodobne bo w koncu np. algorytm zachlanny dziala totalnie od zera, nie wiedzac nic, a chyba powinnismy operowac na tym samym poziomie abstrakcji) to znaczy, ze powinnismy oznaczyc przestrzen stanow jako zbior wszystkich mozliwych ustawien, nawet tych gdzie zalozmy bedzie tylko 1 slownik. Wtedy przy obliczaniu funkcji dla obecnie wybranego zbioru slownikow oraz dla wylosowanego sasiada powinnismy brac pod uwage juz nie tylko ilosc slownikow ale takze pokrycie procentowe wszystkich jezykow. To w sumie taka mala uwaga bo nie zmienia nic w tym, ze sam algorytm podany przez Ciebie jest jak najbardziej poprawny, a przy tej wersji wystarczy dac wzmianke o tym jak wyglad funkcja celu. Jeszcze jedno pytanie - czy mozna bedzie pisac w jezyku naturalnym podobnie jak teraz czy trzeba by to mocniej sformalizowac? |
|
|
Jul 2 2006, 11:54 PM
Post
#40
|
|
Szeregowy Grupa: pjwstk.edu.pl Domain Users Postów: 17 Dołączył: 8-December 05 Nr użytkownika: 1,742 |
Dobra teraz genetyczny.
Wydaje sie ze bardzo wiele mozna samemu przyjac gdyz kodowanie alg genetycznych nie jest w zaden sposob narzucone, tak na prawde najtrudniej jest wlasnie przeniesc jakosc problem na ciagi np. zero jedynkowe. Ja proponuje takie rozwiaznie: Jako osobnika przyjac jakis skonczony zbior zero jedynkowy, powiedzmy ze dlugosc to ilosc wszystkich slownikow. To czy dany osobnik zawiera slownik oznaczamy 1 a jesli nie ma to 0, taka tablica w javie gdzie indeksami sa rozne slowniki, a danymi to czy znajduje sie on w osobniku czy nie.Czyli nasz przykladowy osobnik wyglada mniejwiecej tak : 010011101 Przyjmijmy ze losujemy sobie z ogromnej liczby permutacji (wszystkich mozliwosci) opisania osobnikow jakies 100. mamy osobnika potrzebuje zdefiniowac teraz czym jest mutacja osobnika. Ja proponuje przyjac, ze co jakis czas (stosunkowo zadko) losowany jest jeden osobnik i zmieniamy w nim jeden bit, np losujemy osobnika 0100011101 i zmieniamy mu jeden bit 0->1 albo 1->0 pozycja oczywiscie losowana teraz zdefiniujmy sposob kopulacji. Przyjmijmy ze kopuluja ze soba dwa osobniki, mozna wiecej ale tak jest bardziej po ludzku losujemy sobie pary z naszego zbioru 100 osobnikow, teraz krzyzujemy je z pewnycm prawdopodobienstwem, czyli wynika z tego ze najpierw musza chciec;) Powiedzmy ze paruje sie co droga para. teraz opiszmy jak to wyglada wylosowalismy dwa osobniki 10100010 i 11011000 powiedzmy ze beda sie krzyzowac, teras sposob krzyzowania jest dowolny ja proponuje taki ze dzielimy je w polowie i "material genetyczny" polowa idze do potomka z jednego i droga polowa z kolejnego wyglada to tak rodzice: .................... dzieci 1010|0010..................10101000 jak widac zamienilem koncowki 1101|1000..................11010010 po takim parowaniu mamy dwoje dzieci no i dwoje rodzicow . Teraz widac ze po Tym wszystkim mamy sporo wiecej osobnikow, nalezy ich liczbe zredukowac. teraz przepuszczamy wszytkich przez stopien przystosowania, czyli jak dobrymi rozwiazaniami naszego problemu sa (dla naszego problemu jak najmniej slownikow i jak najwiecej jezykow), i wyniki zapisujemy na kole ruletki, im lepszy osobnik tym wiecej %wo zajmuje kola ruletki, gorsze mniej, teraz krecimy kolem 100 razy i wybieramy nowe osobniki z tych co mielismy. Widzimy ze czesciej przechodza te lepsze. One potem znowu sie paruja i czasem mutuja, z uplywem czasu osobniki staja sie coraz lepsze, dajac po pewnym czasie populacje niemalze optymalna, czyli taka ktore ma najmniej slownikow z jka najwieksza ilosci jezykow, im dluzej algorytm dzila tym lepsze uzyskuje wyniki Ten post edytował pat_atr Jul 3 2006, 12:06 AM |
|
|
Jul 2 2006, 11:55 PM
Post
#41
|
|
Szeregowy Grupa: pjwstk.edu.pl Domain Users Postów: 17 Dołączył: 8-December 05 Nr użytkownika: 1,742 |
zdazylem napisac przed 0:00
|
|
|
Jul 3 2006, 12:01 AM
Post
#42
|
|
Szeregowy Grupa: pjwstk.edu.pl Domain Users Postów: 17 Dołączył: 8-December 05 Nr użytkownika: 1,742 |
co za problem okreslic czym jest zbior X skoro to permutacja wszystkich slownikow, oczywiscie ze mozemy (a newt powinnismy) to zrobic.
Ja opisalem podobne zadnie u Trunga w taki sposob i dostalem max wiec spokojnie mona pisac takim jezykiem naturalnym, ja nie lubie pisac zbyt naukowo, bo malo kto potem to kuma prosilbym kogos o zamiesczenie notatek z sieci hopfilda bo nie moge tego nigdzie u siebie znalezc i nie pamietam jak tam sie wszystko liczylo Ten post edytował pat_atr Jul 3 2006, 12:50 AM |
|
|
Jul 3 2006, 12:12 AM
Post
#43
|
|
Starszy Kapral Grupa: pjwstk.edu.pl Domain Users Postów: 193 Dołączył: 18-October 04 Skąd: inąd Nr użytkownika: 1,030 Wydział: Informatyka |
Fajnie, a teraz czas na moje glupie pytania ... Jak na egzaminie opisze podobne zadanie w analogiczny sposob jak Ty to zrobiles to bedzie ok?
A drugie glupie pytanie: samym testem nie da sie zaliczyc egzaminu? :> Sorry ale naprawde niewiem -------------------- :)
|
|
|
Jul 3 2006, 12:18 AM
Post
#44
|
|
Szeregowy Grupa: pjwstk.edu.pl Domain Users Postów: 17 Dołączył: 8-December 05 Nr użytkownika: 1,742 |
Szczeze mowiac nie wiem, tez jestem na 2-gim roku i wiem tylko ze ma byc test, ktory juz mamy oraz zadanie tego typu co rozwiazalem, moze byc jeszcze jakies na liczenie. Jak wyglada rozklad punktow nie mam pojecia. Ale chyba nie jest trudno zaliczyc egzamin bo jakos uczniowie strszych lat nie ku..wią na wykladowce.
Ma ktos te notatki Ten post edytował pat_atr Jul 3 2006, 12:18 AM |
|
|
Jul 3 2006, 08:35 AM
Post
#45
|
|
Starszy Kapral Grupa: pjwstk.edu.pl Domain Users Postów: 193 Dołączył: 18-October 04 Skąd: inąd Nr użytkownika: 1,030 Wydział: Informatyka |
W alg zachłannym to po prostu w kazdym kroku bedziemy wybierac ten slownik, ktory obejmuje jak najwiecej nie pokrytych jeszcze jezyków, tak??
Kurde juz mi sie wszystko chrzani przed tym egz -------------------- :)
|
|
|
Jul 3 2006, 08:48 AM
Post
#46
|
|
Młodszy Chorąży Sztabowy Grupa: pjwstk.edu.pl Domain Users Postów: 696 Dołączył: 11-October 04 Skąd: Z wielu różnych miejsc... Nr użytkownika: 983 Wydział: Informatyka |
Czyli algorytm wychladzania dziala na gotowych rozwiazaniach?
Ja u Trunga napisalem, ze dziala na wierszach (tzn. wyszukuje coraz lepszy i zapamietuje taka sekwencje) i tez bylo dobrze. A w Twoim przypadku - dziala na rozwiazaniach, ale skad otrzymuje te rozwiazania? Przez dzialanie algorytmy zachlannego, czy jakiegos randomizowanego? No bo gdybysmy dali mu wszystkie mozliwe, to np. przy maciezy 50x50 komp by sie chyba zwiesil tworzac zbior tych rozwiazan... Przeciez to zlozonosc wykladnicza. To cos chyba nie tak, prawda? A w implementacji wazne jest, by Ci swiatlo w domu nie przygaslo, jak komputer liczy -------------------- |
|
|
Jul 3 2006, 10:03 AM
Post
#47
|
|
Sierżant Grupa: pjwstk.edu.pl Domain Users Postów: 319 Dołączył: 11-October 04 Skąd: Radom/WaWa Nr użytkownika: 987 |
pytanie za 100 punktów: czy problem pokrycia macierzy = problem plecakowy? bo chyba ten Stirlitz może udzwignąć max m jakaś wagę słowników, chyba że Bohaterowie Związku Radzieckiego to Pudziany
Ten post edytował Jezzo Jul 3 2006, 10:04 AM |
|
|
Jul 3 2006, 10:08 AM
Post
#48
|
|
Kapral Grupa: pjwstk.edu.pl Domain Users Postów: 138 Dołączył: 30-September 04 Skąd: Skierniewice / Warszawa Nr użytkownika: 945 Wydział: Informatyka |
CYTAT(Jezzo @ Jul 3 2006, 09:03 AM) pytanie za 100 punktów: czy problem pokrycia macierzy = problem plecakowy? bo chyba ten Stirlitz może udzwignąć max m jakaś wagę słowników, chyba że Bohaterowie Związku Radzieckiego to Pudziany Jak dla mnie Stirlitz to Stirlitz i swoje obowiazki ma. Nie interesuje go, ktore slowniki sa najbardziej wartosciowe. Musi miec wszystkie N potrzebnych jezykow i koniec. Wybiera najmniejsza liczbe slownikow, ktore te jezyki zawieraja i to wlasnie je zabiera. Jak sa za ciezkie, to Stirlitz _bardzo_ szybko musi sie stac silniejszy :-D -------------------- Pozdrawiam
|
|
|
Jul 5 2006, 12:58 PM
Post
#49
|
|
Szeregowy Grupa: pjwstk.edu.pl Domain Users Postów: 12 Dołączył: 28-March 04 Nr użytkownika: 524 |
Gdzie i kiedy mają być podane wyniki z egz z 3 lipca? może ktoś wie?
|
|
|
Jul 5 2006, 01:49 PM
Post
#50
|
|
Starszy Szeregowy Grupa: pjwstk.edu.pl Domain Users Postów: 57 Dołączył: 19-October 04 Skąd: Wawa Nr użytkownika: 1,043 Wydział: Informatyka |
|
|
|
Jul 5 2006, 06:27 PM
Post
#51
|
|
Chorąży Sztabowy Grupa: Admin Postów: 704 Dołączył: 8-December 05 Skąd: Warszawa Nr użytkownika: 1,743 Wydział: Sztuka Nowych Mediów |
ja zaliczylem
-------------------- http://zycietoniebajka.jogger.pl/
Porzuć GG na rzecz Jabbera !!! http://jabberfaq.info JID: [email protected] |
|
|
Jul 5 2006, 06:40 PM
Post
#52
|
|
Kapral Grupa: Moderatorzy Postów: 114 Dołączył: 22-September 04 Nr użytkownika: 920 |
|
|
|
Jul 5 2006, 08:38 PM
Post
#53
|
|
Starszy Szeregowy Grupa: pjwstk.edu.pl Domain Users Postów: 70 Dołączył: 7-January 05 Nr użytkownika: 1,263 |
a ja niezaliczylem ale dostalem 3 punkty i moge sie jutro u niego poprawiac osobiscie, jakich pytan sie mozna spodziewac??
|
|
|
Jul 6 2006, 12:21 AM
Post
#54
|
|
Młodszy Chorąży Sztabowy Grupa: pjwstk.edu.pl Domain Users Postów: 696 Dołączył: 11-October 04 Skąd: Z wielu różnych miejsc... Nr użytkownika: 983 Wydział: Informatyka |
Na pewno o NDTM i DTM, oraz o wszystkie materialy z wykladow.
Raczej nie daje pytan problemowych, takich jak np. na egzaminie, tylko jesli juz, to np. 'jak algorytm wychladzania zadziala dla problemu komiwojazera'... -------------------- |
|
|
Jul 6 2006, 10:43 AM
Post
#55
|
|
Sierżant Grupa: pjwstk.edu.pl Domain Users Postów: 319 Dołączył: 11-October 04 Skąd: Radom/WaWa Nr użytkownika: 987 |
z dużej chmury mały deszcz, egzamin był bardzo prosty, wystarczyło nauczyć się pytań które już były w księgarni, poprzeglądać slajdy z wykładów (a też dużo ich nie było) i rozwiązać proste zadanko
|
|
|
Wersja Lo-Fi | Aktualny czas: 23rd June 2008 - 01:06 AM |