Neural Networks - A Systematic Introduction

Book by Raul Rojas: http://page.mi.fu-berlin.de/rojas/neural/index.html.html.

Farscape

Few weeks ago I heard part of a track from Farscape by Klaus Schulze & Lisa Gerrard. I've felt in love and decided to grab the CDs as fast as I can. Definitively one of the best piece of music I have ever heard... masterpiece.

Text algorithms - book

Book by M. Crochemore and W.Rytter is available in a PostScript format:
http://web.njit.edu/~rytter/TEACHING/TEXTS/book.html. I don't see any copyright/licensing notices, but we probably can assume that is free for private use.

Update (2011-04-14): book is freely available on M. Crochemore's site, in a PDF format, just click.

Demovibes Live

What can I say? New demovibes set, live remixes is available. Thanks Willb.

"Wprowadzenie do grafiki komputerowej"

Piszę o książce Foleya, van Dama, et al., w przekładzie prof. Jana Zabrodzkiego.

WNT wciąż sprzedaje i reklamuje ten podręcznik słowami "oto książka uznawana w świecie za najlepszą pozycję dotyczącą grafiki komputerowej". Nie mogę zaprzeczyć, że książka jest dobrą pozycją, np. rozdziały o modelu wirtualnej kamery, barwie, czy rasteryzacji są wyśmienite i "ponadczasowe" (fakt, rasteryzacją mało kto się teraz zajmuje, ale warto wiedzieć, może przyjdzie nam coś narysować na jakimś 8051?).

Proszę jednak pamiętać, że to jest przekład książki ukończonej w 1990 roku, czyli 18 lat temu; pierwsze polskie wydanie ukazało się w 1995. W międzyczasie postęp w dziedzinie informatyki nastąpił ogromny. Rozdziały o generowaniu fotorealistycznych obrazów mówią ledwie o podstawowych metodach, nie ma opisanych wielu modeli oświetlenia, nie ma bardziej zaawansowanych metod generowanie obrazów (path-tracing, bidirectional path-tracing, photon mapping, subsurface-scattering). Rozdział o krzywych i powierzchniach parametrycznych jest bardzo krótki, o wiele lepiej zaglądnąć do "Podstaw modelowania krzywych i powierzchni" P. Kiciaka (WNT 2005), choć to pozycja dość ciężka. O CSG są dosłownie dwie strony; z resztą wiele problemów jest wyłącznie zasygnalizowanych - np. antyaliasing przy rasteryzacji, budowanie drzew BSP i inne. (Jeśli chodzi o algorytmy graficzne to WNT wydało w 2006 świetną "Goemetrię obliczeniową" van Berga et al.).

Gdy kupiłem "Wprowadzenie..." chyba w 2000 roku, może wcześniej, wówczas o powszechnym dostępie do Internetu można było pomarzyć - książka to było coś, była - nie bójmy się tego określenia - oknem na świat. Poza tym raczej nie było alternatyw, no może poza jedną na wpół sensowną książką "Grafika PC bez tajemnic". Obecnie wszystko to można znaleźć po paru klikach w Sieci, choćby przez angielską Wikipedię, która zwykle ma bardzo ciekawe linki zewnętrzne. Przy okazji polecam dwie strony o grafice i krzywych.

Więc jeśli ktoś rozważa kupno tej pozycji to powiedziałbym tak: jeśli wydanie 60-70 złotych nie stanowi dużego problemu, warto mieć pod ręką. W przeciwnym razie lepiej wydać tę kwotę na wspomnianą "Geometrię..." albo "Podstawy...", bo ceny porównywalne.

VIPER - Visual Pascal InterpretER

Nice on-line Pascal interpreter with data structures visualiztion (trees, linked lists, etc.). Link: http://viper.mimuw.edu.pl/.

WikiSpam

Enlarge your Wikipedia for free.

Error Resilience in Compressed Data

I've found very interesting PhD thesis "Error Resilience in Compressed Data — Selected Topics" by Marek Biskup; author concentrated on decoding broken messages encoded with Huffman codes. Additionally parallel decoding of Huffman-coded messages is shown.

Kompresja danych

Zakupiłem ostatnio książkę Artura Przelaskowskiego "Kompresja danych" (BTC 2005). To co do tej pory przeczytałem robi bardzo dobre wrażenie, wydaje mi się jakoś bardziej przyjazne od "Wprowadzenie do kompresji" Adama Drozdka.

Jednakże jednej rzeczy mi brakuje: indeksu; to naprawdę ważna rzecz dla czytelnika, kiedy często sięga po pozycję. Poza tym wydaje mi się, że rezygnacja z wcięć akapitowych ekstrawagancka jest.

Informatyka na Wikipedii

Kiedy w 2003 roku trafiłem na polską Wikipedię, był to projekt raczkujący, ledwie 20 tysięcy haseł (teraz 500 tysięcy i rośnie!). Wówczas wyczytałem na stronie jednej z osób, że jest informatykiem, ale zajmuje się innymi dziedzinami, bo "informatyka jest wyeksploatowana". To oczywista bzdura była i niestety jest nadal. Informatyka to bardzo zapuszczona działka. Przedwczoraj poprawiłem nieco hasło wątek - jego wcześniejsza wersja absolutnie nie dawała odpowiedzi na pytanie "czym jest wątek?". Nawet osoba, która raz w życiu napisała prosty program i od czasu do czasu "grepuje gzipy" nie byłaby w stanie skumać OCB, a cóż dopiero zwykły człowiek.

Moim marzeniem są hasła przystępnie napisane zarówno dla praktyków, teoretyków jak również zwykłych czytelników. Żeby ten ostatni przeczytał i mniej więcej wiedział czym jest to, o czym czytał, praktyk żeby widział jakie są podstawy teoretyczne, a teoretyk jakie zastosowania praktyczne.

Już niedługo Jerzy Ludwichowski poprowadzi dyskusję na konferencji Polskiego Towarzystwa Informatycznego właśnie na ten temat. Mam nadzieję, że m.in. dzięki temu Wikipedia przyciągnie większą liczbę profesjonalistów, nauczycieli akademickich, ażeby nasze wspólne dzieło było jak najlepsze.

BTW to ostatnie brzmi jak wyimek z manifestu Marksa, ale po prawdzie Wikipedia to najlepszy przykład an-archistycznego projektu. Wyobraźcie sobie jak wyglądałaby Wikipedia, gdyby w rządzie był minister do spraw Wikipedii, zaś budżet finansował serwery. Wyglądałoby to pewnie jak Polska Biblioteka Internetowa - 3 miliony złotych w plecy, bo funkcjonalność na poziomie Web 0,0001, zasoby biedne, skany kulawe. A na moje pytania ile w tym roku MSWiA wydało na PBI ministerialne biurwy nie odpowiedziały.

LZP - metoda kompresji

Jeśli kiedyś będziecie potrzebowali wiedzieć jak działa algorytm LZP, to na coraz bardziej niezawodnej Wikipedii znajdziecie. Dla stron polskich G**gle zwraca 10 stron na krzyż.

Bylejakość

Na pewnej popularnej stronie dla programistów czytamy (przez litość nie podaję linku):

Krzywa Beziera to krzywa wielomianowa trzeciego stopnia, czyli taka która może być definiowana za pomocą trzech wielomianów (odpowiednio dla współrzędnych x, y i z) z pewnym parametrem t.

Ludzie, co za kosmiczne bzdury! Wielomianowa krzywa Beziera nie ma ograniczonego stopnia, stopień wielomianów może być dowolny. Sama zaś krzywa Beziera jest krzywą parametryczną.

Z tego tekstu wynika, że liczba wielomianów potrzebnych do określenia krzywej jest równa stopniu wielomianu -- tak oczywiście nie jest. Liczba wielomianów zależy od liczby wymiarów przestrzeni w której określana jest krzywa, wielomiany mogą być dowolnego stopnia; np. można mieć krzywą przestrzenną (czyli 3 wielomiany) ale wielomiany stopnia 125.

Dalej, co to znaczy "wielomiany z pewnym parametrem"? Ja pamiętam jeszcze ze szkoły średniej zadania w rodzaju "dla jakiego parametru c wielomian jakiśtam nie ma pierwiastków", ale tutaj rzecz jasna nie chodzi o to. Mowa oczywiście o wielomianach jednej zmiennej, zwyczajowo argument jest tutaj oznaczany literką 't', a nie 'x' jak się przyzwyczailiśmy.

Dalej jest jeszcze jeden cymes:

Krzywe trzeciego stopnia są również krzywymi najniższego stopnia, które nie leżą w jednej płaszczyźnie w 3D.

Czyli, że co -- nie można określić w przestrzeni krzywej trzeciego stopnia, która leżałaby na płaszczyźnie? (Odpowiedź brzmi oczywiście: nie, na całe szczęście można). A poza tym "w jednej płaszczyźnie" -- ale z czym? Bez sensu kompletnie. O co więc chodzi: krzywa 3-stopnia opisywana jest 4 punktami kontrolnymi, i taka liczba punktów może być niewspółpłaszczyznowa, a co za tym idzie krzywa nie będzie płaska.

Dlaczego o tym piszę? Bo razi mnie taka bylejakość, a poza tym lubię się czasem przypieprzyć; na Wikipedii taki tekst by chyba na pewno nie przeszedł (z resztą mamy na wiki całkiem nieźle opracowany temat krzywych i powierzchni Beziera).

27.08.2008 - dwie drobne poprawki

Wrap me!

Inheritance is fundamental way of creating new types in OOP. Apart of this, there is another important technique: composition, using many object to create higher level objects that provide interface to selected members of component objects. Inheritance is supported by many languages at syntax level, composition -- not!

Consider simple (real-world) example: we have GUI objects -- static label, and list box, we want another widget, labeled list box, a composition of these two simple widgets. We have to write tons of wrappers, that just call label or list methods. Here is example (C++):

class Label {
 public:
  void set_text(string s);
  string get_text();
};


class ListBox {
 public:
  void   clear();
  int    add_item(string s, bool uppercase);
  string get_item(int index);
};


class LabeledListBox {
 public:
  void   set_label(string s) {label.set_text(s);}
  string get_label() {return label.get_text();}

  void   clear() {box.clear();}
  int    add_item(string s) {return box.add_item(s, false);}
  int    add_item_uppercase(string s) {return box.add_item(s, true);}
  string get_item(int index) {return box.get_item(inex);}
 private:
  Label label;
  ListBox box;

};

Of course C++ compiler is able to inline LabeledListBox methods, but programmer have to write many lines of code that merely call another methods. He must know types of arguments, returned values and other. And if some class is changed, he must update classes that use this one. He must maintain all these stupid wrappers. Wrappers are evil.

Wrappers are so frequently used in programming, that I'm still don't know why syntax of popular languages do not reflect this state. This is my view of syntax, but I hope shows the intention -- simple things should remain simple on screen:

class LabeledListBox {
 public:
  method set_label is label.set_text; // rename
  method get_label is label.get_text; // rename

  method clear, get_item from box; // publish two methods of box object
  method add_item is box.add_item with uppercase=false;  // create simple wrappers
  method add_item_upperacase is box.add_item with uppercase=true; // with default arguments set to const

 private:
  Label label;
  ListBox box;
};

Coroutines in C++

What a surprise, there is a portable library for coroutines written 9 years ago by Keld Helsgaun.

Today I compiled some examples using gcc (MinGW) and seems to work! Great! I will try to explore this library and show some additional examples.

More constraints, please

In C++ classes have public, protected and private members. Variable member can be also declared as const or static const and it make such member read-only.

But it would be really great if we can select level of protection, and declare that some variable is const only when accessed at public or protected level. Here is a sample:

class C1 { // C++ - present
 public:
  void foo_x() { /* do some magic with x */ x = 5; }
  int get_x() const { return x;}

 private:
  int x;
};

class C2 { // C++ - future?
 public:
  void foo_x() { /* do some magic with x */ x = 5; }
 
 public const:
  int x;
}

Member x can be freely read/write within C2 member functions, but when accessed from outside, x is read only.

This is not as powerful as Borland's extension __property, which allow to declare property as alias for member variable, or setup getter/setter for a property. However I think proposed extension wouldn't bring much work for compilers authors.

With C++

C++ has lack of everything useful, you won't find local functions for example. But I really miss Pascal with statement. I know people say that would confuse programmer or even compiler. Wait! Pascal programmers were not confused, Pascal compilers were able to deal with this. Moreover, C++ programmers are not confused with tons of nested name spaces, crazy visibility rules and other odds.

Here is a snippet from my program:

for (unsigned i=0; i < data.measure_dist.size(); i++)
  if (data.measure_dist[i].active)
     find_crosspoints(
         data.measure_dist[i].point_1,
         data.measure_dist[i].point_2,
         outline,
         data.measure_dist[i].crosspoints
     );

Using with would make this much clearer:

for (unsigned i=0; i < data.measure_dist.size(); i++)
  with (data.measure_dist[i]) {
     if (active)
         find_crosspoints(point_1, point_2, outline, crosspoints);
  }

Does anybody confused about this code? Does anybody don't know what above code do? I don't think so.

Lets continue. With could also accept more complex syntax and allow temporary rename different entities. This (inefficient!) code finds all intersection between two sets of segments:

double u, v; // parameters, lerp(A, B, u) = A + u*(B-A)
for (int i=0; i < data.points.inner.size() - 1; i++)
  for (int j=0; j < data.points.outer.size() - 1; j++) {
      bool b = intersection(
          data.outline.inner[i],
          data.outline.inner[i+1],
          data.outline.outer[j],
          data.outline.outer[j+1],
          u, v);

      if (b)
          crosspoints.add(lerp(data.outline.inner[i], data.outline.inner[i+1], u));
  }

Now compare with following code:

double u, v;
with (data.points) {
  with (inner as A, outer as B) {
      for (int i=0; i < A.size() - 1; i++)
          for (int j=0; j < B.size() - 1; j++)
              if (intersection(A[i], A[i+1], B[i], B[i+1]))
                  crosspoints.add(lerp(A[i], A[i+1], u));
      }
}

Code is easier, cleaner, compacted. In next posts I will show some other ideas.

demoscene.tv

For a years I was big fan of demoscene. When I was young, demos and intros (some watched over and over, like "Jizz" by TBL) pushed me to learn many new things; moreover I still like to listen demoscene music; for example tracks from music disc "Ambrozia" released by group Pulse around 10 years ago still sound nice.

Now youtube is full of old and new demos uploaded by Good People. But on the net there are Much Better Good People, who created http://demoscene.tv - you can watch demos in high quality, yeah. BTW I love "Photon" by Purple.