doc. RNDr. Tatiana Jajcayová, PhD.

Catalan Numbers appear in various contexts in Computer science. The nthCatalan number is given directly in terms of binomial coefficients, and the recursive definition given by a non-linear recurrence relation is also known.One of the mathematical objects to which the Catalan numbers are related areso called Hankel matrices, and those, in turn, are used with Hidden Markov models

The goal of the theses is to study this connection between the Catalan numbers and Hidden Markov models. Possible means to achieve this is to connect various different combinatorial problems in Informatics in which Catalan Numbers appear, employ some knowledge of statistics and probability, understandHidden Markov models and design good tests and algorithms. This requires to use “intelligent" approach to programming as the sequence of Catalan Numbers grows very fast.

- Introduction
- The origin of Catalan numbers
- Various encounters with Catalan numbers
- Hankel matrices (and Catalan numbers)
- Hidden Markov model
- Implementation
- What I found out
- Conclusion

** 31.10. 2019 ** : Web page

** 12.11. 2019 ** : Time schedule

** 26.11. 2019** : Resources and presentation

** 12.1. 2020 ** : Prototype

** 13.1.2020 - 9.4.2020 ** : Additional research and implementation

** 10.4. 2020 ** : Finishing research

** 10.5. 2020 ** : Writing chapters: Introduction, Conclusion

** 20.5. 2020 ** : Final touches

** 22.5. 2020 ** : Thesis done

** 22.5. 2020 ** : Application done

** 15.6. 2020 ** : Finishing presentation

**x.6. 2020 **Presenting

Type | Title | Author(s) |
---|---|---|

Bachelor Thesis | Bounded Locally Testable Matrices | Marian Opial |

Book | Fibonacci and catalan numbers : an introduction | Ralph P. Grimaldi |

Book | Discrete and combinatorial mathematics | Ralph P. Grimaldi |

Book | Introduction to Algorithms, Third Edition | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein |

Book | Applied Combinatorics | Alan Tucker |

Article | History of catalan numbers | Igor Pak |

Article | The catalan numbers | Tanja Stojadinovic |

Article | Catalan numbers | Tom Davis |

Article | Hankel transforms of linear combinations of catalan numbers | Michael Dougherty, Christopher French, Benjamin Saderholm, Wenyang Qian |

Article | Catalan numbers,the hankel transform and fibonacci numbers | Aleksandar Cvetkovic, Predrag Rajkovic, and Milos Ivkovic |

Article | Enumeration of certain young tableaux with bounded height | Desainte-Catherine M. and X. G. Viennot |

Article | A determinant property of catalan numbers | M. E. Mays and J. Wojciechowski |

Article | Some aspects of hankel matrices in coding theory and combinatorics | Ulrich Tamm |

Book | Markov Chains and Stochastic Stability | S. P. Meyn and R. L. Tweedie |

Book | An introduction to Markov Chains | Ander Stolver |

Book | Markov processes: Theory and examples | Jan Swart and Anita Winter |

Book | Speech and Language Processing | Daniel Jurafsky and James H. Martin |

Article | A Revealing Introduction to Hidden Markov Models | Mark Stamp |

Article | Learning Hidden Markov Models using Non-Negative Matrix Factorization | George Cybenko and Valentino Crespi |

Article | Synthesis of hidden Markov models and processes with finite-rank Hankel matrices | M. Vidyasagar |

Article | The Complete Realization Problem for Hidden Markov Models |
M. Vidyasagar |

Documentation | Rust documentation | https://doc.rust-lang.org/1.3.0/ [23.11.2019] |

Book | The Rust Programming Language | Steve Klabnik and Carol Nichols |

- Generating Catalan Numbers
- Forward Algorithm
- Backward Algorithm
- Forward-Backward Algorithm
- Viterbi Algorithm