View on GitHub

dituoi_alco

Αλγόριθμοι και πολυπλοκότητα

Αλγόριθμοι και πολυπλοκότητα

Ακαδημαϊκό έτος 2024-2025

Γκόγκος Χρήστος, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Άρτα, Πανεπιστήμιο Ιωαννίνων

Σελίδα ecourse του μαθήματος ecourse UoI.

Τελευταία ενημέρωση: 17/11/2024

Παρουσιάσεις από το βιβλίο “Αλγόριθμοι Σχεδίαση και Εφαρμογές” των M. Goodrich και R. Tamassia

Θέματα προετοιμασίας

1. Ανάλυση αλγορίθμων

5. Ουρές προτεραιότητας και σωροί

Ουρές προτεραιότητας στην Python

Ουρές προτεραιότητας στην C++

std::priority_queue

Παράδειγμα: priority_queue_example.cpp

Ουρές προτεραιότητας στην Java

PriorityQueue<E>

Παραδείγματα: Java PriorityQueue by Programiz

Ασκήσεις

  1. Έστω ένας μηχανισμός παραγωγής πραγματικών τιμών. Όταν παράγεται μια νέα τιμή να υπολογίζεται και να εμφανίζεται η διάμεσος από όλες τις τιμές που έχουν παραχθεί μέχρι εκείνη τη χρονική στιγμή. Γράψτε πρόγραμμα που να υλοποιεί τη λύση.
    • Σημείωση 1: η διάμεσος μιας λίστας παρατηρήσεων είναι η τιμή της μεσαίας παρατήρησης στη διατεταγμένη σε αύξουσα σειρά λίστας παρατηρήσεων όταν το πλήθος των παρατηρήσεων είναι περιττό, και το ημιάθροισμα των δύο μεσαίων παρατηρήσεων στη διατεταγμένη σε αύξουσα σειρά λίστας παρατηρήσεων όταν όταν το πλήθος των παρατηρήσεων είναι άρτιο.
    • Σημείωση 2: Προσομοιώστε την παραγωγή πραγματικών τιμών με μια λίστα τυχαίων πραγματικών τιμών. Θεωρείστε ότι στη χρονική στιγμή 0 παράγεται η τιμή που βρίσκεται στη θέση 0 της λίστας, στη χρονική στιγμή 1 παράγεται η τιμή που βρίσκεται στη θέση 1 της λίστας κ.ο.κ.
     Περιγραφή αλγοριθμικής προσέγγισης

 Δημιουργούνται δύο σωροί, ένας σωρός μεγίστων (ΜΑΧHEAP) και ένας σωρός ελαχίστων (MINHEAP). Η ρίζα του MAXHEAP θα πρέπει να είναι μικρότερη από τη ρίζα του MINHEAP. Αν αυτό δεν ισχύει θα πρέπει να μεταφέρεται η ρίζα του ενός από τους δύο σωρούς στον άλλο σωρό έτσι ώστε να επιβληθεί αυτή η συνθήκη. Οι εισαγωγές νέων τιμών θα γίνονται πάντα στον MAXHEAP. Οι δύο σωροί θα πρέπει να έχουν το ίδιο μέγεθος ή ο ένας να είναι κατά 1 μόνο στοιχείο μεγαλύτερος του άλλου και όταν αυτό παραβιάζεται θα μεταφέρεται η ρίζα του μεγαλύτερου σωρού στον μικρότερο σωρό. Η διάμεσος θα είναι είτε η ρίζα του μεγαλύτερου σωρού είτε το ημιάθροισμα των ριζών των δύο σωρών.

 # Ψευδοκώδικας 
 1. Λήψη νέου ακεραίου και προσθήκη στον MAXHEAP
 2. Αν η ρίζα του MAXHEAP είναι μεγαλύτερη από τη ρίζα του MINHEAP τότε αφαίρεσε τη ρίζα του MAXHEAP και πρόσθεσέ την στον MINHEAP
 3. Αν το μέγεθος των 2 σωρών διαφέρει κατά 2 αφαίρεσε τη ρίζα από το μεγαλύτερο σωρό και πρόσθεσε την στο μικρότερο σωρό.
 4. Η διάμεσος θα είναι o μέσος όρος των κορυφών των 2 σωρών, αν οι σωροί έχουν το ίδιο μέγεθος ή η ρίζα του μεγαλύτερου από τους 2 σωρούς.
 5. Επιστροφή στο βήμα 1 ή τερματισμός

6. Πίνακες αντιστοίχισης

Οι πίνακες αντιστοίχισης ή συσχετιστικοί πίνακες (associative arrays) ή συσχετιστικές μνήμες (associative memories), ή χάρτες (maps), ή χάρτες κατακερματισμού (hashmaps) ή λεξικά (dictionaries) είναι σύνολα ζευγών κλειδί/τιμή. Υποστηρίζουν τις λειτουργίες εντοπισμού (με δεδομένο το κλειδί), εισαγωγής του ζεύγους κλειδί/τιμή΄και διαγραφής (με δεδομένο το κλειδί) με υψηλή ταχύτητα, Ο(1) υπό προϋποθέσεις. Μπορούμε να θεωρούμε ότι οι πίνακες αντιστοίχισης αναφέρονται στον Αφηρημένο Τύπο Δεδομένων (ΑΤΔ), ενώ όταν υπάρχει στο όνομα η λέξη κατακερματισμός ότι μιλάμε για υλοποίηση του ΑΤΔ με κάποια υλοποίηση πίνακα κατακερματισμού.

Λεξικά στην Python

Πίνακες αντιστοίχισης στη C++

Πίνακες αντιστοίχισης στη Java

Συναρτήσεις κατακερματισμού

Μη κρυπτογραφικές συναρτήσεις κατακερματισμού (χρήση σε δομές δεδομένων)

Κρυπτογραφικές συναρτήσεις κατακερματισμού

Παραδείγματα με hash functions στην Python

Ελάχιστη τέλεια συνάρτηση κατακερματισμού (minimal perfect hash function)

Τέλεια συνάρτηση κατακερματισμού είναι μια συνάρτηση κατακερματισμού η οποία αντιστοιχίζει τα στοιχεία ενός συνόλου σε ένα σύνολο ακεραίων χωρίς συγκρούσεις. Ελάχιστη τέλεια συνάρτηση κατακερματισμού είναι μια τέλεια συνάρτηση κατακερματισμού που αντιστοιχίζει χωρίς συγκρούσεις n κλειδιά σε n διαδοχικούς ακεραίους από το 0 έως το n-1.

Δείτε και το http://cmph.sourceforge.net/concepts.html

Ανοικτή διευθυνσιοδότηση (open addressing ή closed hashing)

Η ανοικτή διευνσιοδότηση λαμβάνει το όνομά της από την ιδιότητα που έχει να επιτρέπει στα κλειδιά να μετακινηθούν και σε άλλες θέσεις, διαφορετικές από τη θέση στην οποία γίνονται αρχικά hash.

Η ανοικτή διευνσιοδότηση είναι γνωστή και ως κλειστός κατακερματισμός (closed hashing) καθώς τα κλειδία τοποθετούνται μόνο εντός του πίνακα κατακερματισμού και δεν χρησιμοποιείται κάποια άλλη βοηθητική δομή.

Παραλλαγές ανοικτής διευθυνσιοδότησης

Κλειστή διευθυνσιοδότηση (closed addressing ή open hashing ή separate chaining)

Η κλειστή διευθυνσιοδότηση λαμβάνει το όνομά της από την ιδιότητα που έχει να τοποθετεί τα κλειδιά στη θέση στην οποία γίνονται hash, χρησιμοποιώντας μια βοηθητική δομή (π.χ. συνδεδεμένη λίστα) για να αποθηκεύσει στην ίδια θέση πιθανώς περισσότερα από ένα στοιχεία τα οποία γίνονται hash στην ίδια θέση.

Η κλειστή διευθυνσιοδότηση είναι γνωστή και ως ανοικτός κατακερματισμός (open hashing) και ως ξεχωριστή αλυσίδωση (separate chaining). Το όνομα ανοικτός κατακερματισμός προκύπτει καθώς τα κλειδιά δεν είναι απαραίτητο να βρίσκονται εντός του ίδιου του πίνακα κατακερματισμού, αλλά μπορούν να βρίσκονται σε κάποια βοηθητική δομή.

Κατακερματισμός κούκου

Ο κατακερματισμός κούκου πετυχαίνει Ο(1) χρόνο χειρότερης περίπτωσης για αναζήτηση και διαγραφή και Ο(1) χρόνο μέσης περίπτωσγης για εισαγωγή.

Ασκήσεις

  1. Γράψτε ένα πρόγραμμα που να δέχεται έναν πίνακα ακεραίων και μια τιμή sum και να εμφανίζει όλα τα ζεύγη τιμών του πίνακα με άθροισμα ίσο με την τιμή sum.
  2. Γράψτε ένα πρόγραμμα που να εντοπίζει σε ένα λεξικό με μεγάλο πλήθος λέξεων όλες τις λέξεις για τις οποίες υπάρχουν τουλάχιστον άλλες 4 λέξεις που είναι αναγραμματισμοί της (π.χ. user -> [‘rues’, ‘ruse’, ‘suer’, ‘sure’, ‘user’]).
  3. Γράψτε ένα προγραμμα που να εντοπίζει το πλήθος των διακριτών ακεραίων σε μια μεγάλη λίστα ακεραίων.
  4. Γράψτε ένα πρόγραμμα που να δέχεται έναν πίνακα διακριτών ακεραίων τιμών και να εμφανίζει τον αριθμό κατάταξης κάθε τιμής του πίνακα (π.χ. για τον πίνακα [17, 13, 21, 19] να επιστρέφει [2, 1, 4, 3])
  5. Γράψτε ένα πρόγραμμα που να υπολογίζει το πλήθος εμφανίσεων των ελληνικών γραμμάτων (Α-Ω, χωρίς διάκριση σε κεφαλαία ή μικρά) σε ένα δεδομένο κείμενο.

7. Δομές Ένωσης-Εύρεσης (disjoint sets)

Ασκήσεις

  1. Δίνεται ένα σύνολο από σχέσεις φιλίας ανάμεσα σε άτομα (κάθε άτομο αναπαρίσταται από έναν αριθμό και η σχέση φιλίας με ένα ζεύγος αριθμών). Εντοπίστε τις ομάδες ατόμων που είναι συνδεδεμένες (π.χ. friends = [[ 1, 0 ], [ 2, 3 ], [ 1, 2 ], [ 4, 5 ]]).

8. Αλγόριθμοι Merge-Sort και Quick-Sort

Οπτικοποιήσεις Quick-Sort και άλλων αλγορίθμων ταξινόμησης

Κάτω όριο για ταξινόμηση βασισμένη σε συγκρίσεις στοιχείων

Lower bound: Ω(n log n)

10. Άπληστοι Αλγόριθμοι

Οι άπληστοι αλγόριθμοι εφαρμόζονται σε προβλήματα που έχουν:

Παραδείγματα προβλημάτων που λύνονται βέλτιστα με την άπληστη μέθοδο:

Κωδικοποίηση Huffmann

11. Διαίρει και βασίλευε

Διάφορα προβλήματα στα οποία εφαρμόζεται η τεχνική “διαίρει και βασίλευε”:

12. Δυναμικός προγραμματισμός

Υπολογισμός όλων των δυνατών υποακολουθιών συμβολοσειράς με Brute Force

Διάφορα προβλήματα στα οποία εφαρμόζεται η τεχνική του “δυναμικού προγραμματισμού”:

13. Γράφοι

Ακυκλικοί κατευθυνόμενοι γράφοι (DAGs = Directed Acyclic Graphs)

Λαβύρινθοι

14. Συντομότερα μονοπάτια

15. Ελάχιστα συνεκτικά δέντρα

16. Ροή δικτύου και αντιστοίχιση

17. NP-πληρότητα

18. Προσεγγιστικοί αλγόριθμοι

Aσκήσεις

  1. Δίνεται μια ακολουθία μεγάλου μεγέθους με τυχαίες ακέραιες τιμές. Ζητείται να βρεθούν οι 10 πλέον συχνές τιμές χρησιμοποιώντας μια ουρά προτεραιότητας. Αναζητήστε την αποδοτικότερη λύση. Γράψτε πρόγραμμα που να υλοποιεί τη λύση.

  2. Γράψτε πρόγραμμα που να δέχεται τον αριθμό μητρώου και το όνομα, για 10 φοιτητές. Στη συνέχεια να δέχεται επαναληπτικά αριθμούς μητρώου. Αν ο αριθμός μητρώου δεν υπάρχει στους 10 φοιτητές, το πρόγραμμα να τερματίζει, αλλιώς να εμφανίζει το μήνυμα “Γειά σου “ ακολουθούμενο από το όνομα του φοιτητή. Να χρησιμοποιηθεί λεξικό (πίνακας κατακερματισμού).

  3. Γράψτε πρόγραμμα που με είσοδο ένα μη ταξινομημένο πίνακα A χωρίς διπλότυπα και μια τιμή d, να εκτυπώνει όλα τα ζεύγη τιμών του Α με διαφορά τιμής d. Για παράδειγμα για Α=[1, 5, 6, 2, 7, 4] και d=3 να εκτυπώνει τα ζεύγη (1,4), (2,5), (4,7). Παρατηρείστε ότι τα ζεύγη εμφανίζονται με πρώτο το μικρότερο στοιχείο κάθε φορά.

Εκμάθηση Python

Εξάσκηση σε διάφορα αλγοριθμικά προβλήματα

Εργασίες παλαιότερων ετών