ΑΛΓΟΡΙΘΜΟΙ

Παρουσίαση

Η καινοτομία του βιβλίου του Jeff Edmonds είναι ότι μας εισάγει στην έννοια των αλγόριθμων με έναν μοναδικό τρόπο παρουσίασης, που συνδυάζει τη γλαφυρότητα με τη μαθηματική αυστηρότητα σε μοναδική ισορροπία.
Η μέθοδός του βασίζεται στο τρίπτυχο κατανόηση, σχεδίαση και αξιολόγηση: κατανόηση του υπολογιστικού προβλήματος, σχεδίαση του αλγόριθμου που το επιλύει και αξιολόγησή του όσον αφορά το χρόνο και τη μνήμη που χρειάζεται.
Ο αναγνώστης καθοδηγείται βήμα βήμα, ώστε να αναπτύξει την ικανότητα όχι μόνο να κατανοεί πλήρως τη λειτουργία ενός αλγόριθμου, αλλά και να σχεδιάζει και να αναλύει τους δικούς του αλγόριθμους για μια ευρεία κατηγορία υπολογιστικών προβλημάτων.
Στην προσπάθεια αυτή, θα γνωρίσει μερικά από τα πιο σημαντικά υπολογιστικά προβλήματα της επιστήμης της πληροφορικής σε περιοχές όπως η εξερεύνηση γραφημάτων, η γραμματική ανάλυση προτάσεων, ο χρονοπρογραμματισμός εργασιών με περιορισμούς, ο δυναμικός προγραμματισμός, η αναδρομή, η τεχνική της οπισθοδρόμησης, οι αφηρημένες δομές δεδομένων, η ταξινόμηση και η αναζήτηση, ενώ θα μυηθεί και σε μερικά πιο προχωρημένα θέματα, όπως οι τυχαιοποιημένοι αλγόριθμοι και η υπολογιστική πολυπλοκότητα.
Επιπλέον, το βιβλίο περιέχει, για κάθε αλγοριθμική περιοχή που εξερευνά, μια σειρά ασκήσεων, οι οποίες αφορούν τη συμπλήρωση σημείων που αφέθηκαν κενά σε μαθηματικές αποδείξεις, την προσαρμογή των αλγόριθμων που αναπτύχθηκαν, έτσι ώστε να εφαρμόζονται σε άλλα προβλήματα, καθώς και τη διερεύνηση άλλων τεχνικών μαζί με τα πεδία εφαρμογής τους. (Από την παρουσίαση στο οπισθόφυλλο του βιβλίου)

Περιεχόμενα

Εισαγωγή του επιμελητή Γιάννη Σταματίου
Πρόλογος
Εισαγωγή
ΕΠΑΝΑΛΗΠΤΙΚΟΙ ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΑΝΑΛΛΟΙΩΤΕΣ ΣΥΝΘΗΚΕΣ
Επαναληπτικοί αλγόριθμοι: Μέτρα προόδου και αναλλοίωτες συνθήκες
Παραδείγματα χρήσης αναλλοίωτων συνθηκών βασισμένων στη διαδοχική εξέταση στοιχείων της εισόδου
Αφηρημένοι τύποι δεδομένων
Περιορισμός του χώρου αναζήτησης: Δυαδική αναζήτηση
Επαναληπτικοί αλγόριθμοι ταξινόμησης
Ο αλγόριθμος μέγιστου κοινού διαιρέτη του Ευκλείδη
Η αναλλοίωτη συνθήκη για κάτω φράγματα
ΑΝΑΔΡΟΜΗ
Αφηρημένες έννοιες, τεχνικές και θεωρία
Μερικά απλά παραδείγματα αναδρομικών αλγόριθμων
Αναδρομή σε δέντρα
Αναδρομικές εικόνες
Συντακτική ανάλυση με γραμματικές χωρίς συμφραζόμενα
ΠΡΟΒΛΗΜΑΤΑ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗΣ
Ορισμός των προβλημάτων βελτιστοποίησης
Αλγόριθμοι αναζήτησης σε γραφήματα
Ροές δικτύου και γραμμικός προγραμματισμός
Άπληστοι αλγόριθμοι
Αναδρομική οπισθοδρόμηση
Αλγόριθμοι δυναμικού προγραμματισμού
Παραδείγματα δυναμικών προγραμμάτων
Αναγωγές και πληρότητα NP
Πιθανοκρατικοί αλγόριθμοι
ΠΑΡΑΡΤΗΜΑ
Υπαρξιακοί και καθολικοί ποσοδείκτες
Χρονική πολυπλοκότητα
Λογαριθμικές και εκθετικές συναρτήσεις
Ασυμπτωτική αύξηση συναρτήσεων
Προσεγγίζοντας εύκολα τα αθροίσματα
Σχέσεις αναδρομής
Μια αυστηρή απόδειξη ορθότητας
Λύσεις των ασκήσεων
Συμπέρασμα