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

Το βιβλίο αυτό αποτελεί μια περιεκτική εισαγωγή στα βασικά εργαλεία: τις δομές που επιτρέπουν την αποδοτική οργάνωση και ανάκτηση των δεδομένων, τους σημαντικούς αλγορίθμους για προβλήματα που αφορούν γραφήματα, και τις γενικές τεχνικές για τη μοντελοποίηση, την κατανόηση και την επίλυση αλγοριθμικών προβλημάτων.

Οι συγγραφείς επιδιώκουν να επιτύχουν μια ισορροπία μεταξύ της απλότητας και της αποδοτικότητας, της θεωρίας και της πράξης, καθώς και των κλασικών αποτελεσμάτων και της ρηξικέλευθης έρευνας. Τα επιμέρους κεφάλαια καλύπτουν τους πίνακες και τις συνδεδεμένες λίστες, τους πίνακες κατακερματισμού και τους συνειρμικούς πίνακες, την ταξινόμηση και την επιλογή, τις ουρές προτεραιότητας, τις ταξινομημένες ακολουθίες, την αναπαράσταση γραφημάτων, τη διάσχιση γραφημάτων, τις συντομότερες διαδρομές, τα ελάχιστα γεννητικά δένδρα, τη βελτιστοποίηση, τη συλλογική επικοινωνία και υπολογισμό, και την εξισορρόπηση φορτίου. Γίνεται επίσης αναφορά σε σημαντικά ζητήματα όπως οι τεχνολογίες υλοποίησης αλγορίθμων, οι ιεραρχίες μνήμης, οι βιβλιοθήκες αλγορίθμων και οι αλγόριθμοι πιστοποίησης. Προχωρώντας ένα βήμα παραπέρα από τους σειριακούς αλγορίθμους και τις δομές δεδομένων της προηγούμενης αντίστοιχης έκδοσης, το βιβλίο λαμβάνει υπόψη τη μεταστροφή προς την παράλληλη επεξεργασία που απαιτείται πλέον για την υλοποίηση εφαρμογών κρίσιμων από πλευράς απόδοσης, καθώς και τον αντίκτυπο που έχει αυτό στη διδασκαλία των αλγορίθμων.

Το βιβλίο απευθύνεται σε προπτυχιακούς/μεταπτυχιακούς φοιτητές και επαγγελματίες που είναι εξοικειωμένοι με τον προγραμματισμό και έχουν βασικές γνώσεις μαθηματικών. Τα περισσότερα κεφάλαια έχουν την ίδια βασική δομή: Οι συγγραφείς περιγράφουν ένα πρόβλημα από τον πραγματικό κόσμο, και κατόπιν παρουσιάζουν πρώτα τις πιο σημαντικές εφαρμογές και μετά απλές λύσεις, χωρίς περισσότερα μαθηματικά από τα απολύτως απαραίτητα, ώστε οι αναγνώστες να αφομοιώσουν πραγματικά τα υπό εξέταση ζητήματα. Καθώς προχωρούν σε πιο προχωρημένα και προαιρετικά θέματα, αυτή η προσέγγιση οδηγεί σταδιακά σε μια περισσότερο μαθηματική αντιμετώπιση που περιλαμβάνει θεωρήματα και αποδείξεις. Το βιβλίο περιλαμβάνει πολλά παραδείγματα, σχήματα, εξηγήσεις που δεν εμπεριέχουν πολύπλοκα μαθηματικά, και ασκήσεις. Τέλος, στις «Σημειώσεις υλοποίησης» παρουσιάζονται διαφανείς, αποδοτικές υλοποιήσεις σε γλώσσες προγραμματισμού όπως η C++ και η Java.

Περιεχόμενα:

Ορεκτικό: Αριθμητική ακεραίων
Εισαγωγή
Αναπαράσταση ακολουθιών με πίνακες και συνδεδεμένες λίστες
Πίνακες κατακερματισμού και συνειρμικοί πίνακες
Ταξινόμηση και επιλογή
Ουρές προτεραιότητας
Ταξινομημένες ακολουθίες
Αναπαράσταση γραφημάτων
Διάσχιση γραφημάτων
Συντομότερες διαδρομές
Ελάχιστα γεννητικά δένδρα
Γενικές τεχνικές βελτιστοποίησης
Συλλογική επικοινωνία και υπολογισμός
Εξισορρόπηση φορτίου
Παραρτήματα

Συγγραφείς: Kurt Mehlhorn, Martin Dietzfelbinger, Peter Sanders, Roman Dementiev