Μελέτη του προβλήματος των κίβδηλων νομισμάτων

Abstract

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