Πρότυπα σε μονοπάτια Dyck και διατεταγμένα δένδρα

Abstract

Η διατριβή αυτή ασχολείται με τη μελέτη ορισμένων προβλημάτων στο σύνολο των μονοπατιών Dyck. Στο πρώτο κεφάλαιο δίδονται βασικές έννοιες και προκαταρκτικά αποτελέσματα που χρησιμο¬ποιούνται στα υπόλοιπα κεφάλαια. Στο δεύτερο κεφάλαιο μελετάται το σύνολο των μονοπατιών Dyck εφοδιασμένο με τη (μερική) διάταξη κυριαρχίας. Στο τρίτο κεφάλαιο, που αποτελεί και το κεντρικό θέμα της διατριβής, μελετάται το πρόβλημα της απαρίθμησης συγκεκριμένων προτύπων που εμφανίζονται μέσα σε μονοπάτια Dyck. Στο τέταρτο κεφάλαιο χρησιμοποιούνται τα μονοπάτια Dyck για τη μελέτη προβλημάτων του συνόλου των διατεταγμένων δένδρων. Τέλος, τη διατριβή αυτή συμπληρώνει λογισμικό που υλοποιεί τους αλγόριθμους που προκύπτουν σε κάθε κεφάλαιο.