Παρουσίαση/Προβολή

(ICSD224) -  I. Charalabidis, C. Goumopoulos, A. Kaporis

Περιγραφή Μαθήματος

Σύνδεσμος μαθήματος (zoom)

 

Αλγόριθμοι: είναι αλήθεια ότι μόνο με τον προγραμματισμό μπορούμε να γνωρίσουμε ουσιαστικά έναν αλγόριθμο σε κάθε έκφανση του. Η βαθύτερη αλήθεια όμως είναι ότι μόνο η θεωρία αλγορίθμων έχει την όμορφη δύναμη  να μας κάνει να χαμογελάσουμε  από αυτή την  γνωριμία μας.  Η μακρόχρονη ιστορία του πειραματισμού, της σκέψης, αν θέλετε της «παλαίωσης» της ανθρώπινης εμπειρίας, έχει αναδείξει ως αντιπροσωπευτικότερα  μαθησιακά αντικείμενα τις παρακάτω κατηγορίες αλγορίθμων.   Αρχικά, οι επαναληπτικοί αλγόριθμοι σε κάθε βήμα επαναλαμβάνουν τη βασική ρουτίνα, είναι απλοί, όχι ιδιαίτερα έξυπνοι, για αυτό συνήθως αργούν. Έξυπνη εξέλιξη τους είναι οι διαίρει & βασίλευε αλγόριθμοι.  Για να λύσουν το αρχικό πρόβλημα, λύνουν αναδρομικά μικρότερα και ανεξάρτητα υποπροβλήματα που η σύνθεση τους οδηγεί στην συνολική λύση. Συνήθως είναι αποδοτικοί, όμως, λόγω επικαλύψεων υποπροβλημάτων μπορεί να  αργούν,  διότι λύνουν ξανά & ξανά τα ίδια υποπροβλήματα. Αυτό οδήγησε στην εξέλιξη τους, τον δυναμικό προγραμματισμό όπου η ιδέα είναι να αποθηκεύουμε τις λύσεις των υποπροβλημάτων για κάθε μελλοντική χρήση. Τέλος, οι άπληστοι αλγόριθμοι χαρακτηρίζονται από την οξυδέρκεια να διακρίνουν το «σωστό» υποπρόβλημα, κρυμμένο μεταξύ πολλών δυνατοτήτων, που η καίρια  επίλυση του μας οδηγεί στην συνολική λύση του προβλήματος. Επειδή όμως τα δυνατά υποπροβλήματα είναι πολλά, απαιτείτε οξυμένη προσοχή, για να αποφύγουμε τις διαισθητικά προφανείς «απατηλά σωστές» επιλογές, που στην πραγματικότητα αποβαίνουν λαθεμένες.                      

 

Περιεχόμενομαθήματος (αγγλικά)

Algorithms: it is true that only through programming we can really learn the essential details of an algorithm. But, a more subtle truth is that only the theory of algorithms has the beauty and the power to offer us the joy of smiling while programming. This long lasting and evolving process about experimenting, thinking, and maturing lifelong human experience, has led to some more representative categories of algorithms. An iterative algorithm in each step repeatedly applies the basic routine, hence is simple, not so smart and usually slow. A more clever option is a divide & conquer algorithm. In order to solve the problem, it recursively solves smaller independent  subproblems that their combined solutions yields the global solution. This usually is a faster algorithm, a drawback is that subproblems may highly overlap, which increases running time. A way out is  dynamic programming that stores each solved subproblem to be instantly accessed in the future steps. Finally, a greedy algorithm, has the agile ability to identify the correct subproblem to be solved per step. However, there are exponentially many possible subproblems and we must cautiously avoid the intuitive, albeit “seemingly correct” choice, that eventually misleads the computation path.

 

Ημερομηνία δημιουργίας

Τετάρτη 24 Σεπτεμβρίου 2014