czyli czego się możecie ode mnie nauczyć
Bicykl Hamiltona 2010-10-22 19:10
 Oceń wpis
   
_-¯ W dzisiejszym wpisie chciałbym przybliżyć P.T. Czytelnikom mało znaną klasę algorytmów, określanych jako ,,algorytmy a-moralne''. Ojcem tej dziedziny jest zapewne doskonale znana Państwu postać profesora Erwina Donalda Charapa, który szczegółowo opisał ją w swoim dziele ,,The Art of A-moral Computer Programming''. Miałem niewątpliwą przyjemność uczestniczyć w tworzeniu wspomnianej pozycji, a teraz - korzystając z nadarzającej się okazji - chciałbym rozpocząć cykl artykułów poświęconych właśnie a-moralistyce (jak w skrócie określa się algorytmikę a-moralną).

_-¯ Na wstępie kilka słów wyjaśnienia, czym właściwie są algorytmy a-moralne? Główną właściwością tej grupy algorytmów jest ich całkowita nieprzydatność do rozwiązywania danego problemu, czy nawet wręcz szkodliwość. Algorytmy a-moralne nie tylko nie prowadzą do rozwiązania zadania, ale wręcz to rozwiązanie utrudniają. Najprostszym przykładem takiego algorytmu jest ,,a-moral algorithm for optical character recognition'', z sukcesem wykorzystywany w systemach captcha.

captcha_banner

Umieszczony powyżej obrazek to przykład, jak zastosowany algorytm wpływa na postać danych wejściowych (oryginalny tekst znajduje się w nawiasach kwadratowych). Jak widać efektem działania jest nie tylko nie wyprodukowanie poprawnie rozpoznanego tekstu, ale jeszcze zmodyfikowanie danych wejściowych tak, by były możliwie nieużywalne dla innych systemów OCR. Jeden z najbardziej znanych algorytmów tego typu, znany pod nazwą CPW (od nazwisk twórców: Charap-Pratt-Whitney) nie tylko przekształca źródło danych, lecz dodatkowo wysyła obraźliwe e-maile lub stara się tak odcyfrować tekst by ułożyć obraźliwy wierszyk. Dla przykładu z powyższego obrazka zamiast spodziewanego słowa ,,captcha'' wyjściem był następujący tekst:

Na górze róże
Na dole fiołki
Charyzjusz Chakier
Jest głupi jak but i śmierdzi mu z butów!!!111jedenjedenjeden

Złożoność obliczeniowa algorytmu CPW wynosi O(n*log(k*n)), gdzie k jest liczbą słów generowanego wierszyka, zaś n stałą większą 1.5 raza od t, gdzie t jest czasem który użytkownik jest w stanie czekać na wyniki działania programu. Jak widać algorytm jest wysoce wydajny i prowadzi do irytacji zarówno samego użytkownika, jak i jego otoczenia. Jako ciekawostkę dodam fakt, że CPW często używa powtórzeń wyrazów w tej samej, lub w sąsiadujących frazach, w celu spotęgowania wrażenia - zatem zwrot ,,głupi jak but i śmierdzi mu z butów'' wcale nie jest przypadkowy, choć zapewne mniej wydajne algorytmy użyłyby ,,głupi jak but i śmierdzą mu stopy'', co jednak nie jest aż tak niedobre jak w przypadku CPW.

_-¯ Dzisiaj jednak chciałem omówić inny algorytm a-moralny, dotyczący znajdowania bicyklu Hamiltona w grafie. Na wejściu pojawia się spójny graf, zaś algorytm ma znaleźć w nim taki bicykl, na którym Hamilton byłby w stanie objechać wszystkie wierzchołki, odwiedzając każdy dokładnie jeden raz. Rozwinięciem problemu bicyklu Hamiltona jest bicykl komiwojażera, gdy dany jest skierowany graf ważony, zaś komiwojażer ma osiągnąć na swoim bicyklu czas nie gorszy od każdego innego osiągniętego przez Hamiltona na dowolnym znalezionym przez siebie bicyklu. Oczywiście nie należy również dopuścić do tego, by Hamilton wziął bicykl komiwojażera. Oto jak należałoby się do tego zabrać z punktu widzenia a-moralistyki:
1. Napisać algorytm który w pierwszym kroku kradnie pierwszy napotkany bicykl.
2. Używając tego bicyklu ucieka przed Hamiltonem, zachowując na n-tej krawędzi grafu prędkość co najmniej vn, które to vn jest minimalną prędkością potrzebną do przybycia do k-tego wierzchołka zanim Hamilton
osiągnie wierzchołek k-1. W k-tym wierzchołku algorytm porzuca bicykl spuściwszy z jego opon powietrze i kradnie następny.
3. Punkt drugi powtarzany jest tak długo, aż ze wszystkich opon wszystkich bicykli w grafie zostanie spuszczone powietrze.
Przykładem zastosowania w/w algorytmu było wprowadzenie go do komputerów teamu McLarena podczas treningu przed Grand Prix Japonii.
_-¯ Jak wspomniałem, rozwinięciem problemu poszukiwania bicyklu Hamiltona jest problem komiwojażera. Normalne rozwiązanie polega na wyznaczeniu bicyklu na którym komiwojażer w najkrótszym czasie przejedzie przez wszystkie miasta/wierzchołki grafu. Kiedy do problemu zastosowałem ,,a-moral algorithm for traveling salesman problem'' mój komputerowy komiwojażer najpierw zapomniał wziąć ze sobą towaru, potem udał się nie do tych miast które miał odwiedzić, na końcu zaś został napadnięty w pociągu przez szalikowców, pobity i okradziony. Nie tylko więc nie odwiedził żadnego z wyznaczonych punktów, ale również stracił cały dorobek życia (wirtualnego, ale jednak).

_-¯ Na szczęście istnieje prosta metoda posługiwania się algorytmami a-moralnymi tak, by służyły zamiast szkodzić. Wystarczy po prostu używać ich do rzeczy wręcz przeciwnych niż te, których dotyczą, np. ,,a-moral algorithm for picture distorting'' znakomicie nadaje się do rozpoznawania tekstów i obrazów. Ale o tym napiszę w kolejnym wpisie...

PS: Czytelników serdecznie zapraszam do zapoznania się z opowiadaniem Zgrzytanie, pierwszym fan-ficowym utworem o mnie :D
 
 

Komentarze

2010-10-22 20:41:21 | 93.105.232.* | Krev
Re: Bicykl Hamiltona [5]
To jak juz przy algorytmach jestesmy, jest jakas ksiazka ktora moglbys polecic a
jej lektura bylaby pomocna przy OIach czy innych SPOJach? skomentuj
2010-10-22 21:10:21 | *.*.*.* | chakier
Internet - tu jest (prawie) wszystko. Jedyną rzeczą której nie znalazłem to dobry
opis algorytmów dla parametric knapsack problem. skomentuj
2010-10-22 21:16:03 | 93.105.232.* | Krev
W momencie gdy szuka sie informacji na okreslony temat... skomentuj
2010-10-22 21:16:11 | 93.105.232.* | Krev
W momencie gdy szuka sie informacji na okreslony temat... skomentuj
2010-10-22 21:18:57 | *.*.*.* | chakier
W "ogólnych" książkach w kółko tłucze się to samo, zaś by znaleźć książkę
specjalistyczną musisz wiedzieć czego szukasz. A skoro wiesz - to szukasz w
internecie :) skomentuj
2010-10-22 21:37:26 | *.*.*.* | Jurgi
Re: Bicykl Hamiltona [0]
I pomyśleć to, ile koderzy potrafią wycisnąć ze zwykłego kapcia. skomentuj
2010-10-22 21:57:55 | 87.205.222.* | tdabpe
Re: Bicykl Hamiltona [1]
Wszystko fajnie, ale co to znaczy fan-ficowym? Tylko nie odsyłaj mnie do
internetu, bo nie mam :D skomentuj
2010-10-22 22:02:27 | 82.146.224.* | nerd_Chija
@tdabpe: Chyba Charyzjusz miał na myśli Fan fiction. A według wiki to "Fan
fiction (czasem używany skrót: ff) – tworzenie przez fanów (a niekiedy,
przeciwnie, krytyków) istniejącego filmu, książki, serii komiksowej itp.
opowiadań (zwanych fanfikami lub fanfiktami) nawiązujących do danego utworu,
dotyczących dziejów postaci w wybranym przez autora czasie. " skomentuj
2010-10-22 23:21:36 | *.*.*.* | Astroni800
Charyzjusz, w Internecie jest wszystko... oprócz tego, co się właśnie szuka,
oczywiste.
Najgłośniej chichotałam przy kolejnych krokach bicyklu komiwojażera. I zaraz po
nich. I tuż przed. Przypomina mi to trochę fragment którejś z książej Douglasa
Adamsa, w której pojawia się wzmianka o bakteriach, które "po znalezieniu
odpowiedniego nosiciela pozbawiają go sił, po czym uciekają jego statkiem
kosmicznym" (mniej więcej). Czy ty się czasem nie kręciłeś wokół tego autora?;)
A tak nawiasem, jak się temu przyjrzeć (bardzo ostrożnie się przyjrzeć...), to
wydaje mi się, że ten algorytm a-moralny nie jest aż taki lewy - wkońcu
komiwojażer jest stale przed Hamiltonem. Isn't it right?
Co do ff (jak to dotychczas nazywałam takie rzeczy spin-off'ami...) - zakręcony
jesteś jak słoik. Ale dzięki, nadal bardzo się cieszę;) Jak widać tak ci się
podobało, że aż myślę, że fajnie by było zobaczyć twoją minę przy czytaniu:D skomentuj
2010-10-22 23:31:52 | *.*.*.* | Olaf Perlinski
Re: Bicykl Hamiltona [0]
Widzę że mój Hamilton jeszcze z liceum, zrobil niezlą karierę ... skomentuj
2010-10-26 12:30:29 | *.*.*.* | Astroni800
Re: Bicykl Hamiltona [16]
Hej, Charyzjusz, wiesz, że począwszy od 22. października mam na Eiobie co
najmniej 38 wejść dziennie i tylko dzisiaj zajrzało tam już prawie 20 osób (a
przecież dopiero południe)? Aż mi nową rangę przyznali - DZIĘKI WIELKIE jeszcze
raz :p skomentuj
2010-10-26 18:35:30 | *.*.*.* | chakier
Kurczę... sądziłem że czyta mnie więcej niż 38 osób ;) skomentuj
2010-10-26 20:59:09 | *.*.*.* | Astroni800
Luz, w porywach dochodziło do 66 :>

P.S. Heee a wczoraj przypadkiem znalazłam zadanie z SIGALRM i dziwiłam się, że go
nie masz skomentuj
2010-10-26 21:22:00 | 193.84.199.* | ayz
nie wiem ilu czyta (patrząc -chociażby- na listę obecności z wpisów typu:
"Niedługo odziedziczę $20.5 miliona") :-)

OT: wpis od Astroni wygóglało mi się (niechcący) jeszcze przed jego
rozreklamowaniem, ale jak nie ma możliwości komentowania (tak jak tutaj) to drugi
raz nie będę wchodzić - bo ten tekst nie żyje (starczy przeczytać raz).

...nie ma to, jak pomarudzić ;) skomentuj
2010-10-27 07:47:21 | 82.146.224.* | nerd_Chija
@ayz: Oj nie marudź. Dałam Astorni propozycje aby ten tekst przenieść na mojego
bardzo starego, nieużywanego i zakurzonego bloga. I wtedy będziecie mogli
komentować ;). Projekt wciąż się rozwija, ale bądźcie cierpliwi, bo trudno jest
pisać, dla tak dużej grupy, wymagających osób. Jak mamy przenieść to na mój
blog, to trzeba opracować odpowiedni tytuł, opis i wygląd bloga. A to nie jest
robota na kilka godzin, jeśli chcecie mieć piorunujący efekt. Czyli powiem wam że
ten tekst nie jest martwy. Proszę was tylko o cierpliwość :). skomentuj
2010-10-27 23:00:10 | 94.75.118.* | Noqqa
Widzisz - pisanie bloga wymaga czasu, a zawsze otaczają cie żądni nowych wpisów
czytelnicy.

A tak swoją drogą - Charku (mogę tak cię nazywać, Charku?), coś ostatnio się
zopieszyłeś w tworzeniu. skomentuj
2010-10-27 23:19:44 | *.*.*.* | Astroni800
@Noqqa: No ja właśnie dostrzegłam, że wymaga czasu i intieligiencji i wogóle, ale
jak chciałam pomóc, to słyszę, że text nie żyje... Ja się nie dziwię - na miejscu
tego textu jakbym żyła, to już bym dawno poszła sobie stamtąd czytając takie
barwne komentarze. Dobrze chociaż, że samemu zainteresowanemu się podobało;)
A propos: Charyzjusz, jak tam starożytni Rzymianie czy tam Rosjanie..? skomentuj
2010-10-27 23:25:43 | *.*.*.* | chakier
@Noqqa: Mrówki robię
@Astroni800: Prawdziwa cnota krytyk się nie boi skomentuj
2010-10-28 18:25:07 | 94.75.118.* | Noqqa
A jak ci mrówki mogą przeszkadzać?
Robisz tak:

fragment kodu
//fragment wpisu na blog
fragment kodu
//fragment wpisu
... skomentuj
2010-10-28 19:10:08 | *.*.*.* | chakier
Mam długi czas przełączania tasku, to by było nieekonomiczne. skomentuj
2010-10-28 19:43:56 | *.*.*.* | Astroni800
Wątki rozłóż do tego. Albo jeszcze lepiej mrówki.
Tylko mi się tam nie zapętlij przypadkiem. skomentuj
2010-10-30 03:16:02 | 82.146.224.* | nerd_Chija
Ostatnio system mi się psuł i mówiłam to co nie powinnam mówić. Tak to jest gdy,
się dostanie ciałem fizycznym o kształcie kuli, rzucone z duża siłą i poruszające
się ruchem jednostajnie przyspieszonym i przy tym zderzające się z moim czołem.
Ta właśnie nie miła sytuacja spotkała mnie 6 pażdziernika (3 dni w szpitalu, 0
dostępu do komputerów i co najgorsze do internetu!) i znowu podobna sytuacyjna 26
października. Więc jeśli wywaliłam wtedy za dużo errorów, to bardzo przepraszam
za sprawienie problemów. Następnym razem wyjdę w zbroi na ulice. skomentuj
2010-10-31 00:22:40 | 94.75.118.* | Noqqa
Jednostajnie przyspieszonym?
To była piłka z napędem odrzutowym?

Chyba, że miałeś na myśli przyspieszenie ujemne... skomentuj
2010-10-31 07:36:49 | 82.146.224.* | nerd_Chija
@Noqqa: Nie piłka cały czas utrzymywała swoją niesamowitą prędkość (jak ktoś chce
możecie dodać opory powietrza) do czasu kiedy zderzyła się z moim czołem. Ale
wiedziałam, wtedy że nie zdążże w tym czasie odsunąć głowy i krzyknąć
najpopularniejszego słowa w języku polskim. Widocznie te piłki, co tak uwielbiały
trafiać w moje czoło musiały mieć jakiś napęd odrzutowy. skomentuj
2010-10-31 09:54:50 | *.*.*.* | chakier
Najpopularniejsze słowa w języku polskim? Ktoś w ciebie piłką, a Ty do niego
,,oddajcie krzyż!''? skomentuj
2010-10-31 11:36:59 | 82.146.224.* | nerd_Chija
Zapomniałam dodać że jest to wulgarne słowo. A mamusia mówiła, że nie ładnie jest
przeklinać.

Dziękuje Ci Charyzjuszu za poprawę humoru, a może nawet chumoru ;). Jedno
zdanie, a cieszy. skomentuj
2010-10-31 18:00:33 | *.*.*.* | Astroni800
Charyzjusz, to miało być jedno słowo. Pewnie na "k". Stawiam, że "kompilator". A
mój kolega zawsze upomina mnie, kiedy przy ludziach powiem "semafor". skomentuj
 


Najnowsze komentarze
 
2017-10-13 16:30
Rebecca Wendy do wpisu:
Jak się włamać na konto pocztowe
Jak uzyskałem pożądaną kwotę pożyczki z wiarygodnej firmy pożyczkowej[...]
 
2017-10-13 07:27
Gina Acampora do wpisu:
Jak się włamać na konto pocztowe
Nazywam się Gina Acampora i rozmawiam dzisiaj jako najszczęśliwszy człowiek na całym dzikim[...]
 
2017-10-12 20:39
Okeāna Finanses un do wpisu:
Jak się włamać na konto pocztowe
Czy potrzebujesz szybkiej i łatwej pożyczki? Dajemy pożyczkę z 3-procentową stopą procentową.[...]
 
2017-10-01 00:28
Amerisavefinancials@ do wpisu:
Jak się włamać na konto pocztowe
Hvis du trenger haster kreditt for løsning av finansielle behov, kan vi tilby lån[...]
 
2017-10-01 00:26
Amerisave do wpisu:
Jak się włamać na konto pocztowe
Hvis du trenger haster kreditt for løsning av finansielle behov, kan vi tilby lån[...]
 
2017-09-28 02:20
JIM BUFFER do wpisu:
Jak się włamać na konto pocztowe
Ubiegać się o pożyczkę szybki i wygodny sposób na zapłacenie rachunków i wznowienie[...]
 
2017-09-20 19:58
Pani Patricia Kingsm do wpisu:
Jak się włamać na konto pocztowe
OFERUJEMY WSZYSTKICH POŻYCZEK - MAJĄ ZASTĘPOWANIE W ZAKRESIE NIERUCHOMOŚCI. Czy jesteś[...]
 
2017-09-20 19:55
Pani Patricia Kingsm do wpisu:
Jak się włamać na konto pocztowe
Czy jesteś mężczyzną lub kobietą biznesu? Czy jesteś w jakimkolwiek bałaganie finansowym lub[...]
 



 
Chakier, Charyzjusz. Q2hhcnl6anVzeiBDaGFraWVyCg== chakier[at]vp.pl