Μάθημα 1 (μέρος Α) / Εισαγωγικά - Βασικά Στοιχεία Σχεδιασμού και Ανάλυσης Αλγορίθμων (μέρος Α)
Εισαγωγικά - Βασικά Στοιχεία Σχεδιασμού και Ανάλυσης Αλγορίθμων (μέρος Α): Άλλη ακαδημαϊκή χρονιά σε όλους και καλή πρόοδο που ονομάζομαι Χρήστος Ζαρολιάγκης είμαι καθηγητής στο τμήμα για όσους δεν με ξέρουν και μαζί θα κάνουμε το μάθημα εισαγωγής αλγόριθμους στα πλαίσια των ανοιχτών διαλέξεων του π...
| Κύριος δημιουργός: | |
|---|---|
| Γλώσσα: | el |
| Φορέας: | Πανεπιστήμιο Πατρών |
| Μορφή: | Video |
| Είδος: | Ανοικτά μαθήματα |
| Συλλογή: | Τμήμα Mηχανικών Η/Υ & Πληροφορικής / Εισαγωγή στους Αλγόριθμους |
| Ημερομηνία έκδοσης: |
ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ
2014
|
| Θέματα: | |
| Άδεια Χρήσης: | Αναφορά-Μη-Εμπορική Χρήση-Όχι Παράγωγο Έργο |
| Διαθέσιμο Online: | http://delos.upatras.gr/opendelos/videolecture/show?rid=e9564a2f |
| Εισαγωγικά - Βασικά Στοιχεία Σχεδιασμού και Ανάλυσης Αλγορίθμων (μέρος Α): Άλλη ακαδημαϊκή χρονιά σε όλους και καλή πρόοδο που ονομάζομαι Χρήστος Ζαρολιάγκης είμαι καθηγητής στο τμήμα για όσους δεν με ξέρουν και μαζί θα κάνουμε το μάθημα εισαγωγής αλγόριθμους στα πλαίσια των ανοιχτών διαλέξεων του πανεπιστημίου που είναι ένα έργο το οποίο ξεκίνησε από πέρσι σε κάποιες από τις διαλέξεις αυτές στα δύο εντός που πείθουν για καθαρά οφέλη δυστυχώς λόγους από την πλευρά των φοιτητών έτσι ώστε θα αναρτηθούν σε μια πλατφόρμα νομίζω το Classic κάποια άλλη πλατφόρμα όχι πια στο πανεπιστήμιο στο πλαίσιο του ψηφιακού άλματος για την διεξαγωγή των μαθημάτων έτσι ώστε κάποιος σου ποιος είναι εδώ δεν θυμάται καν ένα μέρος διαλέξεις θα μπορεί μετά αργότερα να την ξαναβρεί για παράδειγμα τις καλύτερες σημείωση κάποιος έμπορος παρακολούθηση μαύρη επίσης στη διάλεξη γι αυτό θα υπάρχει κάποιος που διάλεξε την αρχή του μαθήματος βιντεοσκόπηση για αυτό το λόγο σχετικά με το μάθημα αυτό σήμερα θα δούμε μερικά εισαγωγικά διαδικαστικά ζητήματα στο σημερινό και στο αυριανό μάθημα θα σας εξηγήσω τη σημασία του μαθήματος όχι μόνο θεωρητική για το μάθημα είναι θετικό αλλά κυρίως στην τεχνολογική σ.σ. όχι γιατί το κάνουν γιατί έτσι πραγματικότητα δηλαδή το σχεδιασμός και ανάλυση αλγορίθμων κυρίως σχεδιασμός και ανάλυση αποδοτικό αλγόριθμο είναι κάτι για το οποίο δεν θα υπήρχε ποτέ η τεχνολογική πρόοδος που σήμερα πολλοί απολαμβάνουν κυρίως από λάβα θα δούμε σιγά σιγά πάγο ενώ σήμερα και αύριο στους δύο διαλέξεις αυτές του μάθημα λοιπόν ξεπλύνετε και 15 χαμένοι σ' αυτήν εδώ την αίθουσα θα θα υπάρχει ένα μίξη διδασκαλίας και φροντιστηρίου δηλαδή θα γίνουν κάποιες διαλέξεις πρώτα όσον αφορά τη θεωρία μετά ακολουθούν διαλέξεις το μυστήριο και ούτω καθεξής υπάρχουν αναλόγως του πώς προχωράμε στην ύλη του Επικουρικού αφορά το φροντιστήριο θα γίνεται αυτόματα για τους φοιτητές του τμήματος ψήνεται συνεργατισμού στο εργαστήριο το οποίο ο επίσης ιστοσελίδα του μαθήματος την οποία καλό θα είναι να επισκεφθείτε και η οποία έχει πάρα πολλή πληροφορία για το μάθημα όπως βιβλιογραφία διαδικαστικά ζητήματα και άλλα πολλά έχετε κάνει στην ζωή του μαθήματος κανείς καλό θα είναι προσπελάσιμοι από την επίσημη ιστοσελίδα του τμήματος και φυσικά από την δική μου προσωπική ιστοσελίδα τώρα όσον αφορά μερικά διαδικαστικά θα υπάρχουν δύο ετών εξετάσεις υπάρχει μια εξέταση πρόοδο εκείνο πια κάνουμε όταν θα έχουμε καλύψει τουλάχιστον το μισό της σελήνης αυτό γίνεται σημείωσε κάποιο σάββατο έτσι όχι για πολύ καιρό σε ανακοίνωση νωρίτερα και ουσιαστικά είναι ένα πρόβα για την τελική εξέταση αυτουνού είναι προς όφελός σας για δύο λόγους πρώτον βλέπετε πώς είναι ήδη εξετάσει η τελική στις περίοδος ιανουαρίου ιουνίου και σεπτεμβρίου και άρα μπορεί να ξέρετε περίπου τι θα περίμενε δεύτερον θα έχετε διαβάσει πάνω από το μισό της ύλης εάν γίνει σόργο τέλη νοεμβρίου αυτή εξαίρεση πρώτου ιανουαρίου μέσα στην περίοδο θα διαβάσει τα δύο τρίτα της ύλης σχετικά κοντά στη λήξη του εξαμήνου αθάνατα πολύ πιο εύκολο να διαβάσουμε για την τελική εξέταση έτσι με λιγότερο κόπο τρίτον και σημαντικότερο οι στατιστικές που έχουμε κάνει τα τελευταία 14 χρόνια που κάνουμε την σας λόγω έχουν δείξει ότι όποιος έχει επιτύχει στην εξέταση πρόοδο που έχει επιτύχει στην τελική εξέταση αντίθετα όσοι δεν έχουν πάει καλά στην πρόοδο με μεγάλη πιθανότητα θα πάνε καλά και στην τελική εξέταση αυτά λένε τα στατιστικά είναι εξετέθη γιαυτό όλοι για αυτό το λόγο θα ήθελα σαφάρι να συμμετέχετε όλοι στην εξέταση πρώτον είναι μόνο προς όφελος σας έτσι με την προϋπόθεση ότι προετοιμαστείτε σωστά ότι δεν έρχεται δεν έρχεται για να πείτε άλλο ένα καφέ Σάββατο στο πανεπιστήμιο ωραία προετοιμαστείτε Διαβάστε iPhone πειστήρια συγκεκριμένα και θα δείτε ότι ο οποίος είχε προετοιμαστεί σωστά θα πάτε καλά στην στην εξέταση τώρα τόσο στην τελική εξέταση όσο και στην εξέταση του χρόνου επιτρέπουμε να έχετε μαζί σας ένα φύλλο Α4 έχουμε το επίσημο σχόλιο αξίας ούτε μπορείτε να γράφετε ότι θέλετε χειρόγραφα όχι Φωτοτυπία κομμάτια ξέρω γω βιβλίων κλπ χειρόγραφα και μόνο ένα φύλλο Α4 δύο σελίδες της παραπάνω δεν επιτρέπεται στο εξής είναι πάρα πολύ μεγάλη πληροφορία μπορείτε να γράψετε εκείνη και νομίζω μέχρι τώρα δηλαδή δεν χρειάζεται να τους πράγματα που δε θες να αποστηθίσει τα πράγματα μπορεί να αναγράφεται και σημασία σε αυτό το μάθημα είναι να μπορείτε να εφαρμόσετε αλγόριθμους συγκεκριμένα παραδείγματα αγνοούμε όχι να παπαγαλίζει ψευδό χωρικά αλγορίθμων απέξω και να μπορείτε επίσης να κάνετε μια στοιχειώδη αναλύσεις έναν αλγόριθμο για να αποδείξετε μια στοιχειώδη μαθηματική ιδιότητα ένα αλγόριθμου παρά τέλος η εξέταση προτού είναι πρόδηλη έτσι είναι αυτός εδώ οδηγός δείχνει τον τον τελικό βαθμό θα πάρετε πού είναι τα δικά σας δικά μας και τα δικά μας δικά σας δηλαδή αν κατεβείτε στην πρόοδο κατά 40% τους πρώτους έξοδα κάτω του πανεπιστημίου και εξέφρασε κι αυτό βγάζει ένα νούμερο ο βαθμός τελικής εξετάζοντας ένα μεγαλύτερο νούμερο το μέγιστο από τα δύο με δικό σας τελικός βαθμός υπάρχει κάποια απορία εγώ επεξεργαστή για αυτό υπάρχει στην ιστοσελίδα του μαθήματος επαναλαμβάνω ότι θέλατε πολύ σοβαρά την έκθεση προόδου και να προσέλθετε όσο καλύτερα προετοιμασμένοι μπορείτε μόνο κέρδος μπορείτε να έχετε τώρα αν δεν έχετε κάποια απορία μετά διαδικαστικά μέχρι τώρα να προχωρήσουμε ως προς το σκοπός του μαθήματος ώρα ο στόχος του μαθήματος είναι η εισαγωγή σαν θεμελιώδες αλγόριθμοι κές έννοιες και τεχνικές είσαστε σε μικρό το δεύτερο έτος στα μαθήματα θεμελιώδεις αλγόριθμους και τεχνικές υπάρχουν πιο προχωρημένες προηγμένες τεχνικές που έγινε στα πλαίσια μαθημάτων επιλογής σε μεγαλύτερα ωραία να σας δώσω έτσι για να καταλάβετε τι θα κάνετε και ότι θέλω να μάθετε και του πως θα πρέπει να στοχεύσετε έτσι την το διάβασμα σας καιρό εμένα αλληγορικό παράδειγμα τότε θα παίρνει το τι πρέπει να περιμένουν σαν το μάθημα πείτε ότι θέλετε να γίνετε γλύπτης καλλιτέχνες ναι οποιοσδήποτε θέλει να γίνει λήπτης πρέπει να μάθει κάποιες βασικές τεχνικές όπως πού θα βρει τα σωστά υλικά πόστα τα συμβουλεύει πως θα μετακινεί πως φτιάχνει για ένα μεγάλο γλυπτό ένα σκαλωσιά έτσι ώστε να μπορεί να ανάπτυξη το έργο του κλπ τώρα το μήνυμα που θέλω να δώσω το εξής ότι η γνώση των τεχνικών αυτών των θεμελιωδών τεχνικών δε θα σας κάνει διάσημο καλλιτέχνη αλλά οποιοσδήποτε καλλιτέχνης ακόμα κι αν είναι οποιοσδήποτε άνθρωπος ακόμα και ένα πολύ μεγάλο πιστωτικό ταλέντο αν δεν γνωρίζει τις βασικές τεχνικές ποτέ δε θα γίνει μεγάλος καλλιτέχνης ώρα ανεξαρτήτως του ταλέντο σας και των ικανοτήτων σας τις βασικές τεχνικές για ένα συγκεκριμένο αντικείμενο πρέπει να μάθουν και επίσης δεν είναι ανάγκη να διακατέχεται πάντα τελεία δεν μπορεί να περιμένουμε να θυμάστε όλα σε άριστο βαθμό το πιο σημαντικό είναι όμως ότι αυτό θα συμβεί εάν έχετε κάνει μια σωστή εκμάθηση ένα σωστό διάβασμα ξέρετε σε σε οποιαδήποτε μελλοντική στιγμή της ζωής σας αν πρέπει να ανατρέψετε κάπου που να ανατρέξετε και που να βρει τα βιβλιοπωλεία κράτησαν θυμηθείτε πιο γρήγορα αυτό είναι αλληγορικά στόχος του μαθήματος τώρα την αλγόριθμους ο αλγόριθμος υπάρχουν διάφοροι ορισμοί είναι μια βήμα προς βήμα διαδικασία που έτσι ουσιαστικά σε έναν πεπερασμένο αριθμό βημάτων μας βρίσκει λύσεις ένα δεδομένο πρόβλημα το οποίο μας δίνει τη ναυτοσύνη ορισμός στο λεξικό αριστερά αυτός είναι ορισμός από τον μουφτή ο πούτιν είναι ένα από τους πρωτεργάτες της μεγάλης επιστήμονες της επιστήμης των υπολογιστών ομότιμος καθηγητής πλέον στο στάνφορντ έχει γράψει τρεις πολύ διάσημα βιβλία κυρίως ευρώ στη δεκαετία του 60 και του 70 ανθρώπους θεμελιώδες της επιστήμης των υπολογιστών και κυρίως τους σχεδιασμό και την ανάλυση των αλγορίθμων είναι ορατός σε μεγάλη ηλικία νομίζουν περίπου κάτι μεταξύ 70 και 80 τώρα σε πιο αφαιρετικά αυτό που θέλω να σας πω είναι ότι ο αλγόριθμος οι αλγόριθμοι γενικά είναι αυτό θα μπορούσα από τα είναι ότι τα μαθηματικά των υπολογιστών η κινητήρια δύναμη πίσω από κάθε ευθύνη ας λογισμικό και θα σας φέρω θα συζητήσουμε τρεις συγκεκριμένα παραδείγματα δύο είμαι σίγουρος ότι τα ξέρετε το τρίτο πιθανόν να μην ξέρατε το πρώτο είναι συσκευές πλοήγησης αυτοκινήτων του Google Transit για παράδειγμα τα θέλετε να μεταβεί κάπου ένα συγκεκριμένο σημείο σε ένα πόλη σε ένα άλλο έκανε το δικό της αυτοκίνητο η μεταμοντέρνα άμεσα δημόσιας αναφοράς ώρα πίσω λοιπόν από την συσκευή πλοήγησης αυτοκινήτων που στα ελληνικά κακώς λέμε GPS υπάρχει ένα ευφυής αλγόριθμος όποιος σας βρίσκει την πληροφορία σας για τη διαδρομή και σας καθοδηγεί στο πώς να προχωρήσετε και να στρέψετε την ταχύτητα να αναπτύξετε για να φτάσετε γρήγορα το ίδιο έχει ταξιδέψει κανείς στην Ευρώπη ωραία ευρωπαϊκά ταμεία παραδείγματα την κεντρική Ευρώπη ελβετία Γερμανία αυστρία Γαλλία έχει ένα πολύ ωραίο δίκτυο δημόσιων μεταφορών που κυρίως βασίζεται στο σιδηρόδρομο εάν πάτε λοιπόν στην ιστοσελίδα των σιδηροδρομικών το σιδηρόδρομο των γερμανικών σιδηροδρόμων για παράδειγμα μπορείτε να δώσετε app που την αφετηρία ένα σταθμό τρένου προς τον προορισμό σας σε μια πολύ ωραία εφαρμογή διαδικτύου είτε ακόμα και τη διεύθυνση του σπιτιού σας και από και ξεκινάτε δηλαδή μέχρι τη διεύθυνση του φίλου σας που θέλετε να επισκεφθείτε και σας λέει σας δίνει πληροφορία για συνδυασμό μέσων μαζικής μεταφοράς τρένα Μετρό πιθανόν αστικά λεωφορεία έτσι ώστε να να μετακινηθείτε από τον προορισμό από την αφετηρία σας στον προορισμό σας πιστά στον παιδίατρο πίσω από αυτό το CD αυτή τη συγκεκριμένη εφαρμογή την οποία είναι κάτι παρόμοιο με αυτό που κάνει το Google Transit για όσους έχουν δεν υπάρχει κάποιος σαφής αλγόριθμος εάν δεν ήταν ευφυείς αλγορίθμους δεν θα μπορούσατε να πάτε απόκριση σε χιλιοστά του δευτερολέπτου για γιατί αυτός ο χρόνος απόκρισης αυτών των αλγόριθμο θα είναι πάρα πολλά δευτερόλεπτα έως και λεφτά και θα μπορούσατε ποτέ να περιμένει κανείς 8 λεπτά για να πάρει μια τέτοια απάντηση ένα δεύτερο μια δεύτερη εφαρμογή είναι το ξέρετε ήδη αν θέλετε να κάνετε μια αναζήτηση τώρα πιο δημοφιλής μηχανή αναζήτησης μηχανή αναζήτησης της εταιρείας Google και όχι τυχαία είναι πιο δημοφιλής μηχανή αναζήτησης πιθανόν να κατέβει άκουσε ότι πίσω από αυτή τη μηχανή μετά ένα μυστηριώδες αλγόριθμος έτσι τονωθούν βελτίωση νευρωτικό τρόπο συνεχώς και αυτό την καθιστά πραγματικά την πιο καλή μηχανή αναζήτησης σήμερα οι ίδιοι ιδέα η βασική ιδέα αυτού του αλγόριθμου είναι πάρα πολύ απλή και θα δούμε στα επόμενα μαθήματα της όλοι αυτοί έχουν κάνει μόνο οι ελβετικές επεκτάσεις αυτές τις συνήθεις σχολείου βασικής είναι ένα αλλά θέλω να σας πω ότι πίσω από την επιτυχία κρύβεται ένα πολύ δυνατός αλγόριθμους που έδωσε πολύ μεγάλη ευθύνη δόξα και χρήμα φυσικά αυτούς εφευρέτες αφήσει δεν ένα άλλο μια άλλη εφαρμογή είναι οι συστάσεις του κάνετε μέσω των εφαρμογών διαδικτύου αυτό που λέγεται ίσο που αγοράσετε διάφορα προϊόντα αγοράζω σκάφη και μετά σου λένε εφαρμογή ότι μπορείς επιδοτεί χρήστες με παραπλήσια ενδιαφέροντα σαν να δικάσουν υποχωρούσε αυτό το προϊόν αγόρασαν και ένα άλλο που φθάνουν μέχρι και σε αυτοί οι συστάσεις για το τι μπορεί να αγοράσει επίσης κρύβεται από πίσω τους κρύβονται αίφνης αλγόριθμοι και μπορούν να κάνουν αυτή τη συγκεκριμένη αν θέλετε παρουσίαση άλλων προϊόντων που ταιριάζουν πολύ με τα χαρακτηριστικά σας τελειώσουμε έτσι πολλοί τρανταχτή εφαρμογή με την έννοια της πολύ μεγάλης απήχησης ήταν πριν τέσσερις χρόνια στο χρηματιστήριο της νέας υόρκης όπου ήδη παρά το 70% των χρηματιστηριακών συναλλαγών συναλλαγών πραγματοποιούνται μέσω ευφυών αλγόριθμο και μάλιστα κάποιες κατάφερε το μάιο του 2010 δημιούργησαν 30 λεπτό κραχ όπως λέγεται στο χρηματιστήριο της νέας υόρκης διότι κατάφερε να πουλήσει 2,6 εκατομμύρια λίρες περίπου δηλαδή 3000000000 ευρώ μετοχές σε μόλις 20 λεπτά μέσω κάποιου Νέου λογισμικού που μπορούν μπορεί σε βάζο όταν θα πουληθεί αλγόριθμο και μπόρεσε να πουλήσει πιο γρήγορα αυτές συμμετοχές από κάποιους άλλους δήμους πραγματικά πολύ μεγάλο πανικό του τώρα θέλω να σας πω ότι οποιοσδήποτε οποιαδήποτε απορία ενέργεια του μαθήματος διστάζει να διακοπεί με ρωτάει με συνεχίζοντας στο ίδιο μοτίβο υπάρχουν δύο σημαντικά κομβικά σημεία στην εξέλιξη της ανθρωπότητας Νάξου υπάρχουν περισσότερα από δύο προφανώς αλλά δύο θεωρούνται από τα πλέον σημαντικότερα ξέρει κανείς στο ένα ένα πιθανό το ξέρετε δηλαδή ελάμβανε μπορεί κανείς να μαντέψει ορίστε πήγε πολύ πίσω τη φωτιά βρήκαν αλλά ζούσαν ακόμα στα σπήλαια της μέρα είδα το πρώτο σημείο ήταν η ανακάλυψη της τυπογραφίας από έναν γερμανό ότι υπογράφουν που ζούσε στο μάλιστα γερμανίας όποιος κατάφερε να εκτυπώσει βιβλία με μεταλλικά στοιχεία έτσι του Ιωάννης Γουτεμβέργιου όπως λέμε στα ελληνικά το 1440p το δηλαδή το 15ο αιώνα μέχρι τότε ξέρετε πως γινότανε η αναπαραγωγή βιβλίων έχει σημασία αυτό γιατί αυτό έχει ιδιαίτερη σημασία να παραγωγή βιβλίων γιατί χωρίς βιβλία δεν μπορείτε να βρείτε ένωσης έτσι η γνώση η γνώση βέβαια μέχρι τότε μέχρι τότε την εποχή του Γουτεμβέργιου ήτανε στον δυτικό κόσμο αλλά και των πρώην ανατολικών και τη βυζαντινή αυτοκρατορία και μετέπειτα κλεισμένοι στα μοναστήρια Βρετανοί βιβλιοθήκες που είχανε τα μοναστήρια και είχαν τους γράφει σε όποια αντιγραφή ναι με το χέρι διάφορα βιβλία έτσι από την εποχή της Βιβλιοθήκης Αλεξανδρείας μέχρι και βιβλιοθήκες που ανέχεται Διαβάστε βιβλία του Ουμπέρτο Έκο πως το όνομα του πρώτου έργου σας θα έχετε ήδη θα έχετε πάρει μια ιδέα αυτής της της εποχής ούτε αύριο λοιπόν έκανε την αναπαραγωγή βιβλίων πάρα πάρα πολύ εύκολη και αυτό είναι πάρα πολύ σημαντικό σημείο στην εξέλιξη ανθρωπότητας Επιπλέον η γνώση δεν ήταν κλεισμένοι στα μοναστήρια και στους λίγους στη γνώση που απέκτησαν πρόσβαση όλοι μπορεί βέβαια αυτό σας φαίνεται περίεργο στην εποχή του διαδικτύου ζείτε που απάντησαν χθες από τα πάντα ένα κλικ μακριά έτσι πληκτρολογείτε ότι θέτει στη μηχανή αναζήτησης Google και παίρνει την απάντηση είναι πάρα πάρα πολύ μεγάλη ξανά αυτό που θέλω είναι τότε υπήρχαν τα τυπωμένα βιβλία και η νέα επαναλαμβάνω οδηγούμαστε μοναστήρια έτσι αφορά πολύ μεγάλη επανάσταση γιατί πλέον η γνώση έφτασε σε όλα τα στρώματα των ανθρώπων όχι μόνο στους πολύ πλούσιους εις αυτούς που είχαν μόνο πρόσβαση στην στη γνώση το δεύτερο σημείο είναι οι αγορές οι αλγόριθμοι που την πρωτομαγιά στην πρωτόλεια μορφή τους ήτανε οι βασικές αριθμητικές μέθοδοι δεν που κάνουμε πολλαπλασιασμό προσθέσει διαίρεση έτσι αφαίρεση Everest παραγωγικής ρίζας και κλπ αυτά που μαθαίνουμε στο δημοτικό αυτά τα βρήκε ένα αιρέσεις μαθηματικός και αστρονόμος με το όνομα αλλά βασισμένη όποιος βάσισε τις βασικές τις αριθμητικές μεθόδους στο δεκαδικό σύστημα το δεκαδικό σύστημα που σήμερα το έχουμε πώς το λένε στην καθημερινότητά μας και θεωρούμε ότι ότι προϋπήρχε δεν προϋπήρχε εδώ ξανά μόνο κάποια συνθήκη υπέρ σας μέχρι τότε και ξέρει κανείς πότε στην Ευρώπη έφτασε το δεκαδικό σύστημα ακριβώς από τον Λεονάρντο φιμπονάτσι δηλαδή φιμπονάτσι πέρα από τα πολύ καλά μαθηματικά που έκανε τους αριθμούς Βουνάτσου να ξέρετε αυτό που έκανε κυρίως είναι καταλαβαίνει την σημασία το βιβλίο που ουσιαστικά είναι έτσι πάμε στην ουσιαστικά και υπάρχουν και οι μέθοδοι που κάνει στην γαλλική στο βιβλίο αυτό από τους πρωτογενείς αυτές αριθμητικές πράξεις μετάφραση στα λατινικά και την αξία του την κατάλαβε πολύ γρήγορα φύγουν έτσι και ουσιαστικά βοήθησε στο να καθιερωθεί το δεκαδικό αριθμητικό σύστημα στην Ευρώπη φανταστείτε τώρα να κάνετε αριθμούς με λατινικά στοιχεία η αρχαία ελληνικά αυτό δεν σας λέει τίποτα ενώ το θέλετε πολύ εύκολα όπως το κάνουν στην πράξη σε αυτό βοήθησε πάρα πολύ την ανάπτυξη του εμπορίου και ανάπτυξης οικονομίας και γενικότερα να βρεις άνθρωπο ας αλλά εάν δεν υπήρχαν αυτοί εδώ οι αλγόριθμοι δεν θα μπορούσε να διαλέξαμε τρόπο να κάνουμε πράξεις με στοιχεία δε θα μπορούσαμε ένα να δούμε την σημερινή οικονομική εμπορική και τεχνολογική εξέλιξη ετυμολογικά λοιπόν ο αλγόριθμος προέρχεται από τη λέξη αλγόριθμος που σημαίνει διαδικασία εκτέλεσης αριθμητικών πράξεων χρησιμοποιώντας 10 δικούς τους λεγόμενους αραβικούς αριθμούς είναι πολύ λάθος να πιστεύετε ότι ο αλγόριθμος προέρχεται από την ελληνική λέξη από την ελληνική λέξη καταρχήν αποδυτήρια άλγος σημαίνει πόνος επίπονος και αριθμός στον λάθος λέξη αλγόριθμους είναι παραφθορά του ονόματός του αν γνωρίζουν πλήρως τώρα σχεδιασμός και ανάλυση αλγορίθμων ήταν μια ιδέα του γνωστή ήδη από την αρχή όταν δηλαδή ο αλγόριθμος του ευκλείδη για σήμερα στις πμ δύο αιρετοί ήταν ήδη γνωστός αλλά αποσπασματικές αυτές οι προσπάθειες οι αλγόριθμοι του Alvarez επιζεί εθνικές πράξη ήταν επίσης ένα πολύ σημαντικό βήμα όπως εξήγησα αλλά η συστηματική μελέτη και ανάλυση θα μπορέσουν ξεκίνησε πάρα πάρα πολύ πρόσφατα μετά το 1970 και ανάλυση αλγορίθμων απαιτεί μαθηματική σκέψη και ικανότητα επίλυσης προβλημάτων και αυτά είναι που θα δούμε στους δικούς τους στο μάθημα αυτό τώρα οι εφαρμογές εκτός από αυτές που σας πρωί πατήστε τρεις σημαντικά παραδείγματα μπορείτε να βρείτε εφαρμογές πάρα πολλές ΑΦΜ τα δίκτυα το διαδίκτυο όπως σας είπα την επιχειρησιακή έρευνα τεχνητή νοημοσύνη υπολογιστική βιολογία κρυφή μνήμη τώρα ξέρετε οι υπολογιστές δεν έχουν μια και έχουν πολλά στρώματα μνήμης μεταξύ του επεξεργαστή και της κύριας μνήμης υπάρχει λεγόμενη κρυφής μνήμης ένα η περισσότερα στρώματα όπως κάνεις φέρνει δεδομένα από την κα ν στους καταχωρείται στο επεξεργαστή δεν είναι μια κάρτα τετριμμένα γιατί μπορεί να S ένα πληροφορία η οποία δεν υπάρχει στην κρυφή μνήμη αλλά μπορεί να υπάρξει κα μ αυτόν σου επιφέρει μεγάλη καθυστέρηση στους υπολογισμούς ειδικά όταν κανείς διαχειρίζεται πολύ μεγάλο όγκο δεδομένων όπως και το συνεργαζόμενο ωραία και θα δείτε επίσης υπάρχει βάση δεδομένων ομολόγησε το ξέχασε σημάτων γραφικά υπολογιστών κλπ εμείς θα εστιάσουμε σε βασικές τεχνικές κάνουμε ορισμένους τους ο οποίος θα είναι χρήσιμη στην πράξη τώρα ύλη του μαθήματος τα πρώτα μαθήματα θα δούμε μερικά βασικά στοιχεία για το σχεδιασμό και την ανάλυση των αλγορίθμων θα συζητήσουμε την σημαντική έννοια της αποδοτικότητας των αλγορίθμων που συνοδεύεται επίσης από την πολυπλοκότητα και το λεγόμενο οξειδωτικό συμβολισμό πώς μετράμε δηλαδή την αποδοτικότητα αυτό όμως είναι πολύ κοντά θα συζητήσουμε ζητήματα ορθότητας αλγορίθμου θα δούμε μερικές βασικές δομές δεδομένων της απολύτως απαραίτητες για τη διεξαγωγή του μαθήματος γιατί υπάρχει στο εαρινό εξάμηνο ειδικό μάθημα εδώ μέσα και μένω που θα δείτε είναι μια πολύ μεγαλύτερη οικογένεια ομολογουμένως Σταυρούλα λέει λίστες πίνακες και αγορές προβαίνοντας και αφού δούμε αυτά τα βασικά θα ξεκινήσουμε με μια μένα με αλγόριθμους επίλυσης ένα πολύ σημαντικού προβλήματος με ταξινόμηση στοιχείων πως ταξινομούν με αριθμούς η α αρνητικά στοιχεία η οτιδήποτε άλλο στη συνέχεια θα παρακολουθεί θα μάθουμε μια μέθοδος που λέγεται διαίρει και βασίλευε η βασική της ιδέα είναι ότι όταν θέλουμε να επιλύσουμε ένα βασικό πρόβλημα κάνουμε διάσπαση του προβλήματος σε μικρότερα προβλήματα και εφαρμόσουμε Δημήτρια αναδρομικά μέχρις ότου να πάρουμε και υπό προβλήματα έχουν πολύ μικρό μέγεθος το οποίο μπορούμε να επιλύσουμε τα προφανή τρόπο και μετά κάνουμε σύνθεση των επιμέρους λύσεων των προβλημάτων για να βρούμε την λύση στο συνολικό μας το δικό μας πρόβλημα αργότερα θα ασχοληθούμε κι αυτόν το πιο σημαντικό κομμάτι μεταγραφή ματάκια αλγορίθμου γραφημάτων τα γραφήματα είναι ένα μαθηματικό μοντέλο το οποίο μας επιτρέπει να αναπαριστούν με όποια οποιοδήποτε δίκτυο φυσικό δίκτυο υπολογιστικό δίκτυο ιδεατό δίκτυο κλπ όπως ο τον παγκόσμιο ιστό για παράδειγμα ένα οδικό δίκτυο ένα κοινωνικό δίκτυο και ούτω καθεξής και να δούμε που βασικός αλγόριθμους γραφημάτων και εδώ θα συζητήσουμε τον αλγόριθμο που σας έλεγα πριν πάνω στον οποίο βασίζεται η ανά μηχανή αναζήτησης του εκτός από αυτά θα δούμε μια ένα απλή μέθοδο διαίρει και βασίλευε μια σημαντική δύο σημαντικές μέθοδοι σε αλγόριθμους γραφημάτων είναι δούλος απληστίας και μέρος του δυναμικού προγραμματισμού γενικά η απληστία δεν είναι καλή ζωή αλλά σε μερικές περιπτώσεις μας είναι προφανής αλγόριθμους και σε κάποιες από αυτές που βλέπεις καλά στην πράξη και θα δούμε σημαντικά ζει σημαντικά προβλήματα τα οποία αφορούν στη λεγόμενη βελτιστοποίηση δικτύων δηλαδή θέλουμε να βρούμε ελάχιστα γεννητικά δένδρα θέλουμε να βρούμε συντομότερα διαδρομές ροής ένα δίκτυο συντομότερη διαδρομή σημαίνει αυτό που σας έλεγα πριν με την με το Google Transit in με την AMG με την συσκευή πλοήγησης αυτοκινήτων θέλω να πω από ένα σημείο σε ένα άλλο με το γρηγορότερο δυνατό τρόπος χρόνος χιλιόμετρα σε κόστος λοιπόν ωραία έχουν για χρόνου επιτρέποντας μόνο με κάποια άλλα ειδικά θέματα σε ότι αφορά την βιβλιογραφία κυρίως θα ακολουθήσουμε το πρώτο βιβλίο βιογράφοι υπάρχει στην ζωή του μαθήματος ωραία ένα από τα πολύ καλά βιβλία επίσης είναι και τα υπόλοιπα από το δεύτερο και το τρίτο και πιθανόν σε κάποια σημεία να ακολουθήσουν το ΚΕΠΕ και το δεύτερο βιβλίο αυτά είναι όλα ευτυχώς μεταφρασμένη ξαναβγαίνει μεταφρασμένο στα ελληνικά και μπορείτε να επιλέξετε το κουμπί σας περί ασφάλειας παρόντες απλές δημοσιεύματα συνιστά θεσμική κυρίως στο πρώτο αυτά τώρα υπάρχει κάποια απορία μέχρι εδώ ώρα ένα από τους θεωρείται ο πατέρας των υπολογιστών των υπολογιστικών μηχανών ο Charles Μπαμπατζάν καθηγητή στο πανεπιστήμιο του κέμπριτζ ήταν μαθηματικός αστρονόμος εφευρέτης μηχανικός ήτανε τότε που ήταν οι εποχές ήταν πολύ λίγο από όλα αλλά όταν αυτός έμεινε στην ιστορία της κατασκεύασε στο χαρτί την πρώτη υπολογιστική μηχανή την ονόμασε αναλυτική μηχανή τότε το βλέμμα προσκάλεσαν τους προϋπολογισθέντες δεν κατάφερε τότε τον δέκατο ένατο αιώνα την υλοποίηση έμεινε στο χαρτί αυτή υλοποιήθηκε πολύ αργότερα πολύ πρόσφατα 1191 ακριβώς πάνω στο σχέδιο του μπαμπά της τον την υλοποίησαν και προς μεγάλη τους έκπληξη δούλευε πάρα πολύ καλά έτσι αυτός λοιπόν είπε ότι πρώτον δεν υπάρχει τέτοια μηχανή θα επηρεάσει απαραίτητα τη μελλοντική πορεία της επιστήμης και όντως έτσι συμβαίνει μέχρι σήμερα αλλά το πιο σημαντικό είναι ότι έχει με πιο τρόπο υπολογισμό θα μπορεί αυτή η μηχανή να φτάνει στα αποτελέσματα που θέλουμε στον ελάχιστο χρόνο ότι όλοι αυτό θέλουμε θέλουμε πώς να κάνουμε έτσι την επίλυση πώς θα βρούμε λύση στο πρόβλημά μας με τη βοήθεια ένα υπολογιστή στο συντομότερο δυνατό χρόνο έτσι και για να το πούμε αυτό θα πρέπει να συζητήσουμε συγκεκριμένες έννοιες όπως είναι η αποδοτικότητα η προσέγγιση ανάλυσης το πώς μετράμε την πολυπλοκότητα σε έναν αλγόριθμο χώρα και αυτά θα δούμε σιγά σιγά η αποδοτικότητα δεν τίποτα άλλο παρά η επιθυμία μας για εύρεση του πιο αποδοτικού αλγόριθμου ωραία το θέμα είναι πώς μετράμε την αποδοτικότητα μπορεί κανείς να σκεφθεί καμιά ιδέα για το πώς μετράμε την αποδοτικότητα με ωραία ναι που είναι ο αριθμός των στοιχειωδών πράξεων που κάνει τελευταία δεν μα δεν έχουμε επειδή είναι στοιχειώδης πράξη αλλά πάσει περιπτώσει απάντηση είναι είναι σωστή το θέμα είναι ότι L πρέπει να μετρήσουμε τη λεγόμενη κλιμάκωση του αλγόριθμου δηλαδή πώς μεταβάλλεται συμπεριφορά του αλγόριθμου σε διαφορετικά μεγέθη εισόδου προβλήματος καταλαβαίνετε ότι τους δεν είναι δυνατόν να περιμένετε να ταξινομήσει έδρας του ας πάρουμε το απλό πρόβλημα ταξινόμηση στοιχείων ότι καταβάλλεται μια προσπάθεια ταξινόμησης 1000 στοιχεία 1000 αριθμούς και την προσπάθεια υπολογιστική μήνα ταξινόμησε τα εκατομμύρια έτσι τα πράγματα τότε μεγάλη προσπάθεια ωραία αυτό λοιπόν θα πρέπει κάπως να απεικονίζεται στην κλιμάκωση του αλγόριθμου και αυτό έτσι για να το μελετήσουν αυτό υπάρχουν περιστροφή 1ος τρόπος είναι ελεγχόμενη εμπειρική προσέγγιση δηλαδή ειδικά λεχώνα πρόβλημα γράφω στο πρώτο έτος καλέσει έτσι κάνετε Java ωραία πολύ ωραία παίρνω λοιπόν την αγαπημένη σας γλώσσα προγραμματισμού C Java και τις δύο σκέφτεστε μια λύση προγραμματίζονται μπαίνω στον υπολογιστή σας θέλετε να ο αλγόριθμος μου έτσι για αυτή την ισόβια διάφορα αποτελέσματα δεν μπορεί όμως να δώσετε ένα αντικειμενικό μέτρο γιατί ο φίλος μοναχοί φτιάξει υλοποίηση των δύο αλγόριθμο σε μια άλλη γλώσσα προγραμματισμού να λένε στην κάνεις εσύ δεν είσαι πάντα να χρησιμοποιείτε τελείως διαφορετικό υπολογιστικό περιβάλλον και να βγάζει και αυτός ένα νούμερο δεν μπορεί να συγκρίνεται δηλαδή ανομοιογενή πράγματα ένα γλώσσα προγραμματισμού ακόμα και την Apple πουλούσε προγραμματισμούς διαφορετικά προγραμματίστηκαν περιβάλλοντα και επίσης δεν πρέπει να λησμονούμε ότι όλοι οι άνθρωποι δεν έχουν τις ίδιες ικανότητες κάποιος άλλος μπορεί να καλεί τους προγραμματιστές από κάποιον από εσάς ωραία επομένως αυτό δεν δίνει η WIND εμπειρική προσέγγιση παρόλο που δίνει άμεσα λύση δεν προσφέρει μια αντικειμενική σύγκριση για τον αλγόριθμο το δεύτερο είναι ότι εσείς πράξατε αλγόριθμος σας για μια είσοδο ξέρω γω 10000 στοιχείων αν πάρουμε την ταξινόμηση στοιχείων ως ένα παράδειγμα εάν σας που θα σας δώσουν ένα στιγμιότυπο προβλήματος εκατομμύρια στοιχεία πόσο χρόνο θα κάνει αλγόριθμος σας δεν ξέρετε θα πρέπει να δουν ξανά τρέξετε για λόμπι να νιώσω λόγο θα ήθελα μια εκτίμηση τις αποδόσεις του αλγόριθμου για μεγαλύτερα μεγέθη ίσο χορεύει για μικρότερα αντίστοιχα ο δεύτερος δρόμος αλλά για αυτό το λόγο αυτό ακριβώς έρχεται αυτό το ζήτημα έρχεται να το λύσει έτσι να το απαντήσει η ανάλυση αλγορίθμων ουσιαστικά θέλουμε με την ανάλυση αλγορίθμων θέλουμε να προβλέψουμε τους πόρους που χρειάζεται ένα αλγόριθμος σαν συνάρτηση του μεγέθους της εισόδου όταν εννοούμε μπορούσαν υπολογιστικών πόρων δηλαδή κυρίως ο χρόνος θα μας απασχολήσει όπως ο χώρος στην υπάρχουν πολλοί επεξεργάστηκαν συστήματα όπου εκεί πόροι που ανεπεξέργαστα στα μηνύματα επικοινωνίας που ανταλλάσσουν μεταξύ τους οι αποκαλύψεις αλλά αυτά δε θα μας απασχολήσουν και φυσικά για επαναλαμβάνω ότι όταν έχουμε ένα μοντέλο πρόβλεψης των απαιτούμενων πόρων ανάλογα με την είσοδο του προβλήματος τότε μπορούμε να πούμε πραγματικά για κάθε στιγμιότυπο εισόδου περίπου τι απόδοση περιμένουμε από τον αλγόριθμο όταν υλοποιηθεί σε μια πραγματική γνώση προγραμματισμού φυσικά όμως ανάλυση για να γίνει ανάλυση πέντε μοντέλο αξιολόγησης της πολυπλοκότητας ένα άλλου ωραία και χρονική πολυπλοκότητα είναι αυτό που πολύ σωστά είπε συνάδελφος σας ο χρόνος εκτέλεσης είναι ο αριθμός στοιχειωδών λειτουργιών που εκτελούνται από τον αλγόριθμο σαν συνάρτηση του μεγέθους της εισόδου ωραία επαναλαμβάνω το μόνο που θέλω να συζητά να κρατήσετε μέχρι εδώ είναι το εξής ότι η ανάλυση αλγορίθμων σημαίνει προβλέπω τους υπολογιστικού σπόρους κυρίως σε χρόνο και χώρο κουβέντα χρόνια σε πόσο χρόνο θα τρέξει αλγόριθμο μας δηλαδή αριθμό στοιχειωδών λειτουργιών και σαν χώρος πόσα λέξεις μήνυση ποσά by στα κανάλια στη μνήμη του υπολογιστή και εφόσον έχω αυτό τότε μπορώ να έχω και πρόβλεψη και αυτό το εκμεταλλεύονται οι δύο άλλες προσεγγίσεις που μετρά την αποδοτικότητα του αλγόριθμου η πρώτη είναι η λεγόμενη η δεύτερη προσέγγιση γιατί πρώτα κεντρική είναι ελεγχόμενη πολυπλοκότητα χειρότερες περιπτώσεις πολυπλοκότητα χειρότερες περιπτώσεις μας δίνει ένα άνω όριο σε οποιοδήποτε στιγμιότυπο πίσω δηλαδή λέμε στη χειρότερη περίπτωση 1000 στο χειρότερο στιγμιότυπο εισόδου όσα υπολογιστικά πόσα στοιχειώδη βήματα θα κάνει αλγόριθμος μας αυτό είναι το όριο που βγάζουν μπορεί να είναι δρακόντεια το μέτρο δηλαδή γιατί μπορεί να υπάρχουν πολύ λίγα στιγμιότυπα που έχουν αυτήν την πολύ κακή συμπεριφορά και μας οδηγούν σε μεγάλους χρόνους εκτέλεσης αλλά δεν πίστεψε ότι δεν υπάρχει αποτελεσματική εναλλακτική λύση επίσης αυτή προσέγγιση σε αντίθεση με την προηγούμενη με την εμπειρική είναι ομοιογενής παρέχει ένα καλώς ορισμένων συγκριτικό μέτρο για απόδοση διαφορετικών αλγορίθμων μεταξύ τους ωραία υπάρχει δηλαδή ομοιογένεια και φυσικά προσφέρει πληροφορία κλίματος τι πρέπει να προσέχεις σε που επίσης είναι σημαντική αλλά είναι οι λεγόμενοι πολυπλοκότητα άμεσα τις περιπτώσεις δηλαδή εδώ που τα λέμε επειδή όπως σας είπα πριν μπορεί τα κακά στιγμιότυπα εισόδου να είναι πάρα πολύ λίγα λέμε δεν πειράζει ρε παιδί μου κατά μέσο όρο ο αλγόριθμος μας πόσο χρόνο έχει υπάρχουν όντως αλγόριθμοι που έχουν πάρα πολύ καλή ώρα κατά μέσο όρο έτσι για ατυχία στιγμιότυπο εισόδου και πολύ κακή συμπεριφορά για πολύ λίγα στιγμιότυπα εισόδου το πρόβλημα εδώ είναι ότι θα πρέπει για να μετρήσουμε την πολυπλοκότητα των αλγορίθμων να έχουμε γεννήτριες πιθανόν αντίκες κατανομές πέτυχαν είσοδο δεύτερον η ανάλυση του αλγόριθμου είναι εξαρτημένοι από την τυχαία κατανομή εισόδου δηλαδή έχουμε άλλη ανάλυση για ομοιόμορφη κατανομή άλλη ανάλυση για καλούσε να μη άλλη ανάλυση για κατανομή ποσών και ούτω καθεξής επομένως και μπορώ να δίνω αυτές τελείως διαφορετικά αποτελέσματα δεν υπάρχει δηλαδή ομοιογένεια ως προς την ανάλυση και τρίτο και τελευταίο και σημαντικότερο ότι απαιτούνται πολύ ισχυρά μαθηματικά εργαλεία για να κάνει κανείς ανάλυση τέτοιων αλγόριθμο που βγαίνουν εκτός μορίων τους του συγκεκριμένου μαθήματος για το λόγο αυτό εμείς δεν θα ακολουθήσουμε ούτε την πρώτη εβδομάδα μα ούτε την τρίτη προσέγγιση παρά θα ακολουθήσουμε την ανάλυση πολυπλοκότητας χειρότερες περιπτώσεις και όπως θα Δείτε η ανάλυση αυτή δίνει πολύ καλά αποτελέσματα λοιπόν εδώ μπορούμε να κάνουμε τα πρώτα μας διάλειμμα |