Triesscheijn, R.A. and Renardel de Lavalette, G.R. and Meijster, A. (2012) Opwaarts gesloten deelverzamelingen in partieel geordende verzamelingen. Bachelor's Thesis, Computing Science.
|
Text
Final.pdf - Published Version Download (1MB) | Preview |
|
![[img]](https://fse.studenttheses.ub.rug.nl/style/images/fileicons/text.png) |
Text
AkkordRenardel.pdf - Other Restricted to Registered users only Download (30kB) |
Abstract
Het bepalen van het aantal opwaarts gesloten deelverzamelingen in een partieel geordende verzameling levert een uniek kengetal op dat gebruikt kan worden om verzamelingen te vergelijken. Dit kengetal is als het ware een vingerafdruk van de verzameling. Tot nu toe is er, zover mij bekend, nog geen slim algoritme om het aantal opwaarts gesloten deelverzamelingen te bepalen. Daarom moest dit kengetal bepaald worden door met brute kracht alle mogelijke deelverzamelingen te controleren op opwaarts geslotenheid. Dit leidt zelfs voor triviale verzamelingen al snel tot problemen aangezien de complexiteit van dit proces altijd O(2^n) bedraagt. Als het aantal opwaarts gesloten deelverzamelingen met de hand uitgerekend wordt kan eventuele symmetrie uitgebuit worden maar bij grotere verzamelingen, of als er geen symmetrie is, blijft dit een tijdrovend en foutgevoelig proces. In deze scriptie presenteer ik een computer algoritme dat exact en, in de meeste gevallen, sneller het aantal opwaarts gesloten deelverzamelingen kan bepalen.
| Item Type: | Thesis (Bachelor's Thesis) |
|---|---|
| Degree programme: | Computing Science |
| Thesis type: | Bachelor's Thesis |
| Language: | Dutch |
| Date Deposited: | 15 Feb 2018 07:48 |
| Last Modified: | 15 Feb 2018 07:48 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/10255 |
Actions (login required)
 |
View Item |