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
 
Długa droga... 2010-10-09 23:07
 Oceń wpis
   
_-¯ To będzie krótki wpis. Głównie chciałbym przeprosić za mą mizerną aktywność w przeciągu ostatnich dwunastu miesięcy, ale zaprzątał mnie SPOJ. Koniec-końców - udało mi się zanim minął rok dostać na szczyt rankingu (proszę szybko klikać, bo sytuacja tam jest bardzo płynna!), i gdyby nie te cholerne mrówki mógłbym spać spokojnie. A tak - jak tylko zamknę oczy, to zaczynam nosić pożywienie do kopca...
 
Raczej nie 2010-10-03 15:38
 Oceń wpis
   
_-¯ Przede mną stał porucznik ABC. Ten sam, który na moich oczach skonał po wypiciu kawy. Opanowałem się z najwyższym trudem. Co robić? Przecież wystarczyłoby tylko wyjąć kopertę z teczki... Może zdążę?
- Obawiam się, że nie - powiedział Haron, po czym wyciągnął z tylnej kieszeni spodni papierośnicę i zapalił. Oczywiście - zapalił papierosa, nie papierośnicę. Pudełko schował do kieszonki na piersi.
- Co ,,nie''? - nie zrozumiałem.
- Nie zdążysz. Poza tym - ten komputer nie jest do niczego podłączony. Przewidziałem każdy twój ruch, Charyzjuszu. Włącznie z tym, że teraz będziesz się zastanawiał czy zdążysz wklepać polecenia zanim do ciebie dobiegnę. Nie zdążysz. To właśnie miałem na myśli.
- Strasznie dużo gadasz - odgryzłem się, lecz wypadło to bardziej niż mizernie. Zaraz... W ułamku sekundy dopadłem do starego, czternastocalowego, kineskopowego, monochromatycznego, zakurzonego monitora, wyrwałem jego kabel sygnałowy i przytknąłem do skroni. Jednocześnie silnym uderzeniem odbiłem luminofor ze środkowej części ekranu. Teraz tylko odpowiednio zamodulować sygnał... Zadziałało. Przez dziurę w luminoforze wystrzeliła wiązka elektronów, trafiając Harona w pierś i wypalając w jego koszuli brzydką dziurę. Nawet się nie skrzywił.
- To też przewidziałem, chowając moją papierośnicę właśnie w tym miejscu - powiedział, przekładając lekko osmalone pudełko z powrotem do tylnej kieszeni spodni - Nie masz szans.
- Doprawdy? - spróbowałem zrobić dobrą minę do złej gry.
- Dokładnie tak. Jak widzisz - znam każdy twój ruch.
- Ja też znam każdy swój ruch, więc mamy remis - warknąłem, choć sytuacja robiła się coraz bardziej nieciekawa. Staliśmy naprzeciw siebie i mierzyliśmy się wzrokiem. Postanowiłem przerwać milczenie.
- Po co składaliście mi wizytę w domu?
Haron uśmiechnął się lekko.
- To chyba oczywiste. Chcieliśmy odzyskać kopertę - to byłaby szybka, czysta robota. Ja miałem zajmować ciebie rozmową, a dwaj moi agenci znaleźliby co trzeba. Niestety, głupio daliśmy się zaskoczyć twoim RSom.
Papuć i Bambosz! - przemknęło mi przez myśl - Och! A ja na nie nakrzyczałem... Cóż - by zwieść RSa nie wystarczy się przebrać w mundur agenta ABC i pokazać legitymację. Ja dałem się na to nabrać, one - nie.
- A po co ten numer z kawą?
- Och, standardowa procedura operacyjna. Gdybyśmy sobie po wszystkim ot - tak sobie, wyszli - na pewno miałbyś chęć potem porozmawiać z kimś z ABC na nasz temat i sprawa mogłaby się wydać. W momencie gdy upozorowaliśmy śmierć - trzymałbyś język za zębami. Nawet policja nabrała się na naszą sztuczkę z algorytmem zachłannym w kawie. A teraz - poproszę o teczkę. All your base are belong to us.
Nie miałem wyjścia. Podszedłem powoli i wręczyłem mu teczkę. Oparł ją o kolano i otworzył.
- Jest pusta!
Wzruszyłem ramionami.
- Prosiłeś o teczkę to dałem ci teczkę. Ale jak chcesz... - wyjąłem z kieszeni zmiętą chusteczkę higieniczną z planem serwerowni i wrzuciłem do środka - teraz już nie jest pusta.
- Gdzie koperta?!
- Na biurku - odpowiedziałem obojętnie.
- Proszę mi ją podać.
- A jeśli odmówię?
W jego dłoni nie wiadomo skąd pojawił się miotacz sygnałów.
- Wtedy będę musiał sobie ją wziąć sam.
Podałem mu kopertę.
- Też jest pusta!
- Mogę do niej przełożyć chusteczkę z teczki - zaproponowałem. Haron warknął, nie zrobiło to jednak na mnie żadnego wrażenia - Pan wybaczy, ale muszę zrobić swoją robotę - dodałem, podłączając na powrót kabel sygnałowy i sadowiąc się przed ekranem.
- Nie jest podłączony do sieci, już mówiłem - przypomniał.
- Żaden problem - odparłem, wyjmując z kieszeni niewielkich rozmiarów modem. Wetknąłem odpowiednie wtyczki - Już jest.
Za moimi plecami rozległ się cichy stuk, a zaraz po nim następny.
- Proszę się nie kłopotać - wyjaśniłem - wyjąłem iglicę.
- Cóż, byłem na to przygotowany. Mam drugi.
- Z drugiego też.
Ponowny stuk zamka świadczył o tym, że Haron nie uwierzył mi na słowo.
- Z trzeciego też - dodałem.
Za moimi plecami rozległ się ryk wściekłości. Cóż - z samego Harona Hytrego nie mogłem wyjąć iglicy, a wyglądało na to że zaraz rzuci się na mnie osobiście. Nie przerywałem jednak pracy do momentu gdy nie usłyszałem odgłosu uderzenia. Odwróciłem się na fotelu. Haron, miotając przekleństwa, odbijał się od niewidzialnej ściany.
- Transparentny firewall - wyjaśniłem. Mój przeciwnik skrzywił się lekko, po czym zamigotał i znikł. Pojawił się tuż przy mnie.
- Tunel HTTP - oznajmił i grzmotnął mnie na odlew. Chybił.
- 404 - zahihotałem. Niestety, drugi cios trafił w cel.
- 200 - skwitował, gdy gramoliłem się z podłogi. Odstąpił kilka kroków - zawsze noszę ze sobą zapasową iglicę, więc żegnam - powiedział wycelowując we mnie broń.
- Ściema...
- Jestem jak najbardziej poważny, niestety...
- Ja też - dodał aspirant Ściema, waląc Hytrego kolbą w kark. Strzał, oddany w tym samym momencie, musnął mnie o włos.
Wstałem i otrzepałem spodnie.
- Czemu tak późno? - spytałem, podczas gdy Ściema z Widmowskim skuwali Harona kajdankami.
- Ciężko się było wydostać z pańskiej piwnicy, panie Chakier...
- Cieszę się jednak, że się panom udało - powiedziałem oglądając z zainteresowaniem okrągłą dziurę wypaloną w monitorze. Taka sama mogłaby być i we mnie...
- Co z tym? - Widmowski kiwnął głową w stronę komputera.
- Już nic - odpowiedziałem naciskając Enter. Komputer zaszumiał dyskiem i wyłączył się. Odpiąłem modem i schowałem do kieszeni. Haron, leżąc na podłodze, pojękiwał cicho.
- Wie pan, kto go przysłał? - spytał Ściema.
- Wiem.
- Jego też przydałoby się zapakować za kratki.
- Obawiam się, że ten człowiek jest zbyt wysoko postawiony, chociaż... - zawiesiłem głos, gdyż na myśl przyszło mi pewne zabawne skojarzenie - ...zapakować... Czemu nie?
- Co ma pan na myśli?
- Niedługo się panowie dowiedzą - odparłem zagadkowo - A teraz przepraszam, ale mam jeszcze jedną sprawę do załatwienia - pożegnałem się i wskoczyłem w sieć.

_-¯ Wielkie, dwuskrzydłowe drzwi odemknęły się bezszelestnie. Kobieta podeszła do okazałego biurka i pozostawiła na nim kopertę.
- Wiadomość - oznajmiła i wyszła.
Postać na fotelu sięgnęła po kopertę. Przez chwilę studiowała treść listu, po czym zmięła go w garści i ze złością cisnęła do kosza.
- Jeszcze cię dopadnę, Charyzjuszu! - wyszeptała przed siebie.
- Nie, raczej nie - szepnąłem zza oparcia i odpaliłem LZMA. Gotowy pakunek zaadresowałem i włożyłem do kuwetki z napisem ,,korespondencja wychodząca''. Miałem nadzieję, że inspektor Widmowski się ucieszy...

 


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