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? -
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
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
Voorlichtingspraatje (Proefstuderen)
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
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.
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
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.
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'
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]
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
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
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.
•
Can you solve the river crossing riddle?,
A more politically correct version of the missonaries and cannibals problem, with wildebeast and lion, on TED-Ed
•
Edsger Dijkstra explains the problem, utilizing the symmetry between wolf and cabbage.
•
Numberphile - River Crossings (and Alcuin Numbers)
"Alcuin of York, an Anglo-Saxon really smart dude", more items to take, and minimal boat size.
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.
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,
.