Mijn favoriete algoritmen. Praatjes voor algemeen publiek (en studenten). Een "blog" in de vorm van een lijstje voordrachten.

Bavarian Beer Party - de Bruijn rijtjes - Convex hull - Dijkstra - DNA Computers - FRACTRAN - Grafen en Genen - Interval graphs - Knuth, Morris, Pratt - River Crossing - Tetris - Waar is hier de Uitgang? -

Bavarian Beer Party

Pre-Class «Computer Science: Working Smarter!» ⇒info (voorheen Lapp-top)

Cursus dynamisch programmeren, aan de hand van twee problemen gemotiveerd vanuit de Computational Molecular Biology: RNA folding en string alignment.

The professors of the Bayerische Mathematiker Verein have their annual party in the local Biergarten. They are sitting at a round table each with his own pint of beer. As a ceremony each professor raises his pint and toasts one of the other guests in such a way that no arms cross.
We know that the professors like to toast with someone that is drinking the same brand of beer, and we like to maximize the number of pairs of professors toasting with the same brand , again without crossing arms. Write an algorithm to do this, keeping in mind that every professor should take part in the toasting.

ref. The Bavarian Beer Party, in China. (Oorspronkelijk 2006 Benelux Algorithm Programming Contest)

wiki. RNA Folding, Alignment. Dyamic programming

de Bruijn rijtjes

«How to apply de Bruijn graphs to genome assembly» ⇒pdf

Naar aanleiding van het artikel en het recente overlijden van N.G. de Bruijn (9 July 1918 — 17 February 2012).
lezing Challenges in Computer Science, Leiden, 10 April 2012.

ref. P.Compeau, P.Pevzner & G.Tesler: How to apply de Bruijn graphs to genome assembly. Nature Biotechnology 29 (nov. 2011) 879—911. doi:10.1038/nbt.2023

wiki. de Bruijn

Convex hull

«Inpakken!» ⇒info

Voorlichtingspraatje

Hoe kunnen we efficient de "omtrek" van een wolk punten bepalen? Geïllustreerd met een oude programmeeropgave. Twee klassieke methodes zijn Jarvis' March en Graham's Scan. We kijken naar de aanpak en vergelijken ook hun complexiteit.

wiki. Convex hull algoritms

Dijkstra: kortste paden

«Evelien en Serge door Nederland» ⇒pdf

Ouderdag april 2016; Leidsche Flesch Lunsch Lezing 16 april 2010. Naar aanleiding van de monopoly-wedstrijd.

For many years, and in wide circles, The Shortest Path has been the main pillar for my name and fame, and then it is a strange thought that it was designed without pencil and paper, while I had a cup of coffee with my wife on a sunny cafe terrace in Amsterdam, only designed for a demo.... "From my Life" [EWD1166]

Over het beroemde algoritme; maar ook over the cruelty of really teaching computer science [EWD1036].

ref. E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik 1959, Volume 1, Issue 1, pp 269—271. doi:10.1007/BF01386390

wiki. Dijkstra, his algorithm, Hamiltonian path, Monopoly.

DNA Computers

«Computer in a testtube: DNA Computing» ⇒info

Turing's Legacy, The modern day application of his ideas, SNiC Symposium (7 maart 2012, Jaarbeurs Utrecht) & Honours Class Foundations of Informatics: Algorithmic Adventures (Eindhoven, 13 december 2010)

Over de visie van Adleman om met de bouwstenen van DNA ie kunnen programmeren: het Hamiltonian Path Problem geimplementeerd met enzymen. Toegift: knutselen met DNA, self-assembly, hoe je met DNA structuren kunt opbouwen.

ref. Molecular Computation of Solutions to Combinatorial Problem, Science, 266: 1021-1024, (Nov. 11) 1994. doi: 10.1126/science.7973651
Leonard M. Adleman - Computing with DNA Scientific American August 1998

wiki. Adleman

FRACTRAN

«Fractran ... een tamelijk nutteloze programmeertaal» ⇒pdf

Leidsche Flesch Lunsch Lezing 23 november 2016.

"And I thought Brainf*ck was weird" — R.H.

FRACTRAN is een vreemde en onhandige programmeertaal. De reeks breuken 17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1 is een programma om de priemgetallen te berekenen. In deze lezing verklaar ik hoe dit programma werkt. Maar ik wil ook even stilstaan hoe FRACTRAN past in de zoektocht naar simpele en krachtige rekenmodellen, waarvan de Turing Machine de bekendste is.

wiki. Conway, FRACTRAN

ref. • OEIS A007542
• J. H. Conway. FRACTRAN: A Simple Universal Programming Language for Arithmetic, Open Problems in Communication and Computation, pp 4-26, 1987. doi: 10.1007/978-1-4612-4808-8_2

youtube. Marvin Minsky op WebOfStories over Solving Post's unsolvable problem [of "Tag"] leads to the 'Minsky Machines'

Grafen en Genen

«Gene Rearrangements in Ciliates» ⇒pdftechnische info

Leidsche Flesch Lunsch Lezing 1 oktober 2014.

Een wat al te gehaast overzicht over hoe grafen gebruikt worden om DNA eigenschappen te modelleren in verschillende takken van "computational biology" en "bio-inspired computing".

ref. • Prescott: Genome gymnastics. doi: 10.1038/35042057 [Gene Rearrangement binnen gen]
• Hannenhalli & Pevzner: Transforming Cabbage into Turnip. J.ACM 1999. [Gene Rearrangement op chromosoom nivo]
• How to apply de Bruijn graphs to genome assembly, zie praatje hierboven. [reconstructie DNA]
• Brijder & Hoogeboom. The Algebra of Gene Assembly in Ciliates. "Eigen werk" Overzicht. Pdf op aanvraag.
en natuurlijk: • Gates & Papadimitriou (1979). "Bounds for Sorting by Prefix Reversal". doi: 10.1016/0012-365X(79)90068-2 [als Open Archive]

wiki. Pevzner, Ciliate

Interval graphs: unique probe mapping

«Computational Molecular Biology: Unique probe mapping met behulp van PQ-trees» ⇒pdf · ⇒info

Voorbeeldcollege MCB 6 april 2006.

Hoe we uit een verzameling snippers een tekst kunnen reconstrueren, toegepast op letters van DNA. Mooie illustratie van hoe een datastructuur gebruikt kan worden om nog mogelijke permutaties bij te houden. De uitsmijter: het algoritme is uit 1977 (toen DNA nog niet gelezen kon worden).

ref. Kellogg S. Booth, George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, Volume 13, Issue 3, December 1976, Pages 335—379. doi:10.1016/S0022-0000(76)80045-1

Knuth, Morris, Pratt

«KMP patroonherkenning» ⇒pdf

Leidsche Flesch Lunsch Lezing 26 september 2012.

Over het beroemde algoritme; en de cheques van Knuth.

In de woorden van de auteurs: Over Morris die text editor schreef die "was too complicated for other implementors of the system to understand". Over Knuth "the first time in Knuth's experience that automata theory had taught him how to solve a real programming problem better than he could solve it before". En ook "Knuth was chagrined to learn that Morris had already discovered the algorithm, without knowing Cook's theorem"

ref. Donald Knuth, James H. Morris, Jr & Vaughan Pratt. Fast pattern matching in strings. SIAM Journal on Computing 6 (1977) 323—350. doi:10.1137/0206024

filmpje.Knuth zelf, bij WebOfStories

wiki. Knuth, Morris, Pratt, en hun Algoritme

River Crossing

«Kool, Geit en Wolf» ⇒pdf

Leidsche Flesch Lunsch Lezing 7 oktober 2015 (met broodjes en krentenbollen)

Over het beroemde probleem: hoe krijgen we de drie voorwerpen heelhuids over de rivier. We zoeken eerst naar een algoritmische aanpak, en laten dan zien dat in het algemeen dit probleem NP-compleet is, een begrip dat we danken aan Levin en Cook (en een beetje aan Turing). Tenslotte beken ik dat ik ooit een Latijnse voetnoot in een wetenschappelijk artikel gesmokkeld heb.

«Cabbage, Goat, and Wolf» or Computational Complexity of River Crossing Puzzles ⇒pdf

Math Club USF Tampa & Math Club UNF Jacksonville Jan/Feb 2016 (with free pizza)

The Cabbage, Goat, and Wolf puzzle is already known from a medieval manuscript that was written "to sharpen the young". We still use puzzles like these in our lectures to teach modeling, problem solving, or programming. I will explain basic Computational Complexity and show in what sense River Crossing Puzzles are complex. Also River Crossing has similarities to Membrane Systems, a formal model from Natural Computing.

ref. Hiro Ito, Stefan Langerman, Yuichi Yoshida. Generalized River Crossing Problems, Th. Comp. Sys. 56 (2015) 418—435 doi: 10.1007/s00224-014-9562-8
H.J. Hoogeboom. Carriers and Counters: P Systems with Carriers vs. (Blind) Counter Automata, LNCS 2450 (2003) pp. 140—151 doi: 10.1007/3-540-45005-X_12

wiki. Propositiones ···, River Crossing Puzzle, NP Complete Problems, Cook-Levin theorem, en Membrane computing

youtube. A more politically correct version of the missonaries and cannibals problem, with wildebeast and lion, on TED-Ed Can you solve the river crossing riddle?
Edsger Dijkstra explains the problem, utilizing the symmetry between wolf and cabbage.

Tetris

«Tetris is NP-Volledig» ⇒info

De Wetenschap van Tetris, Leidsche Flesch lunch lezing, Juni 2006.

In 2002 hebben Amerikaanse computerwetenschappers de moeilijkheidsgraad van Tetris vastgesteld en aangetoond dat het overeenkomsten heeft met de moeilijkste wiskundeproblemen: een optimale oplossing vergt een uitputtende analyse.

Het oorspronkelijke bewijs van Demaine, Hohenberger and Liben-Nowell, kon op basis van een idee van Ron Breukelaar een stuk getroomlijnd worden. De NP-volledigheid van Tetris is één van de mijlpalen uit Het WiskundeBoek van Clifford A. Pickover, waaruit het bovenstaande citaat komt.

wiki. Tetris,
ref.Erik Demaine
• Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, David Liben-Nowell: Tetris is hard, even to approximate. Int. J. Comput. Geometry Appl. 14 (2004) 41—68. doi: 10.1142/S0218195904001354
youtube. Fun with Hardness Proofs, Tetris door Erik Demaine.

Waar is hier de Uitgang?

«Algoritmen in het Doolhof» ⇒info

Ouderdag april 2015;

We laten een aantal technieken zien om uit het doolhof te komen. Dat is ook nuttig als we ons niet in een doolhof begeven, omdat achter veel problemen een doolhof verborgen blijkt te zijn.

ref. logicmazes.com
wiki. Maze generation algorithm, Theseus, .