IPB
X   Wiadomość
(Wiadomość zostanie automatycznie zamknięta w ciągu 2 sekund)
2 Stron V  < 1 2  
Reply to this topicStart new topic
> Nai - egzamin?, Pytanie tendencyjne ;)
Jezzo
post 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 smile.gif
Go to the top of the pageReport Post
 
+Quote Post
pat_atr
post 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
Go to the top of the pageReport Post
 
+Quote Post
pat_atr
post 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 tongue.gif
Go to the top of the pageReport Post
 
+Quote Post
Rol
post 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?wink.gif
Go to the top of the pageReport Post
 
+Quote Post
pat_atr
post 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 smile.gif 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
Go to the top of the pageReport Post
 
+Quote Post
pat_atr
post 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 laugh.gif
Go to the top of the pageReport Post
 
+Quote Post
pat_atr
post 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 wink.gif

prosilbym kogos o zamiesczenie notatek z sieci hopfilda bo nie moge tego nigdzie u siebie znalezc i nie pamietam jak tam sie wszystko liczylo dry.gif

Ten post edytował pat_atr Jul 3 2006, 12:50 AM
Go to the top of the pageReport Post
 
+Quote Post
Bart
post 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 tongue.gif... 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 wink.gif


--------------------
:)
Go to the top of the pageReport Post
 
+Quote Post
pat_atr
post 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 wink.gif 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 unsure.gif

Ten post edytował pat_atr Jul 3 2006, 12:18 AM
Go to the top of the pageReport Post
 
+Quote Post
Bart
post 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 tongue.gif


--------------------
:)
Go to the top of the pageReport Post
 
+Quote Post
Lucky
post 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 biggrin.gif


--------------------
Pozdrawiam
Lucky
[email protected]
Go to the top of the pageReport Post
 
+Quote Post
Jezzo
post 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 smile.gif

Ten post edytował Jezzo Jul 3 2006, 10:04 AM
Go to the top of the pageReport Post
 
+Quote Post
Bulzaj
post 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 smile.gif
*


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
Go to the top of the pageReport Post
 
+Quote Post
zyza
post 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?
Go to the top of the pageReport Post
 
+Quote Post
Rol
post 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



http://www.jakubw.pl/zajecia/nai/Wyniki_egz_2006.pdf
Go to the top of the pageReport Post
 
+Quote Post
johnek
post 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 biggrin.gif


--------------------
Go to the top of the pageReport Post
 
+Quote Post
radom
post Jul 5 2006, 06:40 PM
Post #52


Kapral
*

Grupa: Moderatorzy
Postów: 114
Dołączył: 22-September 04
Nr użytkownika: 920



CYTAT(johnek @ Jul 5 2006, 06:27 PM)
ja zaliczylem biggrin.gif
*


laugh.gif laugh.gif
Go to the top of the pageReport Post
 
+Quote Post
r666
post 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 biggrin.gif i moge sie jutro u niego poprawiac osobiscie, jakich pytan sie mozna spodziewac??
Go to the top of the pageReport Post
 
+Quote Post
Lucky
post 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'...


--------------------
Pozdrawiam
Lucky
[email protected]
Go to the top of the pageReport Post
 
+Quote Post
Jezzo
post 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 smile.gif
Go to the top of the pageReport Post
 
+Quote Post

2 Stron V  < 1 2
Fast ReplyReply to this topicStart new topic
1 Użytkowników czyta ten temat (0 Gości i 0 Anonimowych użytkowników)
1 Zarejestrowanych: Jeżyk

 



RSS
Wersja Lo-Fi Aktualny czas: 23rd June 2008 - 01:06 AM