Απαρίθμηση και κατασκευή συνόλων δυαδικών λέξεων

Abstract

H διπλωματική αυτή ασχολείται με την απαρίθμηση και κατασκευή συνόλων δυαδικών λέξεων με ορισμένους περιορισμούς ή ιδιότητες. Στο πρώτο κεφάλαιο δίδονται βασικές έννοιες, οι οποίες χρησιμοποιούνται στα υπόλοιπα κεφάλαια. Στο δεύτερο κεφάλαιο μελετάται η απαρίθμηση συνόλων δυαδικών λέξεων με ορισμένους περιορισμούς, με τη μέθοδο των γεννητριών συναρτήσεων αλλά και με συνδυαστικές απεικο-νίσεις. Πιο συγκεκριμένα, γίνεται μελέτη για λέξεις Fibonacci, λέξεις χωρίς zig-zag, λέξεις Dyck και γενικά για λέξεις που αποφεύγουν συγκεκριμένα πρότυπα. Στο τρίτο κεφάλαιο παρουσιάζεται η κατασκευή συνόλων δυαδικών λέξεων με ορισμέ¬νους περιορισμούς, για λέξεις Fibonacci, λέξεις χωρίς zig-zag και λέξεις Dyck και δίνονται επαναληπτικοί και αναδρομικοί αλγόριθμοι επαναληπτικής κατασκευής, ranking-unranking και κατασκευής σε κώδικα Gray για κάθε ένα από τα παραπάνω σύνολα. Τέλος, τη μεταπτυχιακή αυτή διατριβή συμπληρώνει λογισμικό, το οποίο υλοποιεί τους αλγόριθμους που προκύπτουν στο τρίτο κεφάλαιο.