Javascript must be enabled for the correct page display

Opwaarts gesloten deelverzamelingen in partieel geordende verzamelingen

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.

[img]
Preview
Text
Final.pdf - Published Version

Download (1MB) | Preview
[img] 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 View Item