Υπάρχουν θέματα για πτυχιακές κυρίως μαθηματικού/θεωρητικού χαρακτήρα στην ευρύτερη περιοχή των αλγορίθμων. Οι βασικοί στόχοι των πτυχιακών αυτών είναι (1) η απόκτηση καινούργιας γνώσης σε κάποια περιοχή των Θεμελιώσεων της Επιστήμης Υπολογιστών (2) η εμβάθυνση και ο συσχετισμός ήδη αποκτημένων γνώσεων από τα προηγούμενα έτη και (3) η απόκτηση εμπειρίας στην αναζήτηση και σύνθεση βιβλιογραφίας. Προαπαιτούμενο είναι καλή γνώση αλγορίθμων, και μια κάποια έφεση στο μαθηματικό τρόπο σκέψης. Καλές γνώσεις πιθανοτήτων και διακριτών μαθηματικών (στο επίπεδο των αντίστοιχων προπτυχιακών μαθημάτων) θα είναι επίσης χρήσιμες.
Τα σχετικά θέματα εμπίπτουν σε (1) αλγορίθμους σε Συνδυαστική Βελτιστοποίηση (π.χ. ροές σε δίκτυα, χρονοδρομόλογηση, σχεδιασμός δικτύων) και (2) σε αλγοριθμικές όψεις της Θεωρίας Παιγνίων και των Οικονομικών (π.χ. ιδιοτελής δρομολόγηση, συνδυαστικές δημοπρασίες). Η συγκεκριμενοποίηση του θέματος γίνεται ύστερα από συζήτηση με τον/την ενδιαφερόμενο/νη. Ο στόχος είναι να συγκεράσουμε τις προσωπικές κλίσεις και προτιμήσεις με τις τρέχουσες εξελίξεις της διεθνούς βιβλιογραφίας.
Και στις δύο κατηγορίες θεμάτων στην οπτική μας υπεισέρχεται με διάφορους τρόπους η έννοια του προσεγγιστικού αλγορίθμου (approximation algorithm). Οι προσεγγιστικοί αλγόριθμοι είναι ένα από τα σπουδαιότερα εργαλεία που διαθέτουμε για να αντιμετωπίζουμε υπολογιστικά δύσκολα πρόβληματα. Ακολουθεί μια σύντομη συζήτηση της έννοιας του προσεγγιστικού αλγόριθμου.
Τα περισσότερα πρακτικά προβλήματα είναι προβλήματα βελτιστοποίησης: μας ενδιαφέρει να βρούμε μια λύση με το ελάχιστο κόστος (ή αντίστοιχα το μέγιστο κέρδος). Π.χ. το πρόβλημα των shortest paths. 'Ομως τα περισσότερα από τα ενδιαφέροντα προβλήματα βελτιστοποίησης, σε αντίθεση με τα shortest paths, είναι υπολογιστικά δύσκολα, συνήθως NP-hard. Π.χ. το πρόβλημα εύρεσης του μεγαλύτερου μονοπατιού (longest path) σε ένα γράφημα. Οι καλύτεροι αλγόριθμοι βελτιστοποίησης για τέτοιου είδους προβλήματα έχουν εκθετική πολυπλοκότητα. Δεν μπορούμε να ελπίζουμε πως η τεχνολογία θα τους καταστήσει αποδοτικούς όσο γρήγορα και να γίνουν τα υπολογιστικά συστήματα του μέλλοντος. Τί μπορούμε λοιπόν να κάνουμε;
Ο ρ-προσεγγιστικός αλγόριθμος είναι ένας αποδοτικός αλγόριθμος που βρίσκει για οποιαδήποτε είσοδο μία λύση με κόστος το πολύ ρ φορές το βέλτιστο, για κάποιο ρ > 1. Μέρος της ανάλυσης του αλγορίθμου είναι να αποδείξουμε αυτή την εγγύηση "ποιότητας" που εκφράζει το ρ. Σημειώστε πως εγγυώμαστε μαθηματικά προσέγγιση σε μία βέλτιστη τιμή την οποία δεν γνωρίζουμε πώς να υπολογίζουμε!