Αλγόριθμοι και δομές δεδομένων

• Δεδομένα


  Η αφαιρετική αναπαράσταση της πραγματικότητας και συνεπώς μία απλοποιημένη όψη της
• Πληροφορία


  Το αποτέλεσμα της συλλογής των ακατέργαστων δεδομένων και του συσχετισμού τους
• Η μέτρηση, η κωδικοποίηση και η μετάδοση της πληροφορίας αποτελεί αντικείμενο του κλάδου της Θεωρία Πληροφοριών (Information Theory), ένα ιδιαίτερο γνωστικό πεδίο της Πληροφορικής
• Οπτικές μελέτης δεδομένων στην πληροφορική


  • Υλικού
  • Γλωσσών προγραμματισμού
  • Δομές Δεδομένων
  • Ανάλυσης Δεδομένων
• Τύποι δεδομένων


  • Τύπος δεδομένων υλικού
  • Ιδεατοί (εικονικοί) τύποι δεδομένων
  • Αφηρημένοι τύποι δεδομένων
• Δομή δεδομένων


  Ένα σύνολο αποθηκευμένων δεδομένων που υφίσταται επεξεργασία από ένα σύνολο λειτουργιών, που καλούνται από το υπόλοιπο πρόγραμμα
• Στοιχεία δομής δεδομένων


  • Δομή αποθήκευσης
  • Σύνολο ορισμών συναρτήσεων
  • Σύνολο αλγορίθμων

  
• Βασικές λειτουργίες επί των δομών δεδομένων


  • Προσπέλαση
  • Εισαγωγή
  • Διαγραφή
  • Αναζήτηση
  • Ταξινόμηση
  • Αντιγραφή
  • Συγχώνευση
  • Διαχωρισμός
• Κόμβος


  Μία από τις βασικές δομικές μονάδες μίας δομής δεδομένων

  
• Πεδίο


  Μία υποδιαίρεση του κόμβου, που μπορεί να είναι δεδομένα, δείκτης ή δεσμός
• Αλγόριθμος


  Μία έννοια θεμελιώδης για την επιστήμη της πληροφορικής
• Κάποιοι αλγόριθμοι είναι χιλιάδες χρόνια παλιοί, όμως στα πλαίσια του μαθήματος θα επικεντρωθούμε σε αλγορίθμους των τελευταίων 3-4 δεκαετιών
• Αντιγραφή (copying)


  Όλοι οι κόμβοι ή μερικοί από τους κόμβους μίας δομής αντιγράφονται σε μία άλλη δομή
• Συγχώνευση (merging)


  Δύο ή περισσότερες δομές συνενώνονται σε μία ενιαία δομή
• Διαχωρισμός (separation)


  Το αντίστροφο της συγχώνευης
• Δεδομένα / Δομές δεδομένων

  Τα δεδομένα ενός κόμβου μπορεί να αντιστοιχούν σε μία ή περισσότερες μεταβλητές που αποθηκεύονται σε μία ή περισσότερες λέξεις (words), της κύριας μνήμης. Κάθε λέξη μπορεί να είναι από 8 ως 64 δυαδικά ψηφία. Μία υποδιαίρεση του κόμβου είναι το πεδίο (field). Τα πεδία μπορεί να είναι δεδομένα (data) ή δείκτες (pointer) ή δεσμοί (link). Ο δείκτης δείχνει την διεύθυνση κάποιου κόμβου, είτε σε απόλυτη μορφή (absolute address) είτε σχετική (relative address)
• Η έννοια του αλγορίθμου είναι θεμελιώδης για την επιστήμη της πληροφορικής και η λέξη προέρχεται από έναν Πέρση μαθηματικό που έζησε το 825 π.χ.

  
• Αλγόριθμος


  Ένα πεπερασμένο σύνολο εντολών αυστηρά καθορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο, οι οποίες αν ακολουθηθούν επιτυγχάνεται ένα επιθυμητό αποτέλεσμα
• Απαραίτητα χαρακτηριστικά ενός αλγορίθμου


  • Είσοδος (input)
  • Έξοδος (output)
  • Καθορισμός (definiteness)
  • Περατότητα (finiteness)
  • Αποτελεσματικότητα (effectiveness)
• Οπτικές μελέτης αλγορίθμων


  • Υλικού
  • Γλωσσών Προγραμματισμού
  • Θεωρητική
  • Αναλυτική
• Αναπαράσταση αλγορίθμων


  • Φυσική γλώσσα (natural language)
  • Διαγράμματα Ροής (flow chart)
  • Κωδικοποίηση (coding)
• Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα

  
• Εμπειρικός (empirical) ή εκ των υστέρων (posteriori) τρόπος μέτρησης απόδοσης αλγορίθμου


  Ο αλγόριθμος υλοποιείται και εφαρμόζεται σε ένα σύνολο δεδομένων και υπολογίζεται ο χρόνος επεξεργασίας (processing time) και η χωρητικότητα μνήμης (memory space)
• Μειονεκτήματα εμπειρικού τρόπου μέτρησης


  • Δεν μπορεί να προβλεφθεί η συμπεριφορά του αλγορίθμου για κάποιο άλλο σύνολο δεδομένων
  • Ο χρόνος επεξεργασίας εξαρτάται από το υλικό, τη γλώσσα προγραμματισμού και το μεταφραστή, και προπάντων από τη δεινότητα του προγραμματιστή
• Θεωρητικός (theoretical) ή αλλιώς εκ των προτέρων (a priori) τρόπος εκτίμησης απόδοσης αλγορίθμου


  Εισάγεται μία μεταβλητή n που εκφράζει το μέγεθος του προβλήματος, ώστε η μέτρηση της αποδοτικότητας του αλγορίθμου να ισχύει για οποιοδήποτε σύνολο δεδομένων και ανεξάρτητα από υποκείμενους παράγοντες. Ο χρόνος επεξεργασίας και ο απαιτούμενος χώρος εκτιμώνται από μία συνάρτηση f(n), που εκφράζει τη χρονική πολυπλοκότητα ή την πολυπλοκότητα χώρου
• Σε πολλές περιπτώσει όμως δεν μας ενδιαφέρουν οι ακριβείς τιμές αλλά η γενική συμπεριφορά του αλγορίθμου, δηλ. η τάξη του αλγορίθμου. Για αυτό τον σκοπό εισάγουμε τον συμβολισμό Ο
• πεξεργασίας (processing time)


  Χρόνος επεξεργασίας
• χωρητικότητα μνήμης (memory space)


  Απαιτούμενος χώρος
• Μειονεκτήματα


  • Δεν μπορεί να προβλεφθεί η συμπεριφορά του αλγορίθμου για κάποιο άλλο σύνολο δεδομένων
  • Ο χρόνος επεξεργασίας εξαρτάται από το υλικό, τη γλώσσα προγραμματισμού και το μεταφραστή, και προπάντων από τη δεινότητα του προγραμματιστή
• Θεωρητικός (theoretical) ή αλλιώς εκ των προτέρων (a priori)


  Τρόπος εκτίμησης της απόδοσης
• n


  Μεταβλητή που εκφράζει το μέγεθος του προβλήματος
• f(n)


  Συνάρτηση που εκφράζει τη χρονική πολυπλοκότητα ή την πολυπλοκότητα χώρου
• Ο


  Συμβολισμός που δίνει ένα άνω φράγμα για την πολυπλοκότητα του αλγορίθμου

  
• Ω


  Συμβολισμός που δίνει ένα κάτω φράγμα για την πολυπλοκότητα του αλγορίθμου

  
• Θ


  Συμβολισμός που δίνει ένα ακριβές φράγμα για την πολυπλοκότητα του αλγορίθμου

  
• Χρήσιμοι κανόνες - Ο


  1. Αν η f(x) είναι άθροισμα όρων, τότε κρατάμε εκείνον τον όρο που μεγαλώνει πιο γρήγορα

  2. Αν η f(x) είναι γινόμενο όρων, τότε αφαιρούμε όλες τις σταθερές
• Παράδειγμα


  • f(x) = 6x^4 - 2x^3 + 5, g(x) = x^4
• Άσκηση 1


  1. Να υπολογιστεί η τάξη πολυπλοκότητας (αναφορικά με την πράξη του πολλαπλασιασμού) των παρακάτω αλγορίθμων

  2. Ποιος από τους παραπάνω αλγορίθμους είναι πιο γρήγορος