Labirynt

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)

5 najbardziej spektakularnych błędów oprogramowania

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!".

Studia informatyczne to magia

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."