Tematy około algorytmiczne

Pułapka

2009-09-18T13:40:00.002+02:00

Pisałem ostatnio program wykonujący dość długo skomplikowane obliczenia. Przy pewnych danych wejściowych program przepełniał stos i się wysypywał. Po kilku godzinach frustracji postanowiłem przepisać każdą funkcję na wersję ogonową.
W trakcie tego jak to robiłem zacząłem się zastanawiać nad programowaniem funkcyjnym. Generalnie to jego główną ideą jest to, że piszemy w nim nie jak coś policzyć (tak jak to jest w programowaniu imperatywnym) tylko czym wynik danej funkcji ma być. I to jest bardzo przyjemne i bardzo fajnie się tak pisze - wszystkie funkcje wklepuje się niemal intuicyjnie. Problem jest jak dojdzie do funkcji ogonowych. Funkcje ogonowe (zwłaszcza nieco bardziej skomplikowanych obliczeń) są w ogóle nie intuicyjne. Trzeba zacząć się zastanawiać co ma być akumulatorem (może trzeba dać dwa akumulatory?) jakie dodatkowe informacje należy przekazać itp. itd.
Na szczęście udało mi się wszystkie funkcje przepisać na wersje ogonowe (Teraz jak ktoś spojrzy na kod to już się nie dowie co to a to robi :) ). Nie udało się przepisać tylko jednej. Może ktoś z was będzie miał pomysł. Funkcja dostaje długość listy l oraz sumę s i generuje wszystkie listy o długości l zawierające liczby dodatnie sumujące się co najwyżej do s. Na przykład: funkcja 3 5 = [[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,3,1][2,1,1],[2,1,2],[2,2,1],[3,1,1]]. Kolejność list nie jest ważna.
Gdy już miałem prawie wszystkie funkcje ogonowe i sprawdziłem ręcznie, że program nie wywiesza się na tej funkcji nie ogonowej... program dalej się wywieszał :-) Zasięgnąłem zatem opinii dokumentacji i okazało się... że standardowa funkcja map nie jest ogonowa... Troszeczkę się zdenerwowałem. Gdzie kolejność elementów nie była dla mnie ważna użyłem funkcji rev_map. W innych sytuacjach napisałem własną funkcję map:


let mymap l p = rev (map l p);;

Program wciąż nie działa - typ razem już na mojej funkcji (opisanej wyżej). Przepisałem program do C++ działa i to sto razy szybciej ;)

Labirynt cz II

2009-06-28T02:55:00.003+02:00

Normalnie bym nie pisał - bo sesja, ale udało mi się odratować kod źródłowy słynnego już labiryntu. Oto i on:


Rysuj
  | form pen ile i |
  form := Display.
  pen := Pen newOnForm: form.
  pen up.
  form fillWhite.
 
  ile := lab size.
  i := 1.
  [i <= ile] whileTrue:
  [
    pen goto: (lab at: i).
    pen down.
    pen goto: (lab at: (i+1)).
    pen up.
    i := i + 2.
  ]

  pen goto: 0@0.
  pen down.
  pen goto: (10*xsize)@0.
  pen goto: (10*xsize)@(10*(ysize // 2)).
  pen goto: 0@(10*(ysize // 2)).
  pen goto: 0@0.
  pen up.

  pen goto: 0@(10*((ysize // 2) +1)).
  pen down.
  pen goto: (10*xsize)@(10*((ysize // 2) +1)).
  pen goto: (10*xsize)@(10*ysize).
  pen goto: 0@(10*ysize).
  pen goto: 0@(10*((ysize // 2) +1)).
  pen up.

  pen goto: 0@(10*((ysize // 2) +1) + 1).
  pen down.
  pen goto: (10*xsize)@(10*((ysize // 2) +1) + 1).
  pen up.

  pen goto: 0@(10*((ysize // 2)) - 1).
  pen down.
  pen goto: (10*xsize)@(10*((ysize // 2)) - 1).
  pen up.

  [Sensor keyboardPressed] whileFalse: [].
  Display restore.

Stworz: x y: y
  | r v |
  xsize := x.
  ysize := y.
  r := Random new.
  lab := OrderedCollection new.
  0 to: (x-1) do:
    [:x1 |
      0 to: (y-1) do:
        [:y1 |
          (y1 = (y // 2)) ifFalse:
          [
            v := r nextInt: 5.
            (v > 2) ifTrue:
            [ lab addLast: (10*x1)@(10*y1)
              lab addLast: (10*(x1+1))@(10*y1) ].
            (v < 4) ifTrue:
            [ lab addLast: (10*x1)@(10*y1)
              lab addLast: (10*x1)@(10*(y1+1)) ].
          ].
        ].
    ].

Labirynt

2009-05-27T20:29:00.004+02:00

Zadanie brzmiało:

Zaprogramuj klasę generującą i rysującą labirynt o rozmiarze zadanym podczas tworzenia obiektu. Przyjmij że w labiryncie są tylko dwa wejścia oraz że istnieje droga łącząca te dwa wejścia.

Zadanie rozwiązałem po najmniejszej linii oporu. Labirynty generowane przez mój algorytm wyglądały mniej więcej tak:Prowadzący chciał mnie za to poćwiartkować.. Ale przyznał, że mój algorytm spełnia specyfikację zadania (jest to labirynt z dwoma wejściami taki, że istnieje ścieżka między nimi) i skończyło się na zaliczeniu programu na maksymalną ilość punktów.

Jako feature dodałem wysoce specjalistyczny algorytm sztucznej inteligencji znajdujący rozwiązania tego typu labiryntów 8)

Cykl Eulera cz II.

2009-05-21T20:15:00.004+02:00

Cyklem Eulera w grafie nazywamy następujące obejście grafu:

- zaczynamy w wybranym przez nas wierzchołku
- obchodzimy graf w ten sposób, że każdą krawędź przechodzimy dokładnie raz
- kończymy na wierzchołku w którym zaczęliśmy.

Jakie warunki musi spełniać graf aby istniał w nim cykl Eulera? Graf przede wszystkim musi być spójny. Jeśli by nie był mogłaby istnieć krawędź do której nie możemy dojść. Ponadto za każdym razem gdy wchodzimy do jakiegoś wierzchołka musimy umieć z niego wyjść. Zatem stopień każdego wierzchołka musi być wielokrotnością dwójki.

Okazuje się, że jeśli graf spełnia te dwa warunki to istnieje w nim cykl Eulera (dowód przez podanie algorytmu Fleury'ego będzie przedstawiony w którejś z kolejnych notek).

Zadanie z winniczkiem wydaje się teraz banalne. Spójność grafu mamy dane w treści zadania. Ponadto każdą krawędź w tym grafie musimy przejść dwukrotnie (ścieżki są dwa razy szersze od kosiarki) - zatem spełniony jest również drugi warunek. Zatem w grafie istnieje cykl Eulera. Ponieważ w zadaniu nie proszą nas o znalezienie tego cyklu, a jedynie o podanie w jakim czasie Winicjusz jest w stanie przejść ten graf, więc odpowiadamy: suma wag na krawędziach przemnożona przez dwa.

Cykl Eulera cz I.

2009-05-13T12:10:00.002+02:00

Oto zadanie, które musiał rozwiązać w miniony weekend. Zadanie wygląda na bardzo trudne, ale z odrobiną teorii okazuje się banalne.

Jak wszyscy dobrze wiemy, w soboty nie chodzi się do szkoły. Każde dziecko bardzo się z tego powodu cieszy i winniczek Winicjusz nie stanowi pod tym względem wyjątku. Niestety rodzice zaplanowali już, że w sobotę odbędzie się wielkie koszenie trawy w parku przed domem. Ponieważ dawno nikt tego nie robił, park strasznie zarósł i cała rodzina uznała, że nie starczy weekendu, aby doprowadzić go do ładu. Postanowili zatem, że skoszą jedynie trawę rosnącą na ścieżkach.

Przydomowy park jest bardzo typowy. Poprzecinany jest siecią alejek, które spotykają się ze sobą na ponumerowanych skrzyżowaniach. Ponieważ parki zazwyczaj służą do spacerowania, z dowolnego skrzyżowania można dojść na dowolne inne.

Ponieważ przyjaciele Winicjusza chcą wyciągnąć go wieczorem na pizzę, winniczek chciałby wiedzieć, ile czasu zajmie mu koszenie trawy. Kosiarka podczas koszenia porusza się z prędkością 1m/s oraz 2m/s, gdy jedzie po skoszonej trawie, a szerokość alejki jest dwa razy większa niż szerokość kosiarki.

Program, który wie jak bardzo został zoptymalizowany.

2009-05-08T18:22:00.004+02:00

Wczoraj na zajęciach z programowania prowadzący zajęcia powiedział nam o bardzo fajnym programie. Otóż taki program, korzystając z błędów kompilatora wypisywał -O1 kiedy był kompilowany z flagą -O1 oraz -O2 kiedy był kompilowany z flagą -O2. Bardzo zainteresowałem się tematem i postanowiłem wyszukać informacje na temat takiego programu w internecie. Niestety nie znalazłem. Na szczęście wyszukałem na tyle potrzebnych informacji, że udało mi się bez trudu napisać program który sprawdza jak był kompilowany:

[npb@localhost ~]$ cat fun.cpp
#include 

int main(void)
{
  unsigned long l  = 0x00110011;
  float         f  = *((float*)(&l));
  char*         c  = (char*)(&f);

  if      (c[0] == 17) printf("-O1\n");
  else                 printf("-O2\n");

  return 0;
}
[npb@localhost ~]$ g++ -O1 -o funO1 fun.cpp
[npb@localhost ~]$ g++ -O2 -o funO2 fun.cpp
[npb@localhost ~]$ ./funO1
-O1
[npb@localhost ~]$ ./funO2
-O2
[npb@localhost ~]$

Program nie korzysta z konkretnego błędu w kompilatorze, tylko z faktu że trochę oszukujemy kompilator. Widać że autor nie do końca sam wiedział co chciał zrobić. Udało mi się rozbudować program w taki sposób aby wykrywał również opcję -O3. Okazało się niestety że nie działa to na wszystkich kompilatorach g++; jednak kod przedstawię:

[npb@localhost ~]$ cat fun.cpp
#include 

unsigned long long_it(unsigned long in)
{
  return 0x00110011;
}

float float_it(float in)
{
  unsigned long v = long_it(*((unsigned long*)(&in)));
  return *((float*)(&v));
}

int main(void)
{
  float notimportant = 10;
  float retval       = float_it(notimportant);
  char  *retvalP     = (char*)(&retval);

  if      (retvalP[0] == 17) printf("-O1\n");
  else if (retvalP[0] == 0)  printf("-O2\n");
  else                       printf("-O3\n");

  return 0;
}
[npb@localhost ~]$ g++ -O1 -o funO1 fun.cpp
[npb@localhost ~]$ g++ -O2 -o funO2 fun.cpp
[npb@localhost ~]$ g++ -O3 -o funO3 fun.cpp
[npb@localhost ~]$ ./funO1
-O1
[npb@localhost ~]$ ./funO2
-O2
[npb@localhost ~]$ ./funO3
-O3
[npb@localhost ~]$

Postawie browara pierwszej osobie, której uda się ten sam trick z opcją -g :)

Niebezpieczne makra cz II.

2009-05-08T11:21:00.003+02:00

Spójrzmy raz jeszcze raz na program. Po podstawieniu za makro instrukcji if jest on postaci:

// Program pierwszy
if (warunek1)
  if (warunek2)
    instrukcja1;
else
  instrukcja2;

Spostrzegawczy czytelnik na pewno zauważy, że instrukcja2 tak na prawdę powinna być kolejnym ifem, jednak dla czytelności kodu zostawię ją tak jak jest.
W programie nie ma nawiasów klamrowych. Wcięcia sugerują, że instrukcja2 powinna zostać wykonana wtedy, gdy nie spełniony zostanie warunek1. Jednakże kompilator nie zwraca uwagi na wcięcia. Powyższy program i poniższy są dla kompilatora identyczne:

// Program drugi
if (warunek1)
  if (warunek2)
    instrukcja1;
  else
    instrukcja2;

Widzimy, że te dwa programy różnią się od siebie. Instrukcja2 wykonywana jest tylko wtedy gdy zostanie spełniony warunek pierwszy i niezostanie spełniony warunek drugi.
Powyższe programy dla kompilatora który ignoruje białe znaki jest identyczny? Pytanie zatem: jak kompilator traktuje taki kod. Tak jak program pierwszy czy tak jak program drugi? Okazuje się że gdy kompilator napotyka słowo kluczowe "else" próbuje je związać z ostatnią napotkaną pętlą "if". Zatem zinterpretuje kod źródłowy tak jak w programie drugim.

Aby unikać takich sytuacji dobrze jest stosować nawiasy klamrowe w ifach. Dobrym pomysłem jest też zamykanie w klamry całego makra.

Niebezpieczne makra cz I.

2009-05-06T08:09:00.005+02:00

Wczoraj wieczorem zabrałem się za rozwiązanie zadania z pracowni z ASD. Trochę za późno się za to wziąłem, bo na dwie godziny przed oddaniem programu byłem na etapie czytania treści zadania. Po napisaniu programu zająłem się debugowaniem. Doszedłem do wniosku, że błąd tkwi w poniższej pętli warunkowej.

if (j-KLOCKI[i] >= 0)
  assign(TAB[j-KLOCKI[i]][p2], TAB[j][p1]);
else
  assign(TAB[KLOCKI[i]-j][p2], TAB[j][p1]+KLOCKI[i]-j);

Przyglądałem się bardzo uważnie tym instrukcjom, ale nie umiałem dojść dlaczego program nie wchodzi do instrukcji w ciele else. Pomocną informacją może okazać się że assign to makro:

#define assign(a,b) if ((a) < (b)) a = (b)

Mógłbym popsuć wam zabawę i napisać gdzie tkwi błąd. Jednak tego nie zrobię. Opiszę to dopiero w następnej notce. Życzę miłej zabawy :-)

Wyszukiwanie maksimum lokalnego cz II. - O szybkim turyście i chciwym bacy

2009-04-30T09:37:00.006+02:00

Treść tego zadania jest bardzo głupia :) Chciałem ją zmodyfikować, ale stwierdziłem, że tak będzie śmieszniej :) Miłej lektury.

Mamy dany graf w którym wyróżniono dwa wierzchołki - A oraz B. Z każdą krawędzią i są związane dwie liczby rzeczywiste: a_i oraz b_i. Koszt przejechania tej krawędzi w czasie t wynosi a_it + b_i.
Turysta chce przejść z punktu A do B. Turysta jest bardzo sprytny i w dowolnym czasie t potrafi znaleźć najtańszą drogę z punktu A do B. Jest też bardzo bardzo szybki (struś pędziwiatr to przy nim żółw) i całą trasę potrafi przebiec w czasie zerowym!

Pytanie: W jakim czasie T z przedziału [0, 1] baca powinien wypuścić turystę ze swojej chatki, aby zmaksymalizować swój zysk?

Co ma z tym wspólnego maksimum lokalne? Dla każdej ścieżki w grafie jej koszt jest funkcją liniową zależną od T.
Zatem baca jeśli wypuści turystę w czasie T zarobi min(T) dudków, gdzie min(T) jest dane wzorem:
Spójrzmy na wykres tej funkcji.
Funkcja ma tylko jedno maksimum lokalne. Możemy zatem użyć wyszukiwania ternarnego (wystarczy tylko uogólnić algorytm na przedział rzeczywisty - co pozostawiam jako proste ćwiczenie ;) )

Wyszukiwanie maksimum lokalnego cz I. - wyszukiwanie ternarne

2009-04-29T12:29:00.004+02:00

Mamy daną tablicę A[1..n] wypełnioną parami różnymi liczbami rzeczywistymi. Element, który jest większy od swoich sąsiadów nazywamy maksimum lokalnym. W tej notce przedstawię algorytm, który dla danej tablicy znajdzie (jakieś) maksimum lokalne.
W pierwszej kolejności sprawdźmy elementy A[1] oraz A[n]. Mają one tylko jednego sąsiada. Jeśli zatem A[1] jest większe niż A[2] albo A[n] jest większe od A[n-1] to znaleźliśmy maksimum lokalne i kończymy algorytm.
Co jednak jeśli tak nie jest? Wyobraźmy sobie tablice jako wierzchołki. Krawędź między dwoma wierzchołkami jest skierowana w stronę większego elementu. Mamy zatem taką sytuację:
Algorytm działa rekurencyjnie. Oznaczmy zatem element najbardziej na lewo jako A[l], a najbardziej na prawo jako A[r]. Niezmiennikiem naszego wywołania rekurencyjnego będzie to że element A[l] jest mniejszy od A[l+1] a element A[r] jest mniejszy od elementu A[r-1] (rysunek powyżej). Można łatwo udowodnić że w takim przedziale znajduje się maksimum lokalne.
Weźmy dwa środkowe elementy tablicy. Oznaczmy je jako A[p] oraz A[q]. Zapytajmy się który z nich jest większy.
Jeśli A[p] < A[q] to rozwiązanie znajduje się w przedziale A[p..r].
Jeśli A[p] > A[q] to rozwiązanie znajduje się w przedziale A[l..q].
Nie zdarzy się, ża A[p] = A[q] bo założyliśmy że elementy są parami różne. Algorytm zatrzymuje się gdy w dostajemy tablicę 3 elementową (można łatwo udowodnić, że na taką tablicę trafimy: gdy natrafiamy na tablicę rozmiaru 4 to następnie uruchamiamy się dla tablicy 3 elementowej; gdy natrafimy na tablicę rozmiaru 5 to następnie uruchamiamy się dla tablicy albo 3 elementowej albo 4 elementowej). Gdy natrafimy na tablicę 3 elementową to zgodnie z niezmiennikiem algorytmu jego środkowy element będzie maksimum lokalnym.
Algorytm jako że w każdej iteracji wykonuje stałą liczbę operacji, a zawsze przedział dzielony jest na "prawie" połowę to działa w czasie O(lg n).
Jeśli elementy w tablicy najpierw rosną, a potem maleją (lub odwrotnie) to tablica taka ma tylko jedno maksimum (minimum) lokalne i jest nim największy (najmniejszy) element w tablicy. Zatem w tego rodzajach tablic jesteśmy w stanie znaleźć element największy (najmniejszy) w czasie logarytmicznym!

Posortowana lista w sqrt(n)

2009-03-13T19:37:00.009+01:00

Mamy posortowaną listę. Chcemy przy użyciu dodatkowej O(sqrt(n)) ilości pamięci umieć wstawiać i usuwać elementy z tej listy w czasie O(sqrt(n)).

Takie zadanie pojawiło się na pierwszej liście z AiSD. Większość rozwiązań tego zadania dzieliło listę na pierwiastek z n bloków o równej długości. Sprawiało to wiele problemów w sytuacjach w których należało zwiększyć liczbę bloków (jak to zrobić, aby zmieścić się w czasie O(sqrt(n))?). Moje rozwiązanie opierało się na nieco innym pomyśle, dzięki czemu cała struktura danych staje się bardzo prosta i elegancka.

Podzielmy listę (dwukierunkową) na bloki. Pierwszy blok będzie miał jeden element; drugi blok dwa elementy, trzeci trzy... i tak dalej. Przy czym dopuszczamy, aby ostatni blok był niepełny. To będzie nasz niezmiennik. Taka lista będzie miała k dodatkowych wskaźników (na początki bloków) i każdy z bloków będzie miał rozmiar nie większy niż k. Liczba elementów na takiej liście będzie równa 1 + 2 + 3 + ... + k = k(k+1) / 2 = n. Zatem jak widzimy k jest rzędu O(sqrt(n)).

Wstawianie elementu el wykonujemy w czterech prostych krokach:
- Szukamy do którego bloku musi trafić element el (O(k) operacji).
- Szukamy w które miejsce ma trafić element i umieszczamy go w tym miejscu (O(k)).
- Przywracamy niezmiennik listy. Robimy to w ten sposób, że wskaźniki do wszystkich bloków znajdujących się na prawo od wstawionego elementu przesuwamy o jeden element w lewo (O(k) operacji).
- Jeśli ostatni blok przekroczy dozwolony rozmiar, to tworzymy nowy blok (O(1)).
Wstawienie elementu prezentuje poniższy rysunek.
Usuwanie elementu w sposób analogiczny.

ZOSIA wykład

2009-03-08T16:40:00.005+01:00

Na Zimowym Obozie Studentów Informatyki (ZOSIa) przedstawiłem wykład na temat gry SZOK. Zgodnie z obietnicą umieszczam tutaj materiały do wykładu. Poprawioną wersję prezentacji. Dokumentację projektu (gorąco polecam! :) znajduje się w niej opis instalacji). Oraz wreszcie samą grę SZOK. W razie problemów z linkami proszę o kontakt.

Szok to prosta gra w której musimy pomóc owieczce pozbierać z planszy wszystkie marchewki. W tym celu piszemy program w języku logo-podobnym i uruchamiamy go w symulatorze.
I nie byłoby w tej grze nic wyjątkowego, gdyby na każdej planszy nie znajdował się smok. Smok jest także programem napisanym pseudo-logo. Nie chodzi on jednak po planszy, tylko po kodzie źródłowym owieczki i zjada z niego instrukcje…

Do plansz islandofsecrets oraz piratestreasure nie ustaliłem limitów. Nie chciałem ich obierać "na oko", a sam tych planszy jeszcze nie przeszedłem (w sumie nawet nie próbowałem). Osoby, które przejdą te plansze i chcą pomóc przy ustalaniu progów są proszone o kontakt ze mną :-)
Pozdrawiam!

Niecierpliwiec

2009-02-12T14:05:00.004+01:00

Kolokwium już napisane, teraz najgorsze - czekanie na wyniki. Zazwyczaj sprawa wyglądała tak, że wchodziło się na stronę wykładowcy i odświeżało się ją co kilka minut. Na dłuższą metę jest to po prostu nie wygodne i męczące. A że potrzeba jest matką wynalazków... prezentuję niecierpliwca. Ten kilkulinijkowy skrypt ułatwia już życie niejednemu studentowi :)

#!/bin/bash
echo "Niecierpliwiec v. 0.3"
echo "Autor: Krzysztof Piecuch"
rm -f Wzorzec.html Kopia.html
wget -O Wzorzec.html -q $1

while [ true ]
do
   sleep 20
   wget -O Kopia.html -q $1
   if ! diff -q Kopia.html Wzorzec.html
   then
      mplayer Muzyka/coś_tam.mp3
      break
   fi
   rm -f Kopia.html
done

Program ma jedną wadę. Czasami zdarza się, że wgetowi nie uda się pobrać strony. Przez co tworzy w miejscu kopii pusty plik. Następnie diff wykrywa różnice między tym plikiem a wzorcem i wszczyna niepotrzebny alarm.
Program wciąż w fazie testów.
Zamiast uruchamiania mplayera polecam beepa. Jednak na moim sprzęcie beep nie działa :-) Życzę miłej zabawy i powodzenia w sesji poprawkowej ;-)

Wielopoziomowa Lista Liczb Całkowitych

2009-02-06T20:42:00.007+01:00

Zadanie z kursu ANSI C brzmiało:

Wielopoziomową Listę Liczb Całkowitych (w skrócie WLLC) definiujemy jako skończony (w tym także pusty) ciąg, którego elementami są liczby całkowite lub WLLC. Jeśli lista zawiera tylko liczby to nazywamy ją jednopoziomową. Przykłady L1 = [3,1,5]; L2 = [2,[4,7],[]]; L3 = [[[3],[5,8],2],[1,5]]. Lista L1 jest jednopoziomowa. Zdefiniować moduł WLLC (tzn. podać zawartość plików wllc.c oraz wllc.h), w którym:
- Zdefiniowana jest funkcja WLLC merge(WLLC l1, WLLC l2), która zwraca listę powstałą z dołączenia listy l2 na końcu listy l1. Na przykład dołączenie listy L1 na końcu listy L2 powinno stworzyć listę [2,[4,7],[],3,1,5].
- Zdefiniowana jest funkcja WLLC flat(WLLC li), która tworzy nową listę jednopoziomową zawierającą wszystkie liczby z listy li z zachowaniem ich kolejności. Na przykład wywołanie flat(L3) powinno zwrócić listę [3,5,8,2,1,5].

Ja na tym kolokwium podszedłem do tego zadania bardzo rutynowo i stworzyłem strukturę, która wyglądała mniej więcej tak:

struct WLLCnode
{
  bool  isWLLC;    // True jeśli element jest listą WLLC
  int   intvalue;  // Wartość liczbowa
  WLLC* WLLCvalue; // Wartość listowa
  WLLC* next;      // Wskaźnik na następny element
};
typedef WLLCnode* WLLC;

Po czym występowały definicje funkcji. Trochę się zamotałem z tymi wskaźnikami,

"Dać programiście wskaźniki to tak jakby dać małpie karabin maszynowy" Piotr Chrząstowski-Wachtel

pokreśliłem pół kartki ale ostatecznie coś wyszło i o dziwo okazało się poprawne. Nie mam zamiaru odtwarzać tego rozwiązania, ale wierzcie mi - było straszne :D. Natomiast Maciek zaczął to zadanie tak:

typedef char* WLLC;

i wszystkie funkcje pisze się miło i przyjemnie. Bardzo spodobało mi się to rozwiązanie. Z moją pomocą udało się zmniejszyć złożoność obu funkcji do liniowych i zmniejszyć rozmiar tych funkcji do kilku linijek.

Pierwsza funkcja jest bardzo prosta, aż niema co w niej opisywać. Rezerwujemy pamięć, kopiujemy pierwszą listę, kopiujemy drugą listę, wstawiamy przecinek w odpowiednie miejsce. Osobno rozważamy przypadki gdy lista jest pusta.

WLLC merge(WLLC a, WLLC b)
{
  int lena = strlen(a);
  int lenb = strlen(b);
  WLLC answer = malloc((lena + lenb) * sizeof(char));
  
  // Jeśli lista a jest pusta - zwróć listę b
  if (lena == 2)
    return strcpy(answer, b);

  // Analogicznie
  if (lenb == 2)
    return strcpy(answer, a);
  
  strcpy(answer, a);
  strcpy(answer + lena, b + 1);
  answer[lena - 1] = ',';

  return answer;
}

Z funkcją flat na początku były kłopoty. Maciek strasznie zakręcił... ale rozwiązanie jest dość proste:

WLLC flat(WLLC a)
{
  int  j = 1;
  bool inint = false;
  WLLC answer = malloc(strlen(a) * sizeof(char));
  
  answer[0] = '[';
  for (int i = 0; a[i] != '\0'; i++)
  {
    if (('0' <= a[i] && a[i] <= '9') || a[i] == '-')
    {
      answer[j++] = a[i];
      inint = true;
    }
    else
    {
      if (inint) answer[j++] = ',';
      inint = false;
    }
  }
  if (j == 1) j++;
  answer[j-1] = ']';
  answer[j]   = '\0';
  
  return answer;
}

Iterator i przebiega listę, którą chcemy spłaszczyć. Iterator j przebiega naszą listę wynikową. Jeśli na danej nam liście znajduje się cyfra - to ją przepisujemy. Jeśli nie, to sprawdzamy czy nowy znak zakończył nam jakąś liczbę (służy nam do tego zmienna "inint"). Jeśli zakończył to stawiamy przecinek. Na końcu zamykamy nawias i zwracamy wynik. Warunek if na samym końcu zapewnia nas, że zwrócimy poprawny wynik także dla listy pustej. Przykład użycia:

  WLLC L0 = "[]";
  WLLC L1 = "[3,1,5]";
  WLLC L2 = "[2,[4,7],[]]";
  WLLC L3 = "[[[3],[5,8],2],[1,5]]";
  
  printf("%s\n", merge(L2, L1));
  printf("%s\n", flat(L3));

Delta

2009-01-31T18:09:00.001+01:00

Został jeszcze tydzień sesji i przez ten czas pewnie nie napiszę nic kreatywnego na tym blogu. Jeśli jednak ktoś chciałby mnie poczytać, to w nowym numerze Delty znajduje się mój artykuł poświęcony Algorytmowi SPFA. Życzę przyjemnej lektury.

100 ciekawych wpisów

2009-01-16T22:14:00.003+01:00

Mój blog (a konkretnie notka o 5 najbardziej spektakularnych błędów oprogramowania) trafił na antywebową listę 100 ciekawych notek.

W związku ze zbliżającą się sesją nie mam za wiele czasu na prowadzenie tego bloga. Nie będą się zatem w przeciągu najbliższych dwóch tygodni pojawiały notki.
W Ferie postaram się nadrobić zaległości ;)

Pozdrawiam

2009 (0x07D9)

2009-01-01T13:46:00.004+01:00

Ile jest w systemach bugów
Ile w internecie znajdziesz cracków
Ile lamer stracił danych
Ile na rapidzie plików wgranych
Ile w skrzynce miałeś spamu
Ile Vista zżera ramu
Ile notek na tym blogu
Tyle szczęścia w nowym roku

życzy npb

Fresh i Reset bez użycia zmiennych globalnych

2008-12-20T10:24:00.004+01:00

Rozważmy następujący problem. Mamy stworzyć dwie funkcje: fresh i reset. Pierwsza z nich ma generować kolejne liczby naturalne dodatnie, druga ma nam posłużyć do zerowania naszego stanu liczniki. Przykładowa sesja programu może wyglądać na przykład tak:

# fresh ();;
- : int = 1
# fresh ();;
- : int = 2
# fresh ();;
- : int = 3
# fresh ();;
- : int = 4
# reset ();;
- : unit = ()
# fresh ();;
- : int = 1
# fresh ();;
- : int = 2

Cały problem w napisaniu tej funkcji polega na tym, że w implementacji nie możemy korzystać ze zmiennych globalnych. Polecam, abyś sam przez chwilę zastanowił się jak ten problem rozwiązać zanim przeczytasz moje rozwiązanie.

Zmienna w OCamlu "żyje" tak długo aż istnieje wskaźnik na tą wartość. I nie ważne czy zmienna ta została zdefiniowana globalnie czy lokalnie w funkcji.

Pierwszy pomysł to stworzenie funkcji, która jako argument bierze unit, a zwraca parę funkcji (fresh, reset). Zadeklaruje ona lokalnie zmienną, która będzie użyta do zdefiniowania funkcji. Po wyjściu zmienna ta nie będzie już nigdzie widoczna poza zwróconą parą funkcji.

type r = { mutable x : int };;

let create () =
    let y = ref {x = 0} in
    ((fun () -> (ignore (!y.x <- !y.x + 1) ; (!y.x))),
      fun () -> ignore (!y.x <- 0));;

let x = create () ;;
let fresh = fst x and reset = snd x;;

Takie rozwiązanie ma swoje wady i zalety. Zaletą jest to że możemy tworzyć wiele par fresh-reset, wadą to, że pozwalamy na korzystanie ze zmiennej x bez konieczności użycia funkcji fresh i reset.

Edit: W komentarzach pojawiły się inne (imho lepsze) rozwiązania tego zadania. Polecam lekturę tych komentarzy ;)

20 000

2008-12-18T18:05:00.002+01:00

Dzisiejszego dnia strona została wyświetlona po raz 20 000. Dziękuję wszystkim moim Czytelnikom. To dla was tworzę tego bloga.

W najbliższym tygodniu napiszę najprawdopodobniej dwa artykuły dotyczące programowaniu w OCamlu. W pierwszej opiszę pewną sztuczkę z dzieleniem zmiennych pomiędzy dwie funkcje, bez użycia zmiennych globalnych. W drugiej stworzymy gwiazdkę Kocha (tak świątecznie :))

Pozdrawiam!

Do pobrania

2008-12-15T21:57:00.000+01:00

Zmieniłem serwis na którym trzymam pliki z sekcji "do pobrania". Mam nadzieję, że teraz wszystkim będzie się żyło lepiej :)
Pozdrawiam

Wykop

2008-12-07T12:50:00.002+01:00

Kilka dni temu Alek poinformował mnie, że mój blog (a właściwie notka o najbardziej spektakularnych błędach) trafił na stronę główną wykopu. Zdobył nawet bardzo przyzwoity wynik :). Mam nadzieję, że dzięki wykopowi zdobędę kilku nowych czytelników. Ja natomiast obiecuję wciąż trzymać dobry poziom moich notek.
Pozdrawiam serdecznie wszystkich wykopowiczów!

Błędy w OCamlu

2008-12-04T18:49:00.004+01:00

Programy w OCamlu pisze się bardzo przyjemnie. Schody zaczynają się gdy OCaml chce nas poinformować, że zrobiliśmy błąd. Często robi to tak nieudolnie, że bardzo trudno jest błąd nawet zlokalizować. Dziś przez pół godziny szukałem z Maćkiem błędu w implementacji Grafu. Błąd znaleźliśmy, ale w zupełnie innym module niż ten na który wskazywał OCaml.
Dziś rano z kolei OCaml powitał mnie komunikatem

File "Database.ml", line 54, characters 17-25:
This pattern matches values of type punkt
but is here used to match values of type punkt

Bardzo zdziwiłem się widząc ten komunikat. I chyba nie znalazłbym błędu, gdybym nie widział podobnego błędu wcześniej. Troszkę starań i OCaml wypluje nam taki komunikat:

This expression has type t but is here used with type t

Jak zmusić OCamla do wyplucia takiego błędu? Opiszemy za chwilę. Na razie spróbujmy zrozumieć co tak na prawdę OCaml ma na myśli. Rozważmy następującą sesję ewaluatora:

# type typ1 = Konstruktor | Innykonstruktor;;
type typ1 = Konstruktor | Innykonstruktor

# Konstruktor;;
- : typ1 = Konstruktor

# type typ2 = Konstruktor | Jeszczeinnykonstruktor;;
type typ2 = Konstruktor | Jeszczeinnykonstruktor

# Konstruktor;;
- : typ2 = Konstruktor

W trzecim poleceniu do zdefiniowania typu "typ2" użyliśmy ponownie konstruktora "Konstruktor". Przesłoniliśmy w ten sposób konstruktor o tej samej nazwie z typu pierwszego. Nie będziemy mogli już z niego normalnie korzystać. Gdy użyjemy teraz w dowolnym miejscu konstruktora "Konstruktor" zostanie on potraktowany jako konstruktor z typu drugiego (a nie jako konstruktor typu pierwszego).

# type t = Konstruktor of int;;
type t = Konstruktor of int

# let get_int a = match a with Konstruktor b -> b;;
val get_int : t -> int = 

# type t = Konstruktor of int;;
type t = Konstruktor of int

# let osiem = Konstruktor 8;;
val osiem : t = Konstruktor 8

# get_int osiem;;
This expression has type t but is here used with type t

Przeanalizujmy co tutaj się stało. W pierwszej linijce tworzymy nowy typ t. W drugiej linijce definiujemy funkcję, która jako argument bierze typ t - ten z pierwszej linijki (mniejsza o to co ta funkcja robi). W linijce trzeciej tworzymy nowy typ t (ma on nawet tą samą definicję co nasz pierwszy typ t - mimo to będzie traktowany jako nowy typ). Przesłaniamy w ten sposób pierwszy typ t. W linijce czwartej definiujemy wartość "osiem" używając konstruktora "Konstruktor". Jak wiemy z poprzedniego akapitu - będzie to wartość typu t zadeklarowanego w 3 linijce. Na koniec próbujemy wywołać funkcję od wartości "osiem", która jest typu t (zdefiniowanego w linijce 3) podczas gdy funkcja przyjmuje argumenty typu t (zdefiniowane w linijce pierwszej).

5 najbardziej spektakularnych błędów oprogramowania

2008-11-30T11:52:00.009+01:00

Informatyka jest wszędzie. Programy komputerowe otaczają nas zewsząd. W banku, w szpitalu, na ulicach, w elektrowniach. Nawet nie wiemy jak wiele zależy w naszym życiu od tego czy programy te zostały rzetelnie przetestowane przez programistów. Przedstawiam ranking 5 najbardziej spektakularnych błędów w oprogramowaniu. Błędy te pochłonęły miliony dolarów, a co gorsza - w wyniku tych błędów zginęli ludzie.

5 miejsce
Therac-25

Therac-25 jest maszyną do radioterapii. Między 1985 a 1987 rokiem odnotowano przynajmniej 6 przypadków w których pacjentom podano za dużą dawkę promieniowania. Pacjenci zachorowali na chorobę popromienną. Pięciu z nich z tego powodu zmarło.
Powodem był błąd oprogramowania spowodowany tak zwaną sytuacją wyścigu (race condtition). Z sytuacją taką mamy do czynienia na przykład gdy wynik działania jakiegoś procesu zależy od zgrania z czasem lub innych zdarzeń (procesów). Problem ten jest skomplikowany i nie będę się tu nim zajmował. Osób zainteresowanych tym tematem odsyłam do artykułu Michała Wojciechowskiego.

4 miejsce
Blackout 2003

14 sierpnia 2003 roku miała miejsce największa awaria zasilania w historii. Odciętych od prądu zostało 50 mln ludzi. W USA całkowicie od prądu zostały odłączone stany Ohio, Nowy Jork, New England, Massachusetts, Connecticut, Michigan, Pensylwania oraz północne New Jersey. W Kanadzie prowincja Quebec i Ontario. W wyniku awarii zostało wyłączonych 100 elektrowni (w tym 22 atomowe), przestały kursować pociągi, stanęły windy, ulice zostały zakorkowane z powodu braku sygnalizacji świetlnej. Na kilku lotniskach zawieszono loty. Działalność zawiesiła nowojorska giełda towarowa. Mieszkańcy stanu Michigan ucierpieli dodatkowo w wyniku braku wody, która dostarczana jest tam za pomocą pomp elektrycznych. W samym Nowym Jorku straż pożarna odnotowała 3000 zgłoszeń do pożarów (wywołanych zazwyczaj nieumiejętnym posługiwaniem się świeczkami). Awaria zasilania pochłonęła co najmniej 11 ofiar.
Na tą awarię złożyło się kilka czynników. Jednym z nich był błąd w programie w którym dochodziło do sytuacji wyścigu (patrz wyżej).
Wydanie specjalne wiadomości.

3 miejsce
Mariner 1

22 lipca 1966 roku wystartowała sonda kosmiczna Mariner 1. Po 5 minutach lotu oficer bezpieczeństwa widząc nienormalne zachowanie się rakiety wydał polecenie autodestrukcji.
Błąd w oprogramowaniu wynikał... ze złego przepisania wzoru z kartki... Smutne, ale prawdziwe. Przepisujący nie zauważył kreski nad pochodną w czasie n-tego promienia. Kreska oznacza funkcję wygładzania. Bez tej kreski komputer traktował najmniejszą zmianę prędkości bardzo poważnie i wykonywał serię gwałtownych manewrów.
Straty szacuje się na około 18.5 mln $.
Zdjęcie startu Mariner 1

2 miejsce
Masakra w Dhahran

25 lutego 1991 roku iracka rakieta typu SCUD trafia w barak w Dhahranie (Arabia Saudyjska) zabijając 28 amerykańskich żołnierzy. Zawiodło oprogramowanie systemu obrony przeciwlotniczej PATRIOT.
Zmienne zmiennoprzecinkowe mają taką własność, że małe liczby są zapamiętywane z dużą dokładnością, natomiast wielkie z niewielką dokładnością. Jest to bardzo przydatna własność. Gdy chcemy zmierzyć wielkość bakterii to błędy rzędu milimetra powodują, że nasze obliczania nadają się tylko do śmietnika. Jednak gdybyśmy chcieli zmierzyć odległość z Ziemi do Księżyca to jesteśmy w stanie zaakceptować błędy rzędu kilometrów.
Zegar (licznik) baterii patriot liczył czas w zmiennej całkowitej. Następnie w celu dalszych obliczeń ten licznik rzutowany był na liczbę zmiennoprzecinkową. Gdy wartość licznika była duża to błąd bezwzględny był również duży. Podczas gdy Irakijczycy wystrzelili rakietę, system PATRIOT działał już od ponad 100 godzin. Błąd zegara po zrzutowaniu na zmienną zmiennoprzecinkową wynosił około 1/3 sekundy. Co przy prędkościach pocisków balistycznych spowodowało błąd obliczenia celu pocisku o około 700 metrów! System PATRIOT zawiódł.
Amerykanie wiedzieli o tym błędzie. Odpowiednia poprawka oprogramowania była już w drodze. Do Arabii doszła dzień po tragedii.
Masakry można było uniknąć. Wystarczyło co kilka godzin zerować wartość licznika.

1 miejsce
Ariane Lot 501

Choć to zazwyczaj Amerykanom zdarzały się spektakularne klęski, to niestety z bólem serca Europejczykom muszę przyznać pierwsze miejsce w tym rankingu.
4 czerwca 1996 roku. Z kosmodromu Kourou w Gujanie Francuskiej w swój pierwszy lot testowy wyrusza europejska rakieta Ariane 5. Po 37 sekundach lotu rakieta zeszła z kursu i została zniszczona przez system autodestrukcji. Straty szacuje się na około 370 mln $. Sam koszt wystrzelenia takiej rakiety to około 180 mln $.
Choć przed lotem próbnym przetestowano dokładnie cały sprzęt, to nie przetestowano oprogramowania. Bo i po co? Przecież został on niemal w całości skopiowany z Ariane 4, na którym to działał bez zarzutów. Jednak Ariane 5 miał szybsze silniki niż jego poprzednik, przez co oprogramowanie generowało większe liczby. Błąd pojawił się, gdy 64 bitową zmienną zmiennoprzecinkową program próbował zrzutować na 16-bitową zmienną całkowitą. Gdy wartość liczby 64-bitowej nie mogła się zmieścić w 16 bitach, komputer rzucił wyjątek (arithmetic overflow). Spowodowało to efekt domina - komputer zaczął rzucać serię kolejnych wyjątków. Końcowym efektem było zboczenie rakiety z kursu i autodestrukcja.
Film z feralnego lotu można znaleźć tutaj.

Starałem się rzetelnie opisać na czym polegały błędy w oprogramowaniu, choć szukając źródeł trafiałem bardzo często na sprzeczne ze sobą informacje. Niech nie zdziwi was zatem fakt, że być może znajdziecie w innych źródłach inne wyjaśnienia dotyczące błędów w opisanych przeze mnie sytuacjach.

Po tym artykule trochę inaczej będę podchodził do tego gdy mój ćwiczeniowiec znowu krzyknie: "Aha! Pana program źle działa dla takich danych wejściowych!".

Zbiór Mandelbrota w OCamlu

2008-11-28T20:10:00.007+01:00

Ostatnio na pracowni z programowania funkcyjnego kazano nam napisać program w OCamlu rysujący zbiór Mandelbrota.
Postanowiłem zamieścić tutaj swoje rozwiązanie dlatego, że niewiarygodne jest jakie piękne efekty możemy otrzymać za pomocą 20-linijkowego programu.

(* Mandelbrot :-) *)

#load "graphics.cma";;
open Graphics;;
open Complex;;

let conve a =
    float_of_int(a) /. (640. /. 4.) -. 2.;;

let rec calc_color p zn k =
    if      k = 0 then 0
    else if norm zn >= 2. then k
    else    calc_color p (add (mul zn zn) p) (k-1);;

let display () =
open_graph " 640x640";
for x = 0 to 640 do
   for y = 0 to 640 do
      let p = {re = conve x; im = conve y} in
      let k = 8 * calc_color p p 31 in
      set_color (rgb k k k);
      plot x y
   done
done;
let _ = read_key () in close_graph();;

Zbiorem Mandelbrota nazywamy zbiór punktów p na przestrzeni zespolonej, który spełnia warunek |z_n| < 2. Przy czym z₀ = p oraz z_n = z_n-1 * z_n-1 + p dla n > 0. Przybliżenie tego zbioru otrzymujemy ustalając pewną liczbę powtórzeń m, a następnie sprawdzając, które punkty płaszczyzny spełniają z₀ < 2, z₁ < 2, ..., z_m < 2.

Funkcja conve zamienia liczbę naturalną z przedziału [0..640] (w oknie o rozdzielczości 640x640 będziemy rysowali zbiór Mandelbrota) na liczbę rzeczywistą z przedziału [-2..2] (jeśli, któraś ze współrzędnych danego punktu jest spoza tego przedziału to punkt ten nie należy do zbioru Mandelbrota).

Funkcja calc_color liczy kolejne wartości ciągu z_n dla n = 0..k i szuka najmniejszego takiego m, że z_m >= 2. Funkcja zwraca k - m. Od tej wartości będzie zależał kolor na jaki pomalujemy dany punkt na płaszczyźnie (stąd nazwa).

Funkcja display tworzy okno o rozmiarach 640 x 640. Następnie dla każdego piksela w tym oknie liczymy jego współrzędne zespolone. Następnie obliczamy kolor w jakim będziemy malować ten piksel, ustawiamy pędzel na ten kolor i na końcu malujemy ten piksel na dany kolor.

O funkcyjnym paradygmacie programowania napiszę słów kilka w niedalekiej przyszłości.
Jeśli coś było niejasnego w tej notce, lub notka zawiera błąd, to będę wdzięczny za komentarze.

Weronika

2008-11-11T22:48:00.003+01:00

W dziale "do pobrania" pojawił się program Weronika v 8.0. Program walczący, który w tegorocznej edycji Internetowego Turnieju Programów Walczących zajął 16 miejsce.

Imię Weronika pochodzi z języka greckiego: phero - nieść; nike - zwycięstwo. Dosłownie "Nosząca zwycięstwo".

W następnych notkach postaram się przedstawić główną idee działania tego algorytmu.

Algorytm Forda-Johnsona cz III.

2008-11-10T17:53:00.006+01:00

Zgodnie z obietnicą w tej części postaram się wyjaśnić dlaczego akurat taki ciąg został wybrany w części drugiej.

Wszystkie rozważenia przeprowadzę na następującym przykładzie:Rozważymy trzy proste ciągi i policzymy ile w najgorszym przypadku będziemy potrzebowali porównań, aby posortować te liczby. Przypomnę jeszcze, że aby do ciągu n elementowego wstawić liczbę potrzebujemy [lg n] + 1 porównań (gdzie [x] - oznacza podłogę z liczby x).

Spróbujmy wstawiać elementy od lewej do prawej:

Wstawiamy 8 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 7 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 6 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 5 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 4 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 3 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 2 --- Wykonujemy 4 porównania ([lg 8] + 1)
W sumie - 28 porównań.

Zauważmy, że w tej metodzie wstawiając każdy element, wykonaliśmy tyle samo porównań (skorzystamy z tego faktu). Teraz spróbujmy wstawiać elementy od prawej do lewej:

Wstawiamy 2 --- Wykonujemy 2 porównania ([lg 2] + 1)
Wstawiamy 3 --- Wykonujemy 3 porównania ([lg 4] + 1)
Wstawiamy 4 --- Wykonujemy 3 porównania ([lg 6] + 1)
Wstawiamy 5 --- Wykonujemy 4 porównania ([lg 8] + 1)
Wstawiamy 6 --- Wykonujemy 4 porównania ([lg 10] + 1)
Wstawiamy 7 --- Wykonujemy 4 porównania ([lg 12] + 1)
Wstawiamy 8 --- Wykonujemy 4 porównania ([lg 14] + 1)
W sumie - 24 porównania.

Czyli w drugim przypadku wykonaliśmy o 4 porównania mniej. I nasza metoda z poprzedniej notki:

Wstawiamy 3 --- Wykonujemy 2 porównania ([lg 3] + 1)
Wstawiamy 2 --- Wykonujemy 2 porównania ([lg 3] + 1)
Wstawiamy 5 --- Wykonujemy 3 porównania ([lg 7] + 1)
Wstawiamy 4 --- Wykonujemy 3 porównania ([lg 7] + 1)
Wstawiamy 8 --- Wykonujemy 4 porównania ([lg 12] + 1)
Wstawiamy 7 --- Wykonujemy 4 porównania ([lg 12] + 1)
Wstawiamy 6 --- Wykonujemy 4 porównania ([lg 12] + 1)
W sumie - 22 porównania.

Zauważmy dwie rzeczy. W momentach w którym nasz ciąg maleje - (np. we wstawieniu 8, 7, 6) wykonujemy tyle samo porównań (zauważyliśmy już to w ciągu pierwszym). Nie przypadkiem jest również to, że wewnątrz logarytmów są liczby bliskie potęgom liczby 2 (gdybyśmy wstawiali liczby do 11 to w miejscu [lg 12] pojawił by się [lg 15]).

Ciąg trzeci został więc wybrany następująco (zachłannie):
- wybierzmy wierzchołek najbardziej na lewo, który jesteśmy w stanie wstawić w dwóch ruchach.
- wstawmy go do ciągu "głównego" wraz z wszystkimi elementami na prawo od niego
- wybierzmy wierzchołek najbardziej na lewo, który jesteśmy w stanie wstawić w trzech ruchach.
- wstawmy go do ciągu "głównego" wraz z wszystkimi elementami na prawo od niego
- wybierzmy wierzchołek najbardziej na lewo, który jesteśmy w stanie wstawić w czterech ruchach.
- wstawmy go do ciągu "głównego" wraz z wszystkimi elementami na prawo od niego
...

Mam nadzieję, że nieco się wyjaśniło odnośnie tego ciągu. Jeśli nie to proszę o kontakt :)

Algorytm Forda-Johnsona cz II.

2008-11-02T11:25:00.005+01:00

Algorytm Forda Johnsona służy do posortowania n-elementowej tablicy. Algorytm jest bardzo ciekawy z teoretycznego punktu widzenia, bo wykonuje bardzo małą liczbę porównań, bliską optymalnej. Algorytm działa optymalnie dla n < 16 oraz dla n = 20, 21, 22, a najmniejszy n dla którego znamy algorytm wymagający mniejszej liczby porównań to n = 47.

Na początku podzielmy tablicę n-elementową na pary i porównujemy je w tych parach. Jeśli liczba elementów jest nieparzysta to jeden element zostaje nieporównany.Elementy, które okazały się mniejsze w parach, sortujemy rekurencyjnie. Dla ułatwienia naszych dalszych rozważań ponumerujmy elementy. Największy numer dostaje element, który nie został jeszcze porównany (jeśli tablica ma nieparzyście wiele elementów). Resztę elementów numerujemy tak jak na rysunku.Teraz każdy element znajdujący się w ciągu "na dole" będziemy chcieli umieścić w ciągu "na górze". Szukając miejsca tego elementu, będziemy korzystać z wyszukiwania binarnego.
Kolejność w której będziemy wrzucać elementy z dołu do elementów na górze ma kolosalne znaczenie. Optymalną kolejnością wrzucania elementów jest następująca: 1, 3, 2, 5, 4, 11, 10, 9, 8, 7, 6, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 43, 42 ... . Element 1 wpisałem dla porządku, element ten jest już na swoim miejscu i nie trzeba nic z nim robić. Ciąg niemniej może wydawać się trochę skomplikowany. Już tłumaczę jak powstał. Można zauważyć, że po wszystkich liczbach zaznaczonych pogrubieniem, liczby maleją, aż skończą się nam liczby. Następnie pojawia się znowu pogrubiona liczba i liczby znowu zmniejszają się o jeden. Aby umieć wygenerować taki ciąg wystarczy zatem wiedzieć na jakiej podstawie wybieramy pogrubione liczby. Zauważmy, że sumy kolejnych dwóch liczb pogrubionych są równe kolejnym potęgom dwójki: 1 + 3 = 4; 3 + 5 = 8; 5 + 11 = 16; 11 + 21 = 32 itd.

Algorytm jest nieco skomplikowany. Jeśli są z nim jakieś problemy, albo trzeba coś jeszcze wytłumaczyć - to proszę o kontakt.

Algorytm Forda-Johnsona cz I.

2008-10-31T17:38:00.005+01:00

Spróbujmy posortować ciąg 5 liczb za pomocą 7 porównań. Oznaczmy te elementy jako a, b, c, d oraz e. Porównajmy element a z elementem b i załóżmy, że a jest mniejszy (ew. zamieńmy a z b miejscami). Porównajmy element c z d i przyjmijmy, że element c jest mniejszy. I wreszcie porównajmy element a z c i przyjmijmy, że element a jest mniejszy. Wykonaliśmy do tej pory 3 porównania, a sytuację w której się znaleźliśmy przedstawia poniższy rysunek.Spróbujmy teraz wcisnąć element e gdzieś do ciągu [a, c, d]. Możemy to zrobić za pomocą dwóch porównań (użyjemy wyszukiwania binarnego). Najpierw element e sprawdzamy z elementem c. Jeśli jest mniejszy to sprawdzamy z elementem a; w przeciwnym przypadku z elementem d. Trudno przewidzieć w którym miejscu stanie element e. Rozważmy dwa przypadki. Albo e jest najmniejszym elementem z tej trójki (a, c, d), albo nie jest. Ten drugi przypadek przedstawia poniższy rysunek.Jedyną rzeczą jaką trzeba teraz zrobić to wstawić element b pomiędzy elementy {c, d, e}. Identycznie jak poprzednio możemy to zrobić w dwóch ruchach.
W drugim przypadku, gdy element e jest najmniejszy, wystarczy element b porównać tylko z elementami c oraz d. To też możemy zrobić używając dwóch ruchów.

Reasumując. Na początku porównując elementy a, b, c oraz d - wykonaliśmy 3 porównania. Wpychając element e pomiędzy elementy [a, c, e] wykonaliśmy dodatkowe 2 porównania. Na końcu ustawiliśmy element b na swoje miejsce używając nie więcej niż 2 porównań. 3 + 2 + 2 = 7

W następnej notce uogólnimy ten algorytm na tablicę n-elementową.

Studia informatyczne to magia

2008-10-19T09:53:00.005+02:00

Znajomi moi często pytają się mnie czego ja się uczę na studiach informatycznych. Gdy odpowiadam, że na zajęciach piszemy algorytmy, mówimy jak działa komputer (na poziomie bramek logicznych), rozwiązujemy całki itp, to znajomi odpowiadają, że dla nich to czarna magia.

Jaka to czarna magia? - myślałem sobie - Wszystko to jest proste i logiczne! Jednak na pierwszych zajęciach z programowania funkcyjnego profesor UW Marcin Kubica (nie mylić z Robertem) wytłumaczył mi, że to jednak moi znajomi mają rację.

No bo co to jest magia? Cytując za Nową Encyklopedią Powszechną PWN jest to "Zespół działań, zasadniczo pozaempirycznych, symbolicznych, których celem jest bezpośrednie osiągnięcie (...) pożądanych skutków". Wszystko się zgadza, ale pójdźmy dalej.

Wyróżniamy przy tym następujące składniki działań magicznych:
- zrytualizowane działania
- materialne obiekty magiczne
- reguły obowiązujące przy praktykach magicznych
- formuły tekstowe mające moc sprawczą (zaklęcia)

Zrytualizowanymi działaniami jest na przykład wyłączanie komputera, logowanie się do sieci etc. Indeks i karta egzaminacyjna są materialnymi obiektami, które w istocie mają magiczną moc. Jest cała lista reguł obowiązująca przy praktykach magicznych (do sali komputerowej nie można wnosić jedzenia i/lub picia, nie wolno wnosić okryć wierzchnich ani dużych toreb... itp. itd). Natomiast formuły tekstowe mające moc sprawczą są istotą informatyki:

// Przykład formuły tekstowej mającej moc sprawczą

int main(void)
{
  printf("Hello World!\n");
  return 0;
}

Ale pójdźmy jeszcze dalej! Duch to obiekt niematerialny zdolny do działania. Spójrzmy na procesy obliczeniowe - nie można ich zobaczyć, ani dotknąć, ani powąchać, ale możemy obserwować skutki ich działania. Ba! Możemy się ich spytać o interesujące nas informacje.

Istna czarna magia!

Edit (01.01.2009):
Właśnie znalazłem, pasuje jak ulał. Z praw Murphy'ego:
Zasada Clarke'a:
"Każda dostatecznie zaawansowana technologia niczym nie różni się od magii."

3 wiadomości

2008-10-13T10:41:00.004+02:00

Mam do zakomunikowania 3 wiadomości.

Po pierwsze pojawił się nowy dział "Do pobrania", a w nim moja prezentacja z liceum na temat diagramów Voronoi. Wkrótce umieszczę tam więcej ciekawych rzeczy. Póki co rzeczy tam umieszczane znajdują się na chomiku. Prawdopodobnie przeniosę je jak znajdę jakieś lepsze miejsce (albo nie :)).

Po drugie niestety nie mam teraz stałego dostępu do internetu i notki niestety nie będą pojawiały się tak często jakbym chciał.

Po trzecie rozpoczął się konkurs ITPW. Więcej informacji na stronie http://www.mimuw.edu.pl/KNI/ITPW/.

Pozdrawiam!

Problemy z typami danych cz II.

2008-10-05T13:40:00.005+02:00

Do pomiaru rozmiaru struktur danych służy operator sizeof(). Sprawdzimy na początek ile pamięci zajmują wybrane standardowe typy danych.

#include <stdio.h>

int main(void)
{
  printf("%d\n", sizeof(char));
  printf("%d\n", sizeof(short));
  printf("%d\n", sizeof(int));
  return 0;
}

Program wypisze nam ile bajtów zajmuje każdy z następujących typów danych: char, short oraz int. Wyniki zwracane przez program będą różne dla różnych architerktur komputerów na których były uruchomione. Polecam uruchomienie tego programu na własnym komputerze. Na moim komputerze wyniki to: 1 bajt dla chara, 2 bajty dla shorta i 4 bajty dla inta.

Zbadamy teraz ile bajtów zajmują zdefiniowane przez nas struktury danych. Zaczniemy od prostej, lecz często stosowanej konstrukcji.

// Przykład 1

struct struktura
{
  char a;
};

sizeof(struktura) == 1;

Wszystko wygląda w porządku. Mamy w strukturze jedną zmienną typu char, która zajmuje 1 bajt. Zatem cała struktura zajmie nam w pamięci 1 bajt. Nic nadzwyczajnego tu się nie dzieje. Przejdźmy do drugiego przykładu.

// Przykład 2

struct struktura
{
  char a;
  short b;
};

sizeof(struktura) == 4;

Tutaj stało się coś dziwnego.. Zmienna char zajmuje 1 bajt, a zmienna short 2 bajty. Zatem intuicyjnie struktura zawierający te dwie zmienne, powinna zajmować 3 bajty. Natomiast sizeof() informuje nas, że struktura zajmuje aż 4 bajty! Czy to błąd kompilatora albo funkcji sizeof? A może celowe działanie? Spróbuję to wytłumaczyć w dalszej części tego artykułu. Na razie przyjrzyjmy się kolejnemu przykładowi:

// Przykład 3

struct struktura
{
  char a;
  int b;
  char c;
};

sizeof(struktura) == 12;

Pewnie spodziewaliśmy się, że i w tym przypadku rozmiar struktury będzie nieco większy niż wynikałoby to z prostej matematyki. Ale że struktura będzie zajmowała dwa razy więcej miejsca niż zmienne w strukturze? I to jeszcze nie koniec! Przyjrzyjmy się kolejnemu przykładowi.

// Przykład 4

struct struktura
{
  char a;
  char c;
  int b;
};

sizeof(struktura) == 8;

Struktura z praktycznego punktu widzenia nie różni się tak bardzo od poprzedniej. I tu i tu mamy po dwa chary i jednego inta. Zmienne nawet w obu przypadkach są tak samo nazwane! Różnica jest jedynie w kolejności w jakiej te zmienne występują. Dzięki tej z pozoru nieistotnej zmianie zyskaliśmy aż 4 bajty w pamięci. Dlaczego tak się dzieje? O tym w kolejnej części.

Problemy z typami danych cz I.

2008-09-28T10:03:00.010+02:00

Notka będzie najeżona dużą dawką informacji. Zacznijmy!
Na początek tabelka rozmiarów podstawowych typów danych.

char      1
short     2
int       4 (na 32-bitowych komputerach!)
long long 8

Przyjrzyjmy się bliżej typowi int. Jego zakres to -2³¹ ... 2³¹-1. Warto przy tym wspomnieć, że liczba 2³¹-1 (0x7fffffff) jest liczbą pierwszą. Zapamiętaj to! Znajomość dużych liczb pierwszych przyda Ci się przy kilku algorytmach.
W związku z tym, że mamy o jedną liczbę ujemną więcej niż dodatnią, rodzi się nasz pierwszy problem. Spójrzmy na następujący kod źródłowy programu C++:

int x = -2³¹;
int y = -x;
pritnf("%d\n", y);

Pierwsza linijka nie stanowi żadnego kłopotu (nie licząc tego, że kompilator jej nie zaakceptuje). Druga linia rodzi pewien problem. Teoretycznie zmienna x powinna przyjąć wartość 2³¹. Jednak ta liczba nie mieści się w zakresie inta. Pytanie: Jaką zatem wartość ma zmienna y?
Aby to ustalić spójrzmy jak w systemie binarnym zapisane są wybrane liczby całkowite.

 0    00000000 00000000 00000000 00000000
 1    00000000 00000000 00000000 00000001
-1    11111111 11111111 11111111 11111111
-2³¹  10000000 00000000 00000000 00000000

Prześledźmy działanie operatora unarnego "-":
- Negujemy wszystkie bity liczby
- Dodajemy do liczby jeden
Prześledźmy jak ten operator działa dla powyższych liczb. Zero poprawnie przechodzi na zero. Jeden przechodzi na minus jeden, a minus jeden na jeden. Natomiast -2³¹ przechodzi na... -2³¹. To nie koniec niespodzianek.

Przeanalizujmy następujący program:

printf("%d", 1 << 2);
printf("%d", 1 << 31);
printf("%d", 1 << 32);

Pierwsze dwie linie programu działają według naszych przypuszczeń. Pierwsza linijka wypisze na ekran "4", natomiast druga "-2³¹". Natomiast z trzecią linijką jest kłopot o czym informuje nas już kompilator: "warning: left shift count >= width of type". Na ekranie zostanie wypisane "0". Ale spójrzmy jeszcze na to:

int x = 32;
printf("%d", 1 << x);

Program nie powinien się różnić od poprzedniego przykładu, a jednak. Po pierwsze kompilator nie informuje nas o zagrożeniu (kompilator "nie może wiedzieć" czy wartość x przekracza dozwolony zakres). Po drugie, na ekranie zostanie wypisana "1". Procesor bowiem weźmie resztę z dzielenia liczby x przez 32 i o taką liczbę bitów przesunie 1 w lewo. Trzeba o tym pamiętać i mieć to na uwadze.

W drugiej części przedstawię kolejne problemy, tym razem z własnymi strukturami danych.

Przewidywanie skoków w procesorze

2008-09-26T12:58:00.009+02:00

Przeanalizujmy następujący program.

const n = 10000000;
int P[n];

for (int i = 0; i < n; i++)
  scanf("%d", &p[i]);

for (int i = 0; i < n; i++)
{
  if (p[i] < N/2) ++w;
  else ++y;

  if (p[(i+100)%N] < N/2) ++w;
  else ++h;
}

Program na wejściu dostaje permutację liczb 1, 2, ..., n. Program nie liczy nic ciekawego. Ważną rzeczą jest, że dla dowolnej permutacji każda instrukcja w programie zostanie wykonana dokładnie taką samą ilość razy. Mimo to dla permutacji <1, 2, ..., n> program działa szybciej niż dla jakiejkolwiek losowej permutacji:

Losowa permutacja: 4.07 s
Posortowane dane: 3.91 s

Minimalnej różnicy mogliśmy się spodziewać. Czas działania tego programu jest opóźniony przez operację wejścia / wyjścia. Jednak dlaczego program na posortowanych danych działa szybciej?

W każdym programie około 10% instrukcji to skoki. Problemem dla procesora są zwłaszcza tak zwane skoki warunkowe. Gdy procesor wykonuje jakąś komendę, to następne instrukcje już lądują w specjalnej kolejce do tego przeznaczonej. W sytuacji w której wykonujemy skok warunkowy, nie możemy stwierdzić które instrukcje powinny być następnie wykonywane, dopóki nie zostanie sprawdzony warunek. Jednak czekając tak długo tracimy cenne cykle procesora... Jest jednak wyjście z tej sytuacji.

Procesor gdy napotyka na skok warunkowy próbuje "przewidzieć" wynik skoku i odpowiednie instrukcje trafiają do kolejki. Jeśli procesor "zgadł", to instrukcje są wykonywane normalnie. W przeciwnym przypadku instrukcje znajdujące w kolejce są anulowane i wszelkie efekty działania tych instrukcji (tak, tak - procesor czasem wykona te operacje), a do kolejki trafiają poprawne instrukcje.

W sytuacji w której dane są posortowane - procesorowi będzie łatwiej przewidzieć skoki, podczas gdy dla losowych danych takie przewidywania są niemal niemożliwe. Dlatego program dla danych posortowanych działał szybciej.

Jaki jest morał z tego wykładu? Przecież zwykle nie mamy wpływu na dane wejściowe. Zgadza się! Ale czasami chcielibyśmy obliczyć ile program działa w najgorszym wypadku. Mimo, że permutacja <1, 2, ..., n> jest największa z możliwych, a każda instrukcja wykonywana jest w każdej permutacji taką samą ilość razy, to jednak to nie jest najgorsza możliwa permutacja dla tego programu.. Niejeden programista się na tym przejechał.

Mały FAQ dla chcących wiedzieć więcej:
Jak dobrze procesor "przewiduje skoki"? Bardzo dobrze. W zależności od procesora ok 70 - 90%.
Czy gra jest warta świeczki? Czy procesor po prostu nie mógłby poczekać aż zostanie obliczony warunek skoku? Nie! Jeśli w kolejce trzymanych jest 100 operacji to wśród nich jest około 10 skoków! Bez zgadywania w takiej sytuacji procesor byłby 10-krotnie mniej wydajny.
Na podstawie czego procesor przewiduje skoki? Istnieją dwie metody. Pierwsza z nich to metoda statyczna. Każdemu skokowi przyporządkowuje przepowiednię. Faktycznie - dla większości skoków możemy powiedzieć, która z opcji będzie częściej wykonywana po warunku. Druga metoda to metoda dynamiczna. Dla każdego skoku spamiętujemy jego ostatnie wyniki. Na podstawie nich obliczamy naszą "przepowiednię".
Coś więcej na temat algorytmu dynamicznego? Spragnionych wiedzy odsyłam do wyszukiwarki google.

MOKIP wykład

2008-09-26T10:42:00.007+02:00

Zostałem poproszony o przygotowanie wykładu dla Międzyszkolnego Olimpijskiego Kółka Informatycznego Pika (MOKIP). Wykład odbył się 25 września o godzinie 14:35 w VIII Liceum Ogólnokształcącym w Katowicach w sali 114.

Wykład podzielony był na dwie części. W pierwszej "poprawialiśmy" Cormena, w drugiej mówiliśmy o architekturze komputera.

1. Poprawianie Cormena

- ulepszony algorytm Grahama
- szukanie najbliższej pary punktów
- potęgowanie binarne

2. Architektura komputera

- problemy z typami danych
- wierszami czy kolumnami?
- cache procesora
- przewidywanie skoków w procesorze

Część materiałów z tego wykładu już znajduje się na blogu. Resztę umieszczę wkrótce.

Metoda włączeń i wyłączeń cz II.

2008-09-21T16:08:00.005+02:00

Przedstawię dwa proste zadania, które można rozwiązać za pomocą metody włączeń i wyłączeń.

Mamy danych 10 prostopadłościanów ortogonalnych (to znaczy takich, których krawędzie są równoległe do osi układów współrzędnych). Prostopadłościany te mogą na siebie nachodzić. Pytamy o sumę objętości tych prostopadłościanów.
Prostopadłościan ortogonalny może być zapisany za pomocą pary punktów: lewego, dolnego, "bliższego" (nam) oraz prawego, górnego, "dalszego". Powiedzmy, że pewien prostopadłościan jest określony za pomocą pary: (a₁, a₂, a₃) oraz (b₁, b₂, b₃). Jego objętość można wyrazić wzorem: (b₁-a₁)(b₂-a₂)(b₃-a₃).
Bardzo łatwo także wyznaczyć przecięcie dwóch prostopadłościanów, które także jest prostopadłościanem. Jeśli pierwszy z prostopadłościanów to (a₁, a₂, a₃) oraz (b₁, b₂, b₃), a drugi: (c₁, c₂, c₃) oraz (d₁, d₂, d₃) to prostopadłościan, który jest ich przecięciem to: (max{a₁, c₁}, max{a₂, c₂}, max{a₃, c₃}) oraz (min{b₁,d₁}, min{b₂,d₂}, min{b₃,d₃}).
Tak jak nauczyliśmy się w poprzedniej części - możemy teraz obliczyć sumę objętości prostopadłościanów na podstawię ich przecięć.

Drugie zadanie jest następujące. Mamy dany zbiór S = {1, 2, 3, ..., 10⁹}. Pytamy ile jest liczb w tym zbiorze, które są podzielne przez 9, 11 lub 15?
Oznaczmy przez D_k zbiór tych wszystkich liczb należących do S, które są podzielne przez k. Nie trudno zauważyć, że |D_k| = 10⁹ / k. Przy czym dzielenie tutaj rozumiemy jako dzielenie całkowitoliczbowe.
Tak samo łatwo można policzyć przecięcie dwóch zbiorów. Wystarczy tylko zauważyć, że:
Gdzie lcm(k, l) oznacza najmniejszą wspólną wielokrotność liczb k oraz l.
Zgodnie z opisaną w poprzedniej części metodą włączeń i wyłączeń możemy obliczyć sumę zdefiniowanych wzorów.

Dobrym ćwiczeniem będzie dla każdego implementacja powyższych algorytmów. Nie powinno to nikomu sprawić większych problemów, ale warto się oswoić z tą techniką.

Metoda włączeń i wyłączeń cz I.

2008-09-20T08:58:00.009+02:00

Zdarza się, że prosto jest policzyć liczbę elementów przecięcia kilku zbiorów, natomiast trudno liczbę elementów sumy tychże zbiorów. Przedstawimy metodę, dzięki której problem wyznaczenia sumy zbiorów sprowadzimy do wyznaczenia ich przecięć.

Dla dwóch zbiorów sytuacja wygląda prosto. Dodajemy ilość elementów zbioru pierwszego do ilości elementów zbioru drugiego i odejmujemy ilość elementów przecięcia obu zbiorów.
Dla trzech zbiorów sprawa się nieco komplikuje, ale wciąż wzór wygląda przystępnie. Najpierw sumujemy liczbę elementów poszczególnych zbiorów. Następnie odejmujemy liczbę elementów w przecięciach każdych dwóch zbiorów. Na końcu dodajemy liczbę elementów znajdujących się we wszystkich zbiorach.
Dla czterech zbiorów wzór robi się już nieczytelny. Bardzo niemiły jest też wzór dla dowolnego n:
Gdzie P₊(n) oznacza zbiór potęgowy zbioru {1, 2, ..., n} bez zbioru pustego.

Nie przejmuj się jeśli tego wzoru nie rozumiesz. Przedstawię teraz o wiele prostszą definicję metody włączeń i wyłączeń, którą łatwiej zapamiętać i łatwiej zastosować.

Aby znaleźć liczbę elementów sumy zbiorów A₁, A₂, ..., A_n znajdź liczby elementów wszystkich możliwych przecięć zbiorów spośród {A₁, A₂, ..., A_n}, dodaj do siebie wyniki uzyskane dla przecięć nieparzystej liczby zbiorów, a następnie odejmij wyniki uzyskane dla przecięć parzystej liczby zbiorów.

Dowód poprawności tej metody znajduje się na Wikipedii (http://pl.wikipedia.org/wiki/Zasada_w%C5%82%C4%85cze%C5%84_i_wy%C5%82%C4%85cze%C5%84).

Wadą tej metody jest oczywiście złożoność. Gdy mamy N zbiorów policzymy tą metodą liczebność 2^N-1 zbiorów. Niestety, niekiedy jest to najszybszy sposób.

W części drugiej przedstawię kilka przykładów zadań, które wymagają użycia tej metody.

Wyszukiwanie interpolacyjne

2008-09-18T11:35:00.007+02:00

Mamy daną posortowaną N-elementową tablicę zawierającą losowe liczby. Chcemy sprawdzić czy znajduje się wśród nich liczba k. Niejeden programista w tym miejscu krzyknie: "Wyszukiwanie binarne!". Pytanie: Czy można szybciej? Można!

Przypomnijmy może szybko implementację wyszukiwania binarnego:

int bsearch(int* A, int N, int k)
{
  int l = 0, r = N-1;

  while (l <= r)
  {
    int m = (l + r) / 2;

    if (A[m] == k) return m;
    else if(A[m] < k) l = m + 1;
    else r = m - 1;
  }

  return -1;
}

W poszukiwaniu interpolacyjnym korzystamy z następującego spostrzeżenia. Gdy przeszukujemy książkę telefoniczną szukając pana Wołodyjowskiego, to zazwyczaj nie otwieramy książki na stronie środkowej (jak to robi wyszukiwanie binarne) lecz na jej końcu. Z kolei gdy szukamy w książce pani Adamskiej to zaglądamy na początek książki. Aby zaimplementować ten algorytm, wystarczy w algorytmie wyszukiwania binarnego zamienić linijkę:

int m = (l + r) / 2;

na następującą:

int m = l + (k - A[l]) * (r - l) / (A[r] - A[l]);

Zaletą takiego rozwiązania jest złożoność. Algorytm dla tablicy wypełnionej losowymi wartościami używa mniej niż lg lg N + 1 porównań (dla przypomnienia - wyszukiwanie binarne wykonuje lg N + 1 porównań). Funkcja ta rośnie bardzo wolno. Dla przykładu lg lg 10³⁰⁸ < 10. A w przypadku, gdy tablica jest jeszcze regularniej ułożona niż w sposób losowy to liczba wymaganych porównań jest jeszcze mniejsza!

Wadą takiego rozwiązania jest koszt obliczenia wartości m (wykonujemy tutaj dużo operacji arytmetycznych) co dla nie wielkich wartości N może spowodować, że algorytm wyszukiwania binarnego będzie działał szybciej.

Ponadto algorytm nie nadaje się do wyszukiwania w tablicach, o których nie wiemy czy elementy w niej zawarte są równomiernie rozłożone. Algorytm dla przypadków pesymistycznych może wymagać nawet czasu liniowego.

Wyszukiwanie binarne po wynikach cz III.

2008-09-08T17:33:00.012+02:00

W poprzedniej części pokazaliśmy, że czasami łatwiej jest powiedzieć czy dana wartość spełnia warunki zadania, niż znaleźć najmniejszą z nich. W tej części przedstawię metodę, którą można rozwiązać wszystkie przedstawione w tej serii zadania. Przyjrzyjmy się najpierw jakie warunki musi spełniać zadanie, aby można było skorzystać z wyszukiwania binarnego po wynikach.

Aby móc skorzystać z opisanej poniżej metody, zadanie musi spełniać następujące warunki:

Szukamy element e który:

Spełnia warunki zadania
Jest najmniejszym {największym} takim elementem

Dla każdych elementów d oraz d' takich, że d < d' {d > d'} to jeśli d spełnia warunki zadania, to d' także

Drugi warunek może wydawać się dla niektórych skomplikowany. Dlatego rozpatrzymy go na przykładach:

Zadanie o krowach (d > d'). Jeśli potrafimy tak rozdzielić krowy, aby każda z nich była oddalona o conajmniej d jednostek od siebie, to potrafimy to też zrobić aby odległość między każdą z nich była większa o d' (wystarczy wybrać te same obory).

Zadanie o złodzieju (d > d'). Jeśli potrafimy tak wybrać przedmioty aby odpowiedni iloczyn był niemniejszy niż d, to potrafimy też tak je wybrać aby był niemniejszy od d' (wystarczy wybrać te same przedmioty).

Zadanie o zabytkach (d < d'). Jeśli potrafimy znaleźć po d dniach cykl w grafie, to potrafimy też znaleźć cykl po d' dniach (wystarczy "znaleźć" ten sam cykl).

Zatem drugi warunek mówi nam rzecz następującą. Podzielmy wszystkie elementy na dwa zbiory. W pierwszy zbiorze znajdą się wszystkie te liczby, które spełniają warunek zadania, a w drugim te które tego warunku nie spełniają. Każdy element w tym pierwszym zbiorze jest większy {mniejszy} niż każdy element w tym drugim. Prezentuje nam to poniższy rysunek:
Metoda wyszukiwania binarnego po wyniku przypomina zabawę w zgadywankę. Ja pomyślę o jakiejś liczbie. Ty będziesz zgadywał jaka to liczba, a ja będę mówił czy moja liczba jest większa czy mniejsza lub równa.

Pierwszym krokiem będzie znalezienie 2 elementów. Pierwszy z nich ma spełniać warunki zadania, a drugi nie. Oznaczmy je jako S_min oraz S_max.

Nasze rozwiązanie będzie znajdowało się gdzieś w środku (S_min, S_max). Policzmy średnią S_śr = (S_min + S_max) / 2. W zależności od tego czy S_śr spełnia czy nie spełnia warunków zadania, może zmniejszyć obszar naszych poszukiwań do (S_min, S_śr) lub (S_śr, S_max). Cały akapit powtarzamy dopóki nie będziemy pewni poprawnej odpowiedzi.

Istnieje wiele niepoprawnych algorytmów do zadań, które tu omówiliśmy. W następnej notce zaprezentuję kontrprzykłady do niektórych z nich.

Wyszukiwanie binarne po wynikach cz II.

2008-08-28T13:56:00.008+02:00

Przypomnijmy, że wszystkie zadania z części pierwszej to zadania optymalizacyjne. Szukamy największej (najmniejszej) wartości, która spełnia pewne określone warunki. W drugiej części zamiast szukać takiej wartości, sprawdzimy czy konkretna wartość k spełnia dane warunki.

Zadanie o krowach. Napiszmy algorytm, który zwróci prawdę jeśli da się tak ustawić krowy, aby każde dwie z nich były oddalone od siebie o co najmniej k jednostek. Zadanie to daje się rozwiązać zachłannie. Dla pierwszej krowy wybieramy oborę położoną najbardziej na lewo. Następnie usuwamy wszystkie obory, które znajdują się mniej niż k jednostek od tej. Powtarzamy to do momentu, w którym zabraknie nam krów lub miejsc w oborach. Jeśli braknie nam krów to znaczy, że da się tak ułożyć w oborach, aby każde dwie były oddalone od siebie o co najmniej k. Jeśli braknie nam obór, to oznacza że się nie da.

Zadanie o złodzieju. Sprawdzamy czy da się wybrać tak i przedmiotów, aby określony w zadaniu iloraz był większy bądź równy k. Dokonując kolejnych modyfikacji ilorazu, dostajemy następujący wzór (jako I rozumiemy w tym wzorze zbiór wybranych przez złodzieja przedmiotów):Wzór ten można łatwo sprawdzić. Wybieramy i przedmiotów, których wartość cena - k * waga jest najmniejsza wśród wszystkich przedmiotów. Jeśli suma tych wartości i przedmiotów jest większa lub równa od zera to znaczy że da się wybrać i przedmiotów aby iloczyn sumy cen do sumy wag był większy bądź równy niż k. Jeśli jest mniejsza od zera to nie da się.

Zadanie o zabytkach. Sprawdzamy czy po k dniach będzie można wybrać jakiś zabytek, a następnie autostradami przejechać przez kilka innych zabytków i wrócić do pierwszego. To zadanie z tych trzech jest chyba najprostsze. Bierzemy zabytki jako wierzchołki, k pierwszych autostrad jako krawędzie skierowane i sprawdzamy czy tak utworzony graf jest grafem cyklicznym.

Mamy trzy procedury, które w czasie liniowym (czyli bardzo szybko) mówią nam, czy k spełnia określone w zadaniach warunki. W następnej części napiszę, jak na podstawie tych funkcji napisać procedurę, która znajdzie najmniejsze (największe) takie k, które spełnia warunki zadania.

Wyszukiwanie binarne po wynikach cz I.

2008-08-26T12:21:00.008+02:00

W części pierwszej przedstawię trzy zadania. Wszystkie zadanie można rozwiązać za pomocą metody zwanej wyszukiwaniem binarnym po wyniku. Oto i one:

Zadanie o krowach. Farmer John wybudował nową oborę dla krów z N boksami. Boksy są ulokowane w linii prostej na pozycjach x₁, x₂, ..., x_N. John ma C (C <= N) krów. Przy czym nie lubią one przebywać blisko ze sobą. Dlatego John chce tak umieścić krowy w boksach, aby odległość między dwoma najbliższymi krowami była możliwie jak największa.

Zadanie o złodzieju. Mamy dane n przedmiotów. Każdy przedmiot ma określoną cenę oraz określoną wagę. Złodziej chce ukraść i przedmiotów. Przy czym chce wybrać tak przedmioty, aby stosunek sumy cen wszystkich ukradzionych przedmiotów do sumy ich wag była jak największa. Należy podać wartość iloczynu z dokładnością dwóch cyfr po przecinku.

Zadanie o zabytkach. Mamy w mieście n zabytków. Chcemy je połączyć m jednokierunkowymi drogami. W każdym dniu będzie budowana jedna droga. Kolejność budowy dróg jest ustalona. Pytamy o najmniejsze takie k, że po k dniach będzie istnieć ścieżka zaczynająca się i kończąca przy tym samym zabytku.

Proponuję, aby Czytelnik spróbował samodzielnie rozwiązać każde z powyższych zadań. W tym miejscu nie ważna jest złożoność Twoich rozwiązań, ale docelowo będziemy chcieli, aby rozwiązania działały w czasie liniowo-logarytmicznym.

W II części wyjaśni się co te na pozór różne zadania mają ze sobą wspólnego.

Wzory Cramera

2008-08-23T10:03:00.006+02:00

Powiedzmy, że mamy dany układ 2 (3) równań liniowych z 2 (3) niewiadomymi o współczynnikach całkowitych. Wiemy, że układ ma dokładnie jedno rozwiązanie. Chcemy je obliczyć, przy czym chcemy liczyć na liczbach całkowitych tak długo jak tylko się da. Świetnie do tego nadają się wzory Cramera.
Niech dany będzie następujący układ równań:
Macierzą A nazywamy macierzą współczynników tego układu, a macierz B macierzą wyrazów wolnych.
Macierz G_i powstaje w ten sposób, że w macierzy A kolumnę i-tą zastępujemy macierzą B. Dla przykładu macierz G₂ będzie wyglądał następująco:
Rozwiązanie naszego równania wygląda teraz następująco:
Gdzie det X oznacza wyznacznik macierzy X (http://pl.wikipedia.org/wiki/Wyznacznik_macierzy). Jeżeli wyznacznik macierzy A jest równy zero to układ równań nie ma rozwiązania (lub ma ich nieskończenie wiele).
Algorytm wyznacznika macierzy nie zawsze jest łatwa do implementacji. Jednak dla macierzy 2x2 oraz 3x3 obliczenie wyznacznika nie jest trudnym zadaniem.
Co ważne: podczas obliczania wyznacznika korzystamy z operacji dodawania, odejmowania i mnożenia. Nie wychodzi zatem poza liczby całkowite. Operację dzielenia dokonujemy dopiero na samym końcu.
Na koniec jeszcze powiem, że wzory Cramera działają dla każdego układu n równań z n niewiadomymi. Założenia o tym, że mamy tylko 2 (3) równania oraz że współczynniki są całkowite, poczyniliśmy aby pokazać w jakich sytuacjach najlepiej korzystać z metody tu przedstawionej.

Zapowiedzi

2008-08-21T10:50:00.000+02:00

W najbliższym czasie mam zamiar umieszczenie notek na następujące tematy:

Metoda węgierska
Twierdzenie Königa
Przewidywanie skoków w procesorze
Uproszczony algorytm Grahama
Wzory Cramera
Metoda włączeń i wyłączeń
Meet in the middle
Lemat Burnside’a

Jest to lista bardzo "luźna". Notki pojawią się prawdopodobnie w innej kolejności. Dopuszczam też możliwość umieszczenia w bliskiej przyszłości notek nie wymienionych w tym spisie.

Wierszami czy kolumnami? cz III. (Mnożenie macierzy)

2008-08-20T12:28:00.009+02:00

W niniejszej notce omówię algorytm mnożenia macierzy. Jeśli czytelnik z mnożeniem macierzy spotyka się po raz pierwszy to odsyłam do wikipedii (http://pl.wikipedia.org/wiki/Mno%C5%BCenie_macierzy). Operacja mnożenia macierzy jest tam bardzo ładnie wytłumaczona.
Przed napisaniem tej notki wyszukałem w googlach hasło "mnożenie macierzy C++". Pobieżne przejrzenie wyników potwierdziło moje przypuszczenia - zdecydowana większość programistów pisze pętle w złej kolejności. Przedstawmy najpierw typową implementację mnożenia macierzy:

const int N = 1000;
static int T[N][N];
static int A[N][N];
static int B[N][N];

for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
  {
    T[i][j] = 0;
    for (int k = 0; k < N; k++)
      T[i][j] += A[i][k] * B[k][j];
  }

Gdzie leży błąd można na pierwszy rzut oka nie zauważyć. Wytłumaczę to zatem, aby wszyscy mogli to zauważyć, a w razie innego algorytmu - powtórzyć rozumowanie.
Z tablicą T nie ma problemów. Wewnątrz pętli odwołujemy się do elementu T[i][j]. Przy czym przechodzimy ją po wierszach. To znaczy, że pętla iterująca po j-tach znajduje się wewnątrz pętli iterującej po zmiennej i. Podobna sytuacja jest z tablicą A. Odwołujemy się do elementu A[i][k], czyli przechodzimy ją po wierszach (pętla iterująca po zmiennej k znajduje się wewnątrz pętli iterującej po zmiennej i). Problem jest z tablicą B.
W przypadku tablicy B odwołujemy się do elementu B[k][j]. Przechodzimy ją zatem po kolumnach - pętla iterująca po j-tach znajduje się na zewnątrz pętli iterującej po zmiennej k. Procesor zatem nie będzie wczytywał optymalnie tablicy B do pamięci cache.
Możemy to poprawić przestawiając miejscami pętle ze zmienną k z pętlą ze zmienną j. Musimy też stworzyć osobne pętle zerujące tablicę.

const int N = 1000;
static int T[N][N];
static int A[N][N];
static int B[N][N];

for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
    T[i][j] = 0;

for (int i = 0; i < N; i++)
  for (int k = 0; k < N; k++)
    for (int j = 0; j < N; j++)
      T[i][j] += A[i][k] * B[k][j];

Tutaj już wszystko powinno działać w porządku. Wszystkie tablice przechodzimy po wierszach.
Przykład ten jest często wykorzystywany przy omawianiu przechodzenia tablicy po wierszach i kolumnach. Oba algorytmy mają nawet swoje nazwy potoczne. Pierwszy z nich nazywamy algorytmem ijk, natomiast drugi (jak nietrudno się domyślić) ikj.
Czas na przetestowanie obu rozwiązań. Różnica jest odczuwalna:
algorytm ijk - 0:13.63
algorytm ikj - 0:10.45
Motto tego trzy częściowego kursu jest następujące: "Iterowanie po wierszach przyśpiesza program". Czasem o kilka sekund, czasem nawet ośmiokrotnie. Warto o tym pamiętać bo przestawianie dwóch pętli nas nic nie kosztuje.

Wierszami czy kolumnami? cz II.

2008-08-20T09:15:00.007+02:00

Szybkość działania programu nie zależy wyłącznie od ilości wykonanych operacji. Na to czy program zadziała szybko ma wpływ wiele innych czynników. Dzisiaj poznamy jeden z nich.
Procesor posiada specjalną pamięć podręczną zwaną pamięcią cache. Jest ona o wiele szybsza od pamięci RAM. Gdy procesor potrzebuje jakiś danych to najpierw sprawdza czy są one dostępne w pamięci cache. Jeśli tak to świetnie! Dostaniemy do nich dostęp bardzo szybko. Jeśli nie - dostęp do tych danych potrwa nieco dłużej. Często będzie nam zależeć na tym, aby ten drugi przypadek starać się wykluczyć.
Procesor stara się przewidzieć jakie dane będą potrzebne w najbliższej przyszłości. Dwa podstawowe warunki jakimi sugeruje się procesor to:

Jeśli jakiś obiekt był ostatnio używany, to istnieje duże prawdopodobieństwo, że będzie używany w najbliższej przyszłości
Jeśli jakiś obiekt był ostatnio używany, to istnieje duże prawdopodobieństwo, że w najbliższej przyszłości będą używane obiekty leżące blisko niego

Jako elementy "blisko niego" rozumiemy tutaj elementy, które znajdują się koło niego w pamięci RAM (mają podobny adres maszynowy). Zadeklarujmy tablicę dwuwymiarową i sprawdźmy które elementy znajdują się koło których w pamięci. Podejrzewamy, że bezpośrednio koło elementu T[0][0] znajduje się albo element T[0][1], albo T[1][0]. Poniższy program rozwieje nasze wątpliwości.

const int N = 1000;
static char T[N][N];

printf("0x%08x\n0x%08x\n0x%08x\n0x%08x\n",
  &T[0][0], &T[0][1], &T[1][0], &T[0][N-1]);

Po uruchomieniu programu dostałem następujące wyniki (zachęcam do uruchomienia programu na własnym sprzęcie):

Zatem koło adresu T[0][0] znajduje się element T[0][1]. Natomiast element T[1][0] znajduje się o 1000 adresów dalej. Zachęcam do dalszych eksperymentów, w których wykażemy, że koło elementu T[0][1] znajduje się element T[0][2] itd.
Po analizie naszego programu możemy wywnioskować również, że w pamięci po elemencie T[0][N-1] występuje element T[1][0]. Najlepiej iterować tablicę dwuwymiarową w kolejności występowania elementów w pamięci - czyli w kolejności: T[0][0], T[0][1], ..., T[0][N-1], T[1][0], ..., T[N-1][N-1].
Wyjaśniło się nam zatem dlaczego algorytm iterujący po wierszach działa szybciej niż program iterujący po kolumnach. Starajmy się iterować w ten sposób tablice wielowymiarowe zawsze wtedy, kiedy mamy taką możliwość!
W następnej notce przedstawię często spotykany algorytm, w którym stosując poznaną tu sztuczkę zwiększymy szybkość jego działania o kilka sekund.

Wierszami czy kolumnami? cz I.

2008-08-19T12:51:00.012+02:00

Zaczniemy od czegoś bardzo prostego. Sztuczkę tą powinni znać wszyscy programiści. Przyjrzyjmy się poniższemu programowi, dynamicznie liczącemu wartość pewnej tablicy.

const int N = 10000;
static int t[N][N];

for (int i = 1; i < N; i++)
  for (int j = 1; j < N; j++)
    t[i][j] = max(t[i-1][j], t[i][j-1], t[i-1][j-1]);

Poniżej prezentuję ten sam program, z przestawionymi dwoma pętlami. Wyniki obu programów są takie same. Dla wyniku w tym przypadku nie ma bowiem znaczenia która pętla jest zewnętrzna a która wewnętrzna

const int N = 10000;
static int t[N][N];

for (int j = 1; j < N; j++)
  for (int i = 1; i < N; i++)
    t[i][j] = max(t[i-1][j], t[i][j-1], t[i-1][j-1]);

Policzmy jednak czasy działania obu programów (jak zwykle w tym miejscu polecam własne eksperymenty w domu). Wynik być może niektórych zaskoczy. Pierwszy program działa 3-4 razy szybciej. Oto przykładowe czasy działania algorytmów na moim sprzęcie:

Algorytm pierwszy - 0:26.26
Algorytm drugi - 1:13.37

Mojemu znajomemu po drobnej modyfikacji kodu udało się uzyskać następujące czasy:

Algorytm pierwszy - 0:01.23
Algorytm drugi - 0:09.67

Czyli pierwszy program działał 8 razy szybciej niż drugi.
Oba programy wykonują jednakową liczbę operacji i liczą dokładnie to samo (tylko w innej kolejności). Zatem dlaczego pierwszy z nich działa o wiele szybciej? Napiszę o tym w następnej notce.

Zaczynamy!

2008-08-17T21:33:00.000+02:00

Witam na moim nowym blogu poświęconym tematyce algorytmów. Wkrótce będziesz mógł przeczytać tutaj o algorytmach i strukturach danych, których nie znajdziesz w Cormenie, o sztuczkach programistycznych, o technikach projektowania algorytmów. Od czasu do czasu być może zamieszczę jakąś relację z konkursów programistycznych, w których będę brał udział. Albo umieszczę kody źródłowe jakiś większych programów.
To już mój drugi blog poświęcony algorytmom. Pierwszy był zbyt formalny, przez co straciłem chęć do dalszego jego pisania. Mam nadzieję, że tym razem będzie inaczej.
Pozdrawiam i życzę miłego czytania.