\thispagestyle{empty}
\begin{center}
\resizebox{131mm}{!}{
\includegraphics{figs/Info-ang2bszam_s}}
\end{center}


\newpage
\thispagestyle{empty}
\huge

\vspace{78cm}
\begin{center}
\textcolor{blue}{\textbf{ALGORITHMS}} 

\vspace{8mm}
\textcolor{blue}{\textbf{OF INFORMATICS}} 

\vspace{36mm}

\textcolor{blue}{\textbf{Volume 1}} 


\vspace{10cm}

\textcolor{magenta}{\textbf{AnTonCom}} \\


\textcolor{magenta}{\textbf{Budapest, 2010}}
\end{center}


\newpage
\thispagestyle{empty}
\normalsize

\begin{center}
This electronic book was prepared in the framework of project Eastern Hungarian 
Informatics Books Repository no. TÁMOP-4.1.2-08/1/A-2009-0046.
\nevindex{Eastern Hungarian Informatics Books Repository}
\nevindex{TÁMOP-4.1.2-08/1/A-2009-0046}
 
This electronic book appeared with the support of European Union and with the 
co-financing of European Social Fund.\nevindex{European Social Fund}\nevindex{European Union} 


\begin{center}
\resizebox{120mm}{!}{
\includegraphics{figs/UMFT+EUlogo}}
\end{center}


\vspace{4 mm}
\textbf{Editor:} Antal \hrefun{http://compalg.elte.hu/tanszek/tony/oktato.php?oktato=tony}
{Iványi}\nevindex{Iványi, Antal Miklós} 

\small
\vspace{4mm}
\textbf{Authors of Volume 1:} László \hrefun{http://www.cs.elte.hu/~lovasz}{Lovász} (Preface),\nevindex{Lovász, László}
Antal \hrefun{}{Iványi} (Introduction),\nevindex{Iványi, Antal Miklós}
Zoltán \hrefun{http://www.sapientia.ro/hu/dr.-kasa-zoltan.html}{Kása} (Chapter 1),\nevindex{Kása, Zoltán} 
Zoltán \hrefun{http://people.inf.elte.hu/csz/}{Csörnyei} (Chapter 2),\nevindex{Csörnyei, Zoltán} 
Ulrich \hrefun{http://www.tu-chemnitz.de/informatik/HomePages/ThIS/Tamm/}{Tamm} (Chapter 3),\nevindex{Tamm, Ulrich} 
Péter \hrefun{http://www.cs.bu.edu/fac/gacs/}{Gács} (Chapter 4),\nevindex{Gács, Péter} 
Gábor \hrefun{http://www.sztaki.hu/~ivanyos/}{Ivanyos}\nevindex{Ivanyos, Gábor} and 
Lajos \hrefun{http://www.sztaki.hu/~ronyai/}{Rónyai} (Chapter 5),\nevindex{Rónyai, Lajos} 
Antal \hrefun{http://compalg.inf.elte.hu/~ajarai/}{Járai}\nevindex{Járai, Antal} and 
Attila \hrefun{http://www.compalg.inf.elte.hu/attila}{Kovács} (Chapter 6),\nevindex{Kovács, Attila} 
Jörg \hrefun{http://www.cs.uni-duesseldorf.de/~rothe/}{Rothe} (Chapters 7 and 8),\nevindex{Rothe, Jörg} 
Csanád \hrefun{http://www.inf.u-szeged.hu/~cimreh/}{Imreh} (Chapter 9),\nevindex{Imreh, Csanád}
Ferenc \hrefun{http://www.sie.arizona.edu/faculty/szidar.html}{Szidarovszky} (Chapter 10),\nevindex{Szidarovszky, Ferenc}
Zoltán \hrefun{http://www.sapientia.ro/hu/dr.-kasa-zoltan.html}{Kása} (Chapter 11),\nevindex{Kása, Zoltán} 
Aurél \hrefun{http://uni-obuda.hu/users/galantai}{Galántai}\nevindex{Galántai, Aurél} and 
András \hrefun{mailto:matjy@gold.uni-miskolc.hu}{Jeney} (Chapter 12)\nevindex{Jeney, András}



\vspace{2mm}
\textbf{Validators of Volume 1:} Zoltán \hrefun{http://www.inf.u-szeged.hu/~fulop/}{Fülöp} (Chapter 1),\nevindex{Fülöp, Zoltán} 
Pál \hrefun{http://www.inf.unideb.hu/~domosi/}{Dömösi} (Chapter 2),\nevindex{Dömösi, Pál} 
Sándor \hrefun{mailto:http://numanal.inf.elte.hu/fridli.html}{Fridli} (Chapter 3),\nevindex{Fridli, Sándor} 
Anna \hrefun{htpp://www.cs.utexas.edu/~panni}{Gál} (Chapter 4),\nevindex{Gál, Anna} 
Attila \hrefun{http://www.inf.unideb.hu/~pethoe/}{Pethõ} (Chapter 5),\nevindex{Pethõ, Attila} 
Lajos \hrefun{http://www.sztaki.hu/~ronyai/}{Rónyai} (Chapter 6),\nevindex{Rónyai, Lajos}
János \hrefun{mailto:andog@compalg.inf.elte.hu}{Gonda} (Chapter 7),\nevindex{Gonda, János} 
Gábor \hrefun{http://www.sztaki.hu/~ivanyos/}{Ivanyos} (Chapter 8),\nevindex{Ivanyos, Gábor} 
Béla \hrefun{http://www.cs.elte.hu/vizvari}{Vizvári} (Chapter 9),\nevindex{Vizvári, Béla}
János \hrefun{http://www.unizh.ch/ior/Pages/Deutsch/Mitglieder/Mayer/Mayer.php}{Mayer} (Chapter 10),\nevindex{Mayer, János}
András \hrefun{http://www.cs.bme.hu/recski}{Recski} (Chapter 11),\nevindex{Recski, András}
Tamás \hrefun{http://www.math.bme.hu/~szantai/}{Szántai} (Chapter 12),\nevindex{Szántai, Tamás}
Anna \hrefun{http://www.nimfea.hu/kapcsolat/programvez.htm}{Iványi} (Bibliography)\nevindex{Iványi, Anna Barbara} 
 
\vspace{2mm}
\textbf{Authors of Volume 2:}  Burkhard \hrefun{http://www.cecs.csulb.edu/~englert/}{Englert},\nevindex{Englert, Burkhard} 
Dariusz \hrefun{darek@mpi-sb.mpg.de}{Kowalski},\nevindex{Kowalski, Dariusz} 
Gregorz \hrefun{http://www.cs.ua.edu/$\%$7Egreg/ad.html}{Malewicz},\nevindex{Malewicz, Grzegorz} and  
Alexander \hrefun{http://www.engr.uconn.edu/~aas/}{Shvartsman} (Chapter 13),\nevindex{Shvartsman, Alexander Allister} 
Tibor \hrefun{http://www.itk.ilstu.edu/faculty/tbgyires/tbgyires.htm}{Gyires} (Chapter 14),\nevindex{Gyíres, Tibor} 
Claudia \hrefun{http://www.se.e-technik.uni-kassel.de/pm/leopoldE.html}{Fohry} and\nevindex{Fohry, Claudia}
Antal \hrefun{http://people.inf.elte.hu/tony/}{Iványi} (Chapter 15),\nevindex{Iványi, Antal Miklós}
Eberhard \hrefun{http://www2.informatik.uni-jena.de/~nez/}{Zehendner} (Chapter 16),\nevindex{Zehendner, Eberhard} 
Ádám \hrefun{mailto:b_a_s@ludens.elte.hu}{Balogh} and\nevindex{Balogh, Ádám} 
Antal \hrefun{http://people.inf.elte.hu/tony/}{Iványi} (Chapter 17),\nevindex{Iványi, Antal Miklós} 
János \hrefun{http://www.sztaki.hu/sztaki/afe/infodep/demetrovics.jhtml}{Demetrovics} and\nevindex{Demetrovics, János} 
Attila \hrefun{http://www.renyi.hu/~sali/}{Sali} (Chapters 18 and 19),\nevindex{Sali, Attila} 
Attila \hrefun{mailto:kiss@ullman.inf.elte.hu}{Kiss} (Chapter 20),\nevindex{Kiss, Attila}
István \hrefun{}{Miklós} (Chapter 21),\nevindex{Miklós, István} 
László \hrefun{http://www.iit.bme.hu/~szirmay/szirmay.html}{Szirmay-Kalos} (Chapter 22),\nevindex{Szirmay-Kalos, László} 
Ingo \hrefun{http://www.minet.uni-jena.de/www/fakultaet/iam/l_althoefer.html}{Althöfer} and\nevindex{Althöfer, Ingo}
Stefan \hrefun{http://www.minet.uni-jena.de/www/fakultaet/iam/personen/stefan.html}{Schwarz} (Chapter 23)\nevindex{Schwarz, Stefan}


\vspace{2mm}
\textbf{Validators of Volume 2:} István \hrefun{}{Majzik} (Chapter 13),\nevindex{Majzik, István} 
János \href{http://it.math.klte.hu/user/jsztrik/}{Sztrik} (Chapter 14),\nevindex{Sztrik, János}
Dezsõ \hrefun{http://www.nik.hu/felepit.htm}{Sima} (Chapters 15 and 16),\nevindex{Sima, Dezsõ} 
László  \hrefun{mailto:varga@ludens.elte.hu}{Varga} (Chapter 17),\nevindex{Varga, László}
Attila \hrefun{mailto:kiss@ullman.inf.elte.hu}{Kiss} (Chapters 18 and 19),\nevindex{Kiss, Attila} 
András \hrefun{mailto:}{Benczúr} (Chapter 20),\nevindex{Benczúr, András}
István \hrefun{mailto:katsanyi@invitel.hu}{Katsányi} (Chapter 21),\nevindex{Katsányi, István} 
János \hrefun{http://aszt.inf.elte.hu/~jvida/}{Vida} (Chapter 22),\nevindex{Vida, János} 
Tamás \hrefun{http://www.math.bme.hu/~szantai/}{Szántai} (Chapter 23),\nevindex{Szántai, Tamás}
Anna \hrefun{http://www.nimfea.hu/kapcsolat/programvez.htm}{Iványi} (Bibliography)\nevindex{Iványi, Anna Barbara} 

\vspace{2mm}
\textbf{Cover art:} Victor Vasarely, \textit{Kubtuz}, 1983. With the permission of 
\hrefun{http://www.hungart.org/index.php}{\copyright \ HUNGART}, Budapest. 
The used film is due to \hrefun{http://www.goma.hu/}{GOMA Rt.} 

Cover design by Antal \hrefun{http://compalg.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}

\vspace{6mm}
\copyright \ 2010 AnTonCom Infokommunikációs Kft.\nevindex{AnTonCom Infokommunikációs Kft.} \\

Homepage: \hrefun{http://www.antoncom.hu/}{http://www.antoncom.hu/}


\end{center}
\normalsize
\tableofcontents

\chapter*{Preface} 
\addcontentsline{toc}{chapter}{Preface}

It is a special pleasure for me to recommend to the Readers the book
\textit{Algorithms of Computer Science,} edited with great care by
Antal Iványi.\nevindex{Iványi, Antal Miklós} Computer algorithms form a very important and fast
developing branch of computer science. Design and analysis of large
computer networks, large scale scientific computations and
simulations, economic planning, data protection and cryptography and
many other applications require effective, carefully planned and
precisely analyzed algorithms.

Many years ago we wrote a small book with Péter Gács\nevindex{Gács, Péter} \cite{LovaszGa86} under the
title \textit{Algorithms.} The three volumes of the book
\textit{Algorithms of Computer Science} show how this topic developed
into a complex area that branches off into many exciting directions.
It gives a special pleasure to me that so many excellent
representatives of Hungarian computer science have cooperated to
create this book. It is obvious to me that this book will be one of
the most important reference books for students, researchers and
computer users for a long time.

\vspace{6mm}
Budapest, July 2010

László Lovász\nevindex{Lovász, László}

\chapter*{Introduction} 
\addcontentsline{toc}{chapter}{Introduction}

\vspace{-8mm}
The first volume of the book \textit{Informatikai algoritmusok}
appeared in 2004 in Hungarian \cite{Infalg1}, and the second 
volume of the book appeared in 2005 \cite{Infalg2}. Two volumes contained 31 chapters: 23 chapters of the 
first and second volumes of the present electronic book, and further chapters on clustering, frequent elements in data bases, 
geoinformatics,\index{geoinformatics} inner-point methods,\index{inner-point methods} 
number theory,\index{number theory} Petri-nets,\index{Petri-nets} 
queuing theory,\index{queueing theory} and scheduling.\index{scheduling theory}

The Hungarian version of the first volume contains those chapters which were finished until May of 2004, 
and the second volume contains the chapters finished until April of 2005.

The printed English version contains the chapters submitted until April of 2007. Volume 1 \cite{AlgofInf1} contains 
the chapters belonging to the fundamentals of informatics, while the second volume \cite{AlgofInf2} 
contains the chapters having closer connection with some applications.

The first and second volumes of the given book represent an extended and corrected electronic 
version of the printed book written is English. The third volume of the present book contains new chapters.

The chapters of the first volume are divided into three parts. The chapters of Part 1
are connected with automata:  \textit{Automata and Formal Languages} (written by Zoltán Kása,\nevindex{Kása, Zoltán}
Sapientia Hungarian University of Transylvania), 
\textit{Compilers} (Zoltán Csörnyei, Eötvös Loránd University),\nevindex{Csörnyei, Zoltán} 
\textit{Compression and Decompression}  
(Ulrich Tamm, Chemnitz University of Technology Commitment),\nevindex{Tamm, Ulrich} 
\textit{Reliable Computations} (Péter Gács, Boston University).\nevindex{Gács, Péter}

The chapters of Part 2 have 
algebraic character: here are the chapters \textit{Algebra} (written by Gábor Ivanyos and Lajos Rónyai, 
Budapest University of Technology and Economics),\nevindex{Ivanyos, Gábor}\nevindex{Rónyai, Lajos} 
\textit{Computer Algebra} (Antal Járai and Attila Kovács, 
Eötvös Loránd University),\nevindex{Kovács, Attila}\nevindex{Járai, Antal} 
further \textit{Cryptology} and \textit{Complexity Theory} 
(Jörg Rothe, Heinrich Heine University).\nevindex{Rothe, Jörg} 

The chapters of the third part have numeric character: 
\textit{Competitive Analysis} (Csanád Imreh,\nevindex{Imreh, Csanád} 
University of Szeged), \textit{Game Theory} (Ferenc Szidarovszky, 
The University of Arizona)\nevindex{Szidarovszky, Ferenc} and 
\textit{Scientific Computations} (Aurél Galántai, \'Obuda University and  
András Jeney, University of Miskolc).\nevindex{Galántai, Aurél}\nevindex{Jeney, András}

The second volume is also divided into three parts. The chapters of Part 4 
are connected with computer networks: \textit{Distributed Algorithms} 
(Burkhard Englert, California State University;\nevindex{Englert, Burkhard}  
Dariusz Kowalski, University of Liverpool;\nevindex{Kowalski, Dariusz}
Grzegorz Malewicz, University of Alabama;\nevindex{Malewicz, Grzegorz} 
Alexander Allister Shvartsman,\nevindex{Shvartsman, Alexander Allister}  
University of Connecticut), \textit{Parallel Algorithms} 
(Claudia Fohry, University of Kassel\nevindex{Fohry, Claudia} and Antal Iványi, 
Eötvös Loránd University;\nevindex{Iványi, Antal Miklós}), 
\textit{Network Simulation} (Tibor Gyires, Illinois State University)\nevindex{Gyíres, Tibor} and  
\textit{Systolic Systems} (Eberhard Zehendner, Friedrich Schiller University).\nevindex{Zehendner, Eberhard}

The chapters of Part 5 are \textit{Relational Databases} and 
\textit{Query in Relational Databases} (János Demetrovics, Eötvös Loránd University\nevindex{Demetrovics, János} and  
Attila Sali, Alfréd Rényi Institute of\nevindex{Sali, Attila}
Mathematics), \textit{Semistructured Data Bases} (Attila Kiss,\nevindex{Kiss, Attila} Eötvös Loránd University) and 
\textit{Memory Management} (Ádám Balog,\nevindex{Balogh, Ádám} Antal Iványi,\nevindex{Iványi, Antal Miklós} Eötvös Loránd University). 

The chapters of the third part of the second volume have close connections with biology: 
\textit{Bioinformatics} (István Miklós, Rényi Institute of Mathematics),\nevindex{Miklós, István} 
\textit{Human-Computer Interactions} (Ingo Althöfer,\nevindex{Althöfer, Ingo} 
Stefan Schwarz,\nevindex{Schwarz, Stefan} Friedrich Schiller University),  
and \textit{Computer Graphics} (László Szirmay-Kalos,\nevindex{Szirmay-Kalos, László} 
Budapest University of Technology and Economics).

The chapters are validated by Gábor Ivanyos,\nevindex{Ivanyos, Gábor} István Majzik,\nevindex{Majzik, István} Lajos Rónyai,\nevindex{Rónyai, Lajos} 
András Recski,\nevindex{Recski, András} and Tamás Szántai\nevindex{Szántai, Tamás}  
(Budapest University of Technology and Economics), András benczúr,\nevindex{Benczúr, András} 
Sándor Fridli,\nevindex{Fridli, Sándor} János Gonda,\nevindex{Gonda, János} István Tatsányi,\nevindex{Katsányi, István} 
Attila Kiss,\nevindex{Kiss, Attila} László Varga,\nevindex{Varga, László} János Vida,\nevindex{Vida, János} and 
Béla Vizvári\nevindex{Vizvári, Béla} (Eötvös Loránd University), 
Dezsõ Sima (Óbuda University)\nevindex{Sima, Dezsõ} 
Pál Dömösi,\nevindex{Dömösi, Pál} János Sztrik,\nevindex{Sztrik, János} and Attila Pethõ\nevindex{Pethõ, Attila} (University of Debrecen), 
Zoltán Fülöp\nevindex{Fülöp, Zoltán} (University of Szeged), 
Anna Gál\nevindex{Gál, Anna} (University of Texas), 
János Mayer\nevindex{Mayer, János} (University of Zürich).

The first and second volumes contain verbal description, pseudocode and analysis of over 200 algorithms, and  
over 350 figures and 120 examples illustrating how the algorithms work. 
Each section ends with exercises and each chapter ends with problems. 
In the two volumes you can find over 330 exercises and 70 problems.

We have supplied an extensive bibliography, in the section \textit{Chapter Notes} 
of each chapter. In the bibliography the names of the authors, journals and publishers are 
usually active links to the corresponding web sites (the living elements are underlined in 
the printed version and on the screen too).

The \LaTeX \ style file was written by Viktor Belényesi,\nevindex{Belényesi, Viktor} 
Zoltán Csörnyei,\nevindex{Csörnyei, Zoltán} László Domoszlai\nevindex{Domoszlai, László} 
and Antal Iványi.\nevindex{Iványi, Antal Miklós} 
The figures was drawn or corrected by Kornél Locher.\nevindex{Locher, Kornél} 
Anna Iványi\nevindex{Iványi, Anna Barbara} transformed the bibliography into hypertext. 
The DOCBOOK version was made by Marton 2001. Kft.\nevindex{Marton 2001. Kft.}

Using the data of the colofon page you can contact with any of the creators of the book.  
We welcome ideas for new exercises and problems, and also critical remarks or bug reports. 


The publication of the printed book was supported by 
Department of Mathematics of Hungarian Academy of Science, and the electronic 
version received support from European Union and from the European Social Fund.


\vspace{4mm}
Budapest, December 10, 2010

\vspace{4mm}


\hspace{5cm} Antal Iványi (\hrefun{mailto:tony@compalg.inf.elte.hu}{tony@compalg.inf.elte.hu})
\nevindex{Iványi, Antal Miklós}


