Mulligan, Evin (2022) Entropy Compression. Bachelor's Thesis, Mathematics.
|
Text
bMATH_2022_MulliganE.pdf Download (381kB) | Preview |
|
![[img]](https://fse.studenttheses.ub.rug.nl/style/images/fileicons/text.png) |
Text
Toestemming.pdf Restricted to Registered users only Download (123kB) |
Abstract
Entropy Compression is a technique to show that a random process or algorithm terminates in finite time. It can be used to prove the existence of certain objects, such as graphs, samples, strings etc. and to find them using a randomised algorithm. By defining an algorithm that losslessly compresses some random inputs into a string which records the history of the steps taken by ur algorithm we can guarantee termination if the bits of entropy read from our random inputs increases faster than the bits of information stored in our record. In this paper we examine the strategy behind entropy compression, discuss the mathematical background and give some examples of it's use.
| Item Type: | Thesis (Bachelor's Thesis) |
|---|---|
| Supervisor name: | Muller, T. and Trapman, J.P. |
| Degree programme: | Mathematics |
| Thesis type: | Bachelor's Thesis |
| Language: | English |
| Date Deposited: | 19 Jul 2022 07:00 |
| Last Modified: | 19 Jul 2022 07:00 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/27962 |
Actions (login required)
 |
View Item |