May 2019
This note gives a list of theoretical problems that are important to computer science. It is meant to be regularly updated with the various finds dug out from some bibliographical excavations.
| Knight's tour | Instance of the Hamiltonian cycle finding problem with a simple heuristic (Warnsdorff's rule) |
| N-Queens | Simple example to illustrate backtracking |
| Stable marriages | Reference problem when considering offer/demand systems |
| Post's correspondance problem | Often used to prove the undecidabilty of some decision problem |
| Wang tiles | Useful for procedural generation: with as few as 11 basic tile patterns, a plane can be tiled aperiodically |
| Rule 110 | Similar to Wang tiles, to the difference that it displays a high amount of near similar patterns |
| Equational logic | Convenient for a logical (or computational) introduction to abstract algebras |
| Unbounded nondeterminism | Well-known problem when considering concurrent systems |