Articles and other writings by Martin Mareš

Mathematics and Computer Science

The Saga of Minimum Spanning Trees [English, 2008-05-05]
My PhD thesis on graph algorithms and especially problems related to minimum spanning trees and ranks of combinatorial structures.
In: Computer Science Review, Volume 2, Issue 3, Elsevier, 2008, pp. 165-221
Linear-Time Ranking of Permutations (with Milan Straka) [English, PS, 2007-04-27]
A simple algorithm for calculating lexicographic rank of a permutation or a k-permutation in linear time using data structures encoded in integers.
In: Algorithms – ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings, LNCS 4698, Springer Verlag, Berlin 2007
Two Linear Time Algorithms for MST on Minor Closed Graph Classes [English, 2002-03-14]
My small contribution to research on the Minimum Spanning Tree problem. This paper presents two MST algorithms running in linear time for any class of graphs closed on graph minors (i.e., deletions and contractions of edges), which also includes planar graphs and graphs of bounded genus.
In: Archivum mathematicum, Volume 40 (2003), No. 3, pp. 315-320
2-Edge-Connectivity in Dynamic Graphs [Czech, 2000-08-08]
My diploma thesis on data structures for dynamic and semi-dynamic graph algorithms, especially connectivity, spanning trees and 2-edge-connectivity

Programming Contests

Computer Maintenance via Batch Execution [English, PDF, 2013-05-01]
Organization of programming contests often involves maintenance of hundreds of computers. We present a simple, yet powerful batch processing system, which makes this task easier.
In: Olympiads in Informatics, 2013, Vol. 7, 55-60
A New Contest Sandbox (with Bernard Blackham) [English, PDF, 2012-04-02]
We present a new construction of a sandbox for automatic evaluation of programs at programming contests. It is based on recently added container features of Linux kernel. Unlike previous sandboxes, it has no measurable overhead and is able to handle multi-threaded programs.
In: Olympiads in Informatics, 2012, Vol. 6, 100-109
Fairness of Time Constraints [English, PDF, 2011-04-26]
When programs are being tested automatically (e.g., submissions in a programming contest), strict limits on execution time are usually imposed. Are they really fair? We try to shed some light on the precision and repeatability of program timing.
In: Olympiads in Informatics, 2011, Vol. 5, 92-102
Moe – Design of a Modular Grading System [English, PDF, 2009-02-28]
A follow-up on my previous paper on grading systems, describing the design of Moe in more detail.
In: Olympiads in Informatics, 2009, Vol. 3, 60-66
Perspectives on Grading Systems [English, PDF, 2007-05-31]
A description of the MO-Eval system for automatic grading of programming contest tasks and perspectives on further development of such systems.
In: Olympiads in Informatics, 2007, Vol. 1, 124-130

Teaching

Krajinou grafových algoritmů [Czech]
Turistický průvodce grafovými algoritmy pro středně pokročilé (aneb skriptíčka k mé přednášce).
Jak psát... [Czech, PDF, 2012-11-04]
Většina matfyzáků se dříve či později setká s úkolem napsat krátký odborný text – třeba zápočtovou práci nebo příspěvek na konferenci. Tento stručný spisek se pokouší začínajícího badatele bezpečně provést hlavními úskalími odborného psaní.
Tři věty o prvočíslech [Czech, PDF, 2012-08-21]
Elegantní kombinatorické důkazy třech klasických vět o prvočíslech, které se často používají v informatice: Bertrandova postulátu, věty o hustotě prvočísel a věty o součtu prvočíselné harmonické řady. Pocta Paulovi Erdősovi.
Algoritmy okolo teorie čísel [Czech, PDF, 2013-06-10]
Úvod do algoritmů spojených s teorií čísel: Euklidův algoritmus, konstruktivní verze Čínské věty o zbytcích, RSA, pravděpodobnostní testy prvočíselnosti.
Medvědův průvodce po Céčku [Czech, PDF, 2014-02-27]
Průběžně se vyvíjející slajdy k různým mým přednáškám o Céčku.
Programování s ohledem na hardware [Czech, PDF, 2014-03-14]
Úvod do architektury dnešních PC z pohledu programátora. Doprovodný text k přednášce na FP TUL v Liberci.
Kouzelnické karty [Czech, PDF, 2011-12-02]
Hříčka s Hammingovými kódy ze Dne otevřených dveří 2011: Myslete si číslo, ukažte mi, na kterých kartičkách je, a já vám povím, které to bylo. Pokud vám to přijde snadné, pak dodám, že můžete jednou lhát, a přesto číslo poznám.
Letáčky na Den otevřených dveří [Czech, 2010-12-02]
Čtyři ukázky toho, čím se zabývají diskrétní matematikové, aneb malá návnada ke studiu na naší katedře přichystaná pro fakultní Den otevřených dveří. Založeno na starších textech Jirky Fialy.
Kombinatorické drobnosti [Czech, PDF, 2014-04-04]
Pár kombinatorických drobností, které zazněly na mých přednáškách z Kombinatoriky a grafů I a nesnadno se hledají v české literatuře. Obsahuje důkaz Hallovy a Birkhoffovy věty, rozbor Edmondsova-Karpova algoritmu na maximální tok a malou ochutnávku nekonečné kombinatoriky.
Lineární rekurence [Czech, PDF, 2010-03-31, updated 2013-06-10]
Věta o řešení lineárních rekurencí a její tři důkazy (pomocí vytvořujících funkcí, přes vektorové prostory a diagonalizací matice). Též algoritmy na výpočet n-tého členu rekurence.
Transcendence čísla e [Czech, PDF, 2009-08-04]
Důkaz transcendence Eulerova čísla vedený poměrně elementárními prostředky.
Hales-Jewettova věta [Czech, PDF, 2008-02-17]
Můj pokus o převyprávění důkazu Hales-Jewettovy věty o barvení hyperkrychlí.
Tři otázky k výuce programování [Czech, HTML, 2007-03-08]
Krátké zamyšlení nad tím, v jakém jazyce by se mělo učit programování a proč by to nemělo být C#.

Computers and Networking

Slidy k přednášce o LibUCW [Czech, PDF, 2013-06-10]
Stručné představení knihovny LibUCW, které jsem přednesl na 42. konferenci EurOpen v Třešti.
Malý tahák ke Gitu [Czech, PDF, 2013-07-19]
A short cheat sheet for Git users.
META HTTP-Equiv Considered Harmful [Czech, HTML, 2006-11-18]
A brief article about disadvantages of using META HTTP-Equiv tags to describe document charset.
BIRD Tutorial [Czech, 2001-02-19]
My talk about the BIRD Internet Routing Daemon held at SLT'2001 in Selský Dvůr.
Tutorial on Shared Libraries [Czech, HTML, 2000-07-07]
A short tutorial on creating and using shared libraries in Linux. For (much) more background, I recommend the paper How to Write Shared Libraries by Ulrich Drepper.
psref [English, 1998-09-21]
Poor man's PostScript command reference

Other stuff

The list of E-Codes of food additives [English, ASCII/PostScript, 2001-08-05]
A list of food aditives compiled from various sources. Also available as a pocket reference booklet in PostScript (print it on a two-sided A4, fold three times, cut and bind and you have a fancy booklet).
Česká přísloví přeložená do vědecké češtiny [Czech, Plain text, 1997-07-14]
Czech proverbs translated to modern scientific terminology (a compilation from various sources plus some additions by me).

Obsolete stuff

Wonderful World of Linux 2.5 [English, Compressed text, 2002-11-10]
Notes for my talk on news in Linux kernel 2.5.x held at SLT'2002 in Seč
IP Networking in Linux 2.2 [Czech, HTML, 1999-09-22]
A sequel to the previous paper describing Linux IP stack evolution in detail. It's been presented as a lecture at CZLUG conference in Prudká and also at the Linux Seminar.
Networking in Linux 2.1 [Czech, HTML, 1999-09-11]
An article on new networking features in Linux 2.1, originally published in Linuxove Noviny, an aperiodical magazine issued by Czech Linux Users Group. Also presented at the Linux Seminar at our faculty.
Bus Architecture for Linux [English, Compressed text, 1999-07-05]
A brief summary of my thoughts on how to handle buses and devices in Linux kernel. Now obsoleted by the new driver model in 2.6.x kernels.
Linux Kernel Inside [Czech, 1998-10-29]
Detailed abstract of my driver writing lecture at SLT'98 in Jevíčko
Archiv státnicové konference [Czech, Compressed text, 2001]
Otázky a odpovědi stran ožehavých témat matfyzáckých státnic z informatiky ve formě archivu mailing-listu, který jsme na Atreyovi na toto téma léta páně 2001 provozovali.
This page is maintained by Martin Mareš