Articles and other writings by Martin Mareš
Mathematics and Computer Science
- New detail insight into Halloysite structure [English, 2023-04-22]
- I co-authored a paper on structure of Halloysite nanotubes, my contribution was software for simulation of these structures written together with Kateřina Macková.
- Průvodce labyrintem algoritmů (2. vydání) [Czech, 2022-10-04]
- A textbook on algorithms and data structures. Goes from the very basics to advanced topics like algorithmic applications of the Fast Fourier Transform and persistent data structures. Published by CZ.NIC, z.s.p.o. in Prague. ISBN: 978-80-88168-63-8.
- 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, PDF, 2000-08-08, updated 2024-07-07]
- My diploma thesis on data structures for dynamic and semi-dynamic graph algorithms, especially connectivity, spanning trees and 2-edge-connectivity.
Programming Contests
- Security of Grading Systems [English, PDF, 2021-06-21]
- Programming contests often employ automatic grading of solutions.
Graders need to run potentially malicious code, which brings many
security issues. We discuss various attacks on grading system security
and suggest counter-measures.
In: Olympiads in Informatics, 2021, Vol. 15, 37-52 - 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).
- Kombinatorika do kapsy [Czech, PDF, 2022-10-18]
- Kapesní přehled základních kombinatorických vět tak, jak je vyprávím na přednáškách z Diskrétní matematiky.
- Ramseyovy věty [Czech, PDF, 2014-05-09, updated 2016-05-16]
- Stručný přehled tvrzení Ramseyovy teorie, které zazněly na mých přednáškách z Kombinatoriky a grafů I a nesnadno se hledají v české literatuře.
- 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, updated 2019-04-04]
- Elegantní kombinatorické důkazy tří 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, 2019-03-11]
- 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, 2017-01-12]
- 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, 2015-05-05]
- Stručné představení knihovny LibUCW, které jsem přednesl na 42. konferenci EurOpen v Třešti. Od té doby průběžně vylepšováno pro potřeby přednášky z AIM.
- Malý tahák ke Gitu [Czech, PDF, 2018-06-30]
- 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 SLT98 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.