ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ

Παρουσίαση

Οι αλγόριθμοι βρίσκονται στην καρδιά σχεδόν κάθε εφαρμογής για υπολογιστές και η Αλγοριθμική αποτελεί έναν σύγχρονο και ενεργό κλάδο της Επιστήμης των Υπολογιστών. Κάθε επιστήμονας των υπολογιστών και κάθε επαγγελματίας προγραμματιστής πρέπει να γνωρίζει τα βασικά αλγοριθμικά εργαλεία: τις δομές που επιτρέπουν την αποδοτική οργάνωση και ανάκτηση των δεδομένων, τους αλγορίθμους που χρησιμοποιούνται συχνότερα, και τις βασικές τεχνικές για τη μοντελοποίηση, την κατανόηση και την επίλυση αλγοριθμικών προβλημάτων.
Το βιβλίο αυτό αποτελεί μια περιεκτική εισαγωγή και απευθύνεται σε φοιτητές και επαγγελματίες που είναι εξοικειωμένοι με τον προγραμματισμό και τα βασικά μαθηματικά. Τα επιμέρους κεφάλαια καλύπτουν τους πίνακες και τις συνδεδεμένες λίστες, τους πίνακες κατακερματισμού και τους συνειρμικούς πίνακες, την ταξινόμηση και την επιλογή, τις ουρές προτεραιότητας, τις ταξινομημένες ακολουθίες, την αναπαράσταση και διάσχιση γραφημάτων, τις συντομότερες διαδρομές, τα ελάχιστα γεννητικά δένδρα, και τη βελτιστοποίηση.
Οι αλγόριθμοι παρουσιάζονται με έναν μοντέρνο τρόπο, ο οποίος περιλαμβάνει ρητά διατυπωμένες αναλλοίωτες ιδιότητες μαζί με σχόλια για σύγχρονες τάσεις όπως οι τεχνολογίες υλοποίησης αλγορίθμων, οι ιεραρχίες μνήμης, οι βιβλιοθήκες αλγορίθμων, και οι αλγόριθμοι πιστοποίησης. Για την περιγραφή και την εξήγηση των αλγορίθμων χρησιμοποιούνται σχήματα, λεκτικές περιγραφές και ψευδοκώδικας υψηλού επιπέδου, ενώ στη συνέχεια παρουσιάζονται περισσότερες λεπτομέρειες για την αποδοτική υλοποίησή τους σε πραγματικές γλώσσες προγραμματισμού όπως η C++ και η Java. (Από την παρουσίαση στο οπισθόφυλλο του βιβλίου)

Περιεχόμενα

Πρόλογος της ελληνικής έκδοσης
1 Ορεκτικό: Αριθμητική ακεραίων
Πρόσθεση
Πολλαπλασιασμός: Η σχολική μέθοδος
Έλεγχος αποτελέσματος
Μια αναδρομική εκδοχή της σχολικής μεθόδου
Πολλαπλασιασμός Karatsuba
Τεχνολογίες υλοποίησης αλγορίθμων
Τα προγράμματα
Αποδείξεις του Λήμματος 1.5 και του Θεωρήματος 1.7
Σημειώσεις υλοποίησης
Ιστορικές σημειώσεις και πρόσθετες διαπιστώσεις
2 Εισαγωγή
Ασυμπτωτικός συμβολισμός
Το μοντέλο μηχανής
Ψευδοκώδικας
Σχεδιασμός ορθών αλγορίθμων και προγραμμάτων
Ένα παράδειγμα - Δυαδική αναζήτηση
Βασική ανάλυση αλγορίθμων
Ανάλυση μέσης περίπτωσης
Τυχαιοκρατικοί αλγόριθμοι
Γραφήματα
Ρ και ΝΡ
Σημειώσεις υλοποίησης
Ιστορικές σημειώσεις και πρόσθετες διαπιστώσεις
3 Αναπαράσταση ακολουθιών με πίνακες και συνδεδεμένες λίστες
Συνδεδεμένες λίστες
Μη φραγμένοι πίνακες
Επιμερισμένη ανάλυση
Στοίβες και ουρές
Λίστες και πίνακες
Σημειώσεις υλοποίησης
Ιστορικές σημειώσεις και πρόσθετες διαπιστώσεις
4 Πίνακες κατακερματισμού και συνειρμικοί πίνακες
κατακερματισμός με αλύσωση
Καθολικός κατακερματισμός
Κατακερματισμός με γραμμική ανίχνευση
Αλύσωση και γραμμική ανίχνευση
Τέλειος κατακερματισμός
Σημειώσεις υλοποίησης
Ιστορικές σημειώσεις και πρόσθετες διαπιστώσεις
5 Ταξινόμηση και επιλογή
Απλοί ταξινομητές
Συγχωνευτική ταξινόμηση - Ένας αλγόριθμος χρόνου O (n log n)
Ένα κάτω φράγμα
Ταχυταξινόμηση
Επιλογή
Παραβίαση κάτω φράγματος
Εξωτερική ταξινόμηση
Σημειώσεις υλοποίησης
Ιστορικές σημειώσεις και πρόσθετες διαπιστώσεις
6 Ουρές προτεραιότητας
Δυαδικοί σωροί
Διευθυνσιοδοτήσιμες ουρές προτεραιότητας
Εξωτερική μνήμη
Σημειώσεις υλοποίησης
Ιστορικές σημειώσεις και πρόσθετες διαπιστώσεις
7 Ταξινομημένες ακολουθίες
Δυαδικά δένδρα αναζήτησης
(a, b) - δένδρα και μελανέρυθρα δένδρα
Περισσότερες λειτουργίες
Επιμερισμένη ανάλυση των λειτουργιών ενημέρωσης
Επαυξημένα δένδρα αναζήτησης
Σημειώσεις υλοποίησης
Ιστορικές σημειώσεις και πρόσθετες διαπιστώσεις
8 Αναπαράσταση γραφημάτων
Μη διατεταγμένες ακολουθίες ακμών
Πίνακες γειτνίασης - Στατικά γραφήματα
Λίστες γειτνίασης - Δυναμικά γραφήματα
Η αναπαράσταση με μητρώα γειτνίασης
Έμμεσες αναπαραστάσεις
Σημειώσεις υλοποίησης
Ιστορικές σημειώσεις και πρόσθετες διαπιστώσεις
9 Διάσχιση γραφημάτων
Αναζήτηση πρώτα κατά πλάτος
Αναζήτηση πρώτα κατά βάθος
Σημειώσεις υλοποίησης
Ιστορικές σημειώσεις και πρόσθετες διαπιστώσεις
10 Συντομότερες διαδρομές
Από τις βασικές έννοιες σε έναν γενικό αλγόριθμο
Κατευθυνόμενα άκυκλα γραφήματα
Μη αρνητικό κόστος ακμών (αλγόριθμος του Dijkstra)
Ανάλυση μέσης περίπτωσης για τον αλγόριθμο του Dijkstra
Μονοτονικές ουρές προτεραιότητας ακεραίων
Αυθαίρετο κόστος ακμών (ο αλγόριθμος των Bellman-Ford)
Πανζευκτικές συντομότερες διαδρομές και δυναμικά κόμβων
Ερωτήματα συντομότερων διαδρομών
Σημειώσεις υλοποίησης
Ιστορικές σημειώσεις και πρόσθετες διαπιστώσεις
11 Ελάχιστα γεννητικά δένδρα
Ιδιότητες αποκοπής και κύκλου
Ο αλγόριθμος των Jarnik-Prim
Ο αλγόριθμος του Kruskal
Η δομή δεδομένων union-find
Εξωτερική μνήμη
Εφαρμογές
Σημειώσεις υλοποίησης
Ιστορικές σημειώσεις και πρόσθετες διαπιστώσεις
12 Γενικές τεχνικές βελτιστοποίησης
Γραμμικός προγραμματισμός
Άπληστοι αλγόριθμοι - Ποτέ μην κοιτάς πίσω
Δυναμικός προγραμματισμός - Κατασκευάζοντάς το κομμάτι-κομμάτι
Συστηματική αναζήτηση - Σε περίπτωση αμφιβολίας, χρησιμοποίησε ωμή βία
Τοπική αναζήτηση - Σκέψου σφαιρικά και δράσε τοπικά
Εξελικτικοί αλγόριθμοι
Σημειώσεις υλοποίησης
Ιστορικές σημειώσεις και πρόσθετες διαπιστώσεις
Α' Παράρτημα
Μαθηματικά σύμβολα
Μαθηματικές έννοιες
Βασική θεωρία πιθανοτήτων
Χρήσιμοι τύποι
Βιβλιογραφία
Αγγλοελληνικό λεξικό όρων
Ελληνοαγγλικό λεξικό όρων
Ευρετήριο