Το πρόβλημα είναι το εξής: Δίνεται ένας πίνακας δύο διαστάσεων που περιέχει ακέραιους αριθμούς. Κάποιες από τις γραμμές του πίνακα μπορεί να έχουν διαγραφεί. Π.χ. στο παρακάτω παράδειγμα η δεύτερη γραμμή έχει διαγραφεί.
1 2 4 8 3
2 2 6 2 1
2 3 4 9 0
…
Το ζητούμενο είναι να βρεθούν μη διαγραμμένες γραμμές του πίνακα που περιέχουν συγκεκριμένους αριθμούς κάτω από συγκεκριμένες συνθήκες. Π.χ. “να βρεθεί μια μη διαγραμμένη γραμμή που να περιέχει το 2 στην τρίτη στήλη“. Επίσης ζητούμενο είναι να υλοποιηθούν διαδικασίες εισαγωγής εγγραφών στον πίνακα και διαγραφής από αυτόν. Στόχος της διπλωματικής είναι να συγκρίνει δύο μεθόδους για να γίνουν αυτά. Η πρώτη μέθοδος είναι απλή. Θεωρεί ότι ο πίνακας είναι αποθηκευμένος ως array δύο διαστάσεων (π.χ. στη C). Για να βρεθεί μια γραμμή που έχει το 2 στην τρίτη στήλη απλά ψάχνουμε μια μια τις γραμμές ξεκινώντας από την πρώτη και ελέγχουμε αν η εκάστοτε γραμμή έχει διαγραφεί, και αν όχι, αν έχει τον ζητούμενο αριθμό στην τρίτη στήλη της. Η δεύτερη μέθοδος βασίζεται στην αποθήκευση του πίνακα ως ένα σύνολο από tries. To trie είναι ένα είδος δενδρικής δομής που διευκολύνει την γρήγορη αναζήτηση.
Απαιτούμενες γνώσεις: Προγραμματισμός (π.χ. C ή Java), Αλγόριθμοι και Δομές Δεδομένων.
Επιβλέπων Καθηγητής: Κώστας Στεργίου