ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ (ΕΠΙΤΟΜΟ - ΣΚΛΗΡΟΔΕΤΗ ΕΚΔΟΣΗ)

Παρουσίαση

Κάποια από τα υπάρχοντα εγχειρίδια αλγορίθμων πραγματεύονται το θέμα τους με αυστηρότητα, αλλά είναι ελλιπή κάποια άλλα καλύπτουν μεν μεγάλη έκταση διδακτικής ύλης, αλλά στερούνται αυστηρότητας. Η Εισαγωγή στους αλγορίθμους συνδυάζει με μοναδικό τρόπο την αυστηρότητα με την πληρότητα. Το βιβλίο καλύπτει σε βάθος ένα ευρύ φάσμα αλγορίθμων, διατηρώντας ταυτόχρονα την ανάλυση και τη σχεδίασή τους προσιτή σε αναγνώστες κάθε επιπέδου. Το κάθε κεφάλαιο είναι σχετικά αυτοτελές, και μπορεί να χρησιμοποιηθεί ως αυτόνομη μονάδα μελέτης. Οι αλγόριθμοι περιγράφονται σε φυσική γλώσσα και σε έναν ψευδοκώδικα σχεδιασμένο έτσι ώστε να είναι εύληπτος από οποιονδήποτε έχει έστω και ελάχιστη εμπειρία προγραμματισμού. Η εξήγηση της λειτουργίας τους διατηρείται σε στοιχειώδες επίπεδο χωρίς να θυσιάζεται η εμβάθυνση ή η μαθηματική αυστηρότητα.
Το βιβλίο χρησιμοποιείται ευρύτατα σε πανεπιστημιακές σχολές σε ολόκληρο τον κόσμο, και έχει καθιερωθεί ως κλασική πηγή αναφοράς για τους επαγγελματίες της επιστήμης υπολογιστών. Η παρούσα έκδοση (μετάφραση της τρίτης αμερικανικής) έχει αναθεωρηθεί και ενημερωθεί σε όλη της την έκταση. Περιλαμβάνει δύο νέα κεφάλαια, με αντικείμενο τα δένδρα van Emde Boas και τους πολυνηματικούς αλγορίθμους, καθώς και σημαντικές προσθήκες στο κεφάλαιο για τις αναδρομικές σχέσεις (το οποίο πλέον τιτλοφορείται «Διαίρει-και-κυρίευε») πραγματεύεται επίσης καλύτερα τον δυναμικό προγραμματισμό και τους άπληστους αλγορίθμους και εισάγει στην ύλη των δικτύων ροής μια νέα έννοια ροής βάσει ακμών, ενώ έχουν προστεθεί πολλές καινούργιες ασκήσεις και επιπλέον προβλήματα. (Από την παρουσίαση στο οπισθόφυλλο του βιβλίου)

Περιεχόμενα

Πρόλογος
Ι Θεμελιώδεις έννοιες
1 Ο ρόλος των αλγορίθμων στις υπολογιστικές διαδικασίες
Αλγόριθμοι
Οι αλγόριθμοι ως τεχνολογία
2 Προκαταρκτικές έννοιες και παρατηρήσεις
Ενθετική ταξινόμηση
Ανάλυση αλγορίθμων
Σχεδίαση αλγορίθμων
3 Ρυθμός αύξησης συναρτήσεων
Ασυμπτωτικός συμβολισμός
Καθιερωμένοι συμβολισμοί και συνήθεις συναρτήσεις
4 Διαίρει-και-κυρίευε
Το πρόβλημα της μέγιστης υποσυστοιχίας
Ο αλγόριθμος του Strassen για πολλαπλασιασμό πινάκων
Η μέθοδος της αντικατάστασης για επίλυση αναδρομικών σχέσεων
Η μέθοδος του δένδρου αναδρομής για επίλυση αναδρομικών σχέσεων
Η μέθοδος του κυρίαρχου όρου για την επίλυση αναδρομικών σχέσεων
Απόδειξη του θεωρήματος του κυρίαρχου όρου
5 Πιθανοτική ανάλυση και τυχαιοκρατικοί αλγόριθμοι
Το πρόβλημα της πρόσληψης
Δείκτριες τυχαίες μεταβλητές
Τυχαιοκρατικοί αλγόριθμοι
Πιθανοτική ανάλυση και άλλες χρήσεις των δεικτριών τυχαίων μεταβλητών
II Ταξινόμηση και διατακτικές στατιστικές
6 Ταξινόμηση σωρού
Σωροί
Διατήρηση της ιδιότητας σωρού
Κατασκευή σωρού
Ο αλγόριθμος της ταξινόμησης σωρού
Ουρές προτεραιότητας
7 Ταχυταξινόμηση
Περιγραφή της ταχυταξινόμησης
Επίδοση της ταχυταξινόμησης
Μια τυχαιοκρατική εκδοχή της ταχυταξινόμησης
Ανάλυση της ταχυταξινόμησης
8 Ταξινόμηση σε γραμμικό χρόνο
Κάτω φράγματα για αλγορίθμους ταξινόμησης
Απαριθμητική ταξινόμηση
Αριθμοτακτική ταξινόμηση
Ταξινόμηση με δοχεία
9 Διάμεσοι και διατακτικές στατιστικές
Ελάχιστο και μέγιστο
Επιλογή σε γραμμικό αναμενόμενο χρόνο
Επιλογή σε γραμμικό χρόνο χειρότερης περίπτωσης
ΙΙΙ Δομές δεδομένων
10 Στοιχειώδεις δομές δεδομένων
Στοίβες και ουρές
Αλυσίδες
Υλοποίηση δεικτών και αντικειμένων
Αναπαράσταση έρριζων δένδρων
11 Πίνακες διασποράς
Πίνακες σταθερών διευθύνσεων
Πίνακες διασποράς
Συναρτήσεις διασποράς
Η μέθοδος των μεταβλητών διευθύνσεων
Πλήρης διασπορά
12 Δυαδικά δένδρα αναζήτησης
Τι είναι ένα δυαδικό δένδρο αναζήτησης;
Άντληση πληροφοριών από δυαδικό δένδρο αναζήτησης
Εισαγωγή και διαγραφή
Τυχαία κατασκευασμένα δυαδικά δέντρα αναζήτησης
13 Μελανέρυθρα δένδρα
Ιδιότητες των μελανέρυθρων δένδρων
Περιστροφές
Διαγραφή
14 Επαύξηση δομών δεδομένων
Δυναμικές διατακτικές στατιστικές
Μεθοδολογία της επαύξησης δομών δεδομένων
Δένδρα διαστημάτων
IV Ανώτερες τεχνικές σχεδίασης και ανάλυσης
15 Δυναμικός προγραμματισμός
Κοπή ράβδου
Πολλαπλασιασμός αλληλουχίας πινάκων
Στοιχεία δυναμικού προγραμματισμού
Μέγιστη κοινή υπακολουθία
Βέλτιστα (στατικά) δυαδικά δένδρα αναζήτησης
16 Άπληστοι αλγόριθμοι
Ένα πρόβλημα επιλογής δραστηριοτήτων
Στοιχεία της άπληστης στρατηγικής
Κώδικες Huffman
Θεωρητική θεμελίωση της άπληστης μεθοδολογίας
Ένα πρόβλημα χρονοπρογραμματισμού εργασιών ως μητροειδές
17 Αποσβεστική ανάλυση
Η σωρευτική μέθοδος
Η χρεωπιστωτική μέθοδος
Η μέθοδος του δυναμικού
Δυναμικοί πίνακες
V Δομές δεδομένων προηγμένης σχεδίασης
18 Δένδρα Β
Ορισμός των δένδρων Β
Βασικές πράξεις σε δένδρα Β
Διαγραφή κλειδιού από δένδρο Β
19 Σωροί Fibonacci
Δομή των σωρών Fibonacci
Πράξεις συγχωνεύσιμου σωρού
Μείωση κλειδιού και διαγραφή κόμβου
Φραγή του μέγιστου βαθμού
20 Δένδρα van Emde Boas
Προκαταρκτικές τεχνικές
Μια αναδρομική δομή
Το δένδρο van Emde Boas
21 Δομές δεδομένων για παράσταση ξένων συνόλων
Πράξεις ξένων συνόλων
Αναπαράσταση ξένων συνόλων μέσω συνδεδεμένων λιστών
Δάση ξένων συνόλων
Ανάλυση της ένωσης κατά τάξη με συμπίεση διαδρομής
VI Αλγόριθμοι γραφημάτων
22 Στοιχειώδεις αλγόριθμοι γραφημάτων [...]
23 Ελαφρύτατα συνδετικά δένδρα
24 Συντομότατες διαδρομές κοινής αφετηρίας
25 Συντομότατες διαδρομές πλήρους σύζευξης
26 Μέγιστη ροή
VII Επιλεγμένα θέματα
27 Πολυνηματικοί αλγόριθμοι
28 Πράξεις σε πίνακες
29 Γραμμικός προγραμματισμός
30 Πολυώνυμα και FFT
31 Αριθμοθεωρητικοί αλγόριθμοι
32 Ταύτιση συμβολοσειρών
33 Υπολογιστική γεωμετρία
34 NP-πληρότητα
35 Προσεγγιστικοί αλγόριθμοι
VIII Παράρτημα: Μαθηματικό υπόβαθρο
Αθροίσματα
Σύνολα, σχέσεις, γραφήματα και άλλα
Απαρίθμηση και πιθανότητες
Πίνακες
Γλωσσάριο
Βιβλιογραφία
Ευρετήριο