Podatkovne strukture in algoritmi PoStrInA

Na naslovu http://valjhun.fmf.uni-lj.si/PoStrInA se bodo počasi pričele zbirati prispevki o podatkovnih strukturah in algoritmih.

Vabilo

Če imate kakršna koli vprašanja / komentarje / popravke / ideje / ..., ali vas samo področje podatkovnih struktur in algoritmov posebej zanima, vas vabim, da se oglasite po elektronski pošti na Andrej.Brodnik@IMFM.Uni-Lj.SI ali neposredno na enega od mojih naslovov . Vsakomur se bom z veseljem odzval.

Nekaj priporočene literature

Prva knjiga, ki sem jo omenjal, in katera vsebuje dokaj celovit pregled znanj s tega področja je

T.H. Cormen and C.E. Leiserson and R.L. Rivest: Introduction to Algorithms, MIT Press, Cambridge, Massachusetts, 1990 (ISBN 0-262-03141-8, 0-07-013143-0).

Poleg tega so zanimivi vsi trije zvezki knjige (takorekoč ,,biblija računalništva``):

D.E. Knuth, The Art of Computer Programming Addison-Wesley, Reading, Massachusetts, 1973. (Fundamental Algorithms, Sorting and Searching

Snov je v teh zvezkih predstavljena veliko celoviteje kot v prvi knjigi. Zadnja izdaja (izšla lansko leto) je tudi dopolnjena v primerjavi z ono iz konca šestdesetih oziroma začetka sedemdesetih let. Zadnja izdaja bo tudi razširjena, saj Knuth obljublja še četrti in peti zvezek ([]).

Tej knjigi (knjigam) je primerljiva zbirka malce starejšega datuma:

K. Mehlhorn, Data Structures and Algorithms, Springer-Verlag, Berlin, 1984 (ISBN 3-540-13642-8).

Tudi ta zbirka vsebuje tri zvezke. Za razliko od Knuthove zbirke, obravnava podatkovne strukture in algoritme do manjše podrobnosti in morda malce bolj ,,računalniško``. Takorekoč ,,iz`` te zbirke je nastala knjižnica učinkovitih podatkovnih tipov in algoritmov LEDA (v resnici LEDA vključuje precej sodobnejših podatkovnih struktur in algoritmov, ki v zbirki še sploh niso omenjeni).

Za pomoč pri analizi algoritmov (in problemov) je nepogrešljiva knjiga:

R.L. Graham and D.E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley Publishing Co., Reading, Massachusetts, 1989 (ISBN 0-201-14236-8).

Knjiga je ,,matematično`` usmerjena, a ostane v okviru znanj potrebnih pri analizi algoritmov.

Za ,,hitrejše`` (in ne tako poglobljeno) branje so na voljo še vsaj knjige:

M.A. Weiss, Data Structures and Algorithm Analysis, The Benjamin/Cummings Publishing Company, Redwood City, California, 1992 (ISBN 0-8053-9052-9).
H.R. Lewis and L. Denenberg, Data Structures & Their Algorithms, Harper-Collins Publishers, New York, New York, 1991 (ISBN 0-673-39736-X).
R. Sedgewick, Algorithms, Addison-Wesley, Reading, Massachusetts, 1988 (ISBN 0-201-06673-4, novejše izdaje vsebujejo kodo v c++ in pascalu).

V skrivnosti računske geometrije vas bosta popeljali (starejši) knjigi

F.P. Preparata and M.I. Shamos, Computational Geometry (2. izdaja), Texts and Monographs in Computer Science, Springer-Verlag, Berlin, 1985
H. Edelsbrunner, Algorithms in Combinatorial Geometry, EATCS Monographs in Theoretical Computer Science, Springer-Verlag, Berlin, 1987 (ISBN 3-540-13722-X).

Dokaj podroben pregled podatkovnih struktur je na voljo v

G.H. Gonnet and R. Baeza-Yates, Handbook of Algorithms and Data Structures, International Computer Science Series, Addison-Wesley, Reading, Massachusetts, 1991 (ISBN 0-201-41607-7).

Velika večina podatkovnih struktur predstavljene v priročniku, ki tudi je bolj priročnik kot študijska knjiga, je tudi implementirana v jeziku c ali pascal ([]).

Masrsikaj o podatkovnih strukturah in algoritmih je na voljo tudi na internetu.

Ne nazadnje je za vse, ki želijo izvedeti še več o teoretičnem računalništvu, na voljo izredna zbirka preglednih člankov iz različnih področij računalništva (do približno leta 1990):

J. van Leeuwen, Handbook of Theoretical Computer Science, Elsevier, Amsterdam, Holland, 1990 (ISBN 0-444-88071-2).

Knjiga sestoji iz dveh zvezkov, od katerih je prvi, Algorithms and Complexity, za obravnavano področje, zanimivejši. Drugi zvezek ima naslov Formal Models and Semantics.

To in ono

Dvanajstega svečana 2002 je na torkovem seminarju govoril Sergi(o) Cabello o Cuttings and spanning trees with low crossing number.