ΣΔΟΕ για την πάταξη της φοροδιαφυγής

Στη μεγάλη προσπάθεια που καταβάλλει το ΣΔΟΕ για την πάταξη της φοροδιαφυγής,  της παραοικονομίας και της διακίνησης «μαύρου» χρήματος, έχει εντοπίσει ένα σύνολο n ύποπτων συναλλαγών οι οποίες σε ένα διάστημα λίγων ημερών εμφανίζονται να τροφοδοτούν έναν κοινό λογαριασμό (εκτός χώρας). Τα τεχνολογικά μέσα που διαθέτει το ΣΔΟΕ καθώς και οι προσεκτικές κινήσεις των εμπλεκομένων δεν επιτρέπουν την διακρίβωση της ταυτότητας του τροφοδότη λογαριασμού, και δεν προσφέρουν ακριβή στοιχεία των συναλλαγών (ποσό, χρόνος πραγματοποίησης συναλλαγής).   Η μόνη πληροφορία που μπόρεσε να συλλέξει το ΣΔΟΕ είναι ένας κατά προσέγγιση χρόνος εκτέλεσης μιας συναλλαγής j, δηλ. ότι η j-οστή συναλλαγή  πραγματοποιήθηκε εντός του χρονικού διαστήματος [τ_j – ε_j, τ_j + ε_j], όπου ε_j είναι το σφάλμα χρονικής προσέγγισης. Διαφορετικές συναλλαγές έχουν διαφορετικά σφάλματα χρονικής προσέγγισης και μπορεί να υπάρχει χρονική επικάλυψη μεταξύ διαφορετικών χρονικών διαστημάτων.

Το ΣΔΟΕ διαθέτει επίσης μια λίστα ύποπτων λογαριασμών προς έλεγχο, που ανήκουν στο ευρύτερο περιβάλλον των οικογενειών Μάκη Πούλα και Αχιλλέα Μπέη, και αναζητά τρόπους προκειμένου να διαπιστώσει αν κάποιος από τους ύποπτους αυτούς λογαριασμούς συνδέεται με τις ύποπτες συναλλαγές. Για κάθε λογαριασμό, το ΣΔΟΕ έχει εντοπίσει n κινήσεις, οι οποίες πραγματοποιήθηκαν τις χρονικές στιγμές t₁, t₂, ..., t_n (που έλαβαν χώρα στο ίδιο χρονικό διάστημα με τις n ύποπτες συναλλαγές). Ένας τρόπος προσδιορισμού συσχέτισης ενός λογαριασμού με τις ύποπτες συναλλαγές είναι η χρονική συσχέτιση των n κινήσεων του λογαριασμού με τις nύποπτες συναλλαγές.  Αν η i-οστή κίνηση του λογαριασμού που πραγματοποιήθηκε τη χρονική στιγμή t_i απέχει χρονικά το πολύ ε_j από την χρονική στιγμή τέλεσης τ_j μιας ύποπτης συναλλαγής j, δηλ. αν |τ_j – t_i| £ ε_j, τότε θεωρούν ότι η i-οστή κίνηση συσχετίζεταιμε την j-οστή ύποπτη συναλλαγή. Aν κάθε μία κίνηση μπορεί να συσχετιστεί με μια διαφορετική συναλλαγή, το ΣΔΟΕ θεωρεί ότι έχει σοβαρές ενδείξεις ότι ο ύποπτος λογαριασμός συνδέεταιμε τις ύποπτες συναλλαγές. Η δυσκολία επίλυσης του προβλήματος σύνδεσης ενός λογαριασμού με ένα σύνολο nύποπτων συναλλαγών έγκειται στο ότι το ΣΔΟΕ δεν γνωρίζει ποιά κίνηση λογαριασμού πρέπει να συσχετίσει με ποια ύποπτη συναλλαγή.

(Α) Δώστε έναν αποδοτικό άπληστο αλγόριθμο που θα δέχεται ως είσοδο τις χρονικές στιγμές t₁, t₂, ..., t_n πραγματοποίησης των n κινήσεων ενός λογαριασμού, τους κατά προσέγγιση χρόνους εκτέλεσης τ₁, τ₂, ..., τ_nτων nύποπτων συναλλαγών και τα σφάλματα προσέγγισής τους ε₁, ε₂, ..., ε_n και θα αποφασίζει αν ο λογαριασμός συνδέεται με τις ύποπτες συναλλαγές, δηλ. αν υπάρχει 1 προς 1 συσχέτιση μεταξύ των t₁, t₂, ..., t_n και των χρονικών διαστημάτων τέλεσης των ύποπτων συναλλαγών.

(Β) Αποδείξτε την ορθότητα του αλγορίθμου σας και την χρονική του πολυπλοκότητα, η οποία πρέπει να είναι O(n²).