Εισαγωγή στις Δομές Δεδομένων και στους Αλγόριθμους

Πρόλογος 7

κεφάλαιο 1
Εισαγωγή, Βασικές Έννοιες Δεδοµένων και Αλγορίθµων

1.1 Τύποι Δεδομένων και Δομές Δεδομένων 17
1.1.1 Bασικές Έννοιες Δομών 18
1.2 Αλγόριθμοι 20
1.2.1 Γενικά 20
1.2.2 Προγραμματιστικές δομές 22
1.2.3 Παραδείγματα αλγορίθμων 27
1.3 Πίνακες 32
1.3.1 Πίνακας μιας διάστασης 33
1.3.2 Γραμμική Δομή λίστα στην Python (List) 36
1.3.3 Δείκτες μνήμης (pointers) στη C 40
1.3.4 Διδιάστατοι πίνακες 42
1.4 Αλφαριθμητικά (strings) 46
1.4.1 Επεξεργασία αλφαριθμητικών 47
1.4.2 Αλφαριθμητικά στην Python 48
1.5 Δομή σύνολο στην Python 51
1.6 Συναρτήσεις 53
1.6.1 Συναρτήσεις και παραδείγματα σε Python 56
1.6.2 Αλγόριθμοι εύρεσης πρώτων αριθμών
(με συναρτήσεις) 57
1.6.3 Αναδρομικοί αλγόριθμοι και συναρτήσεις 60
1.7 Αποδοτικότητα Αλγορίθμων 65
1.7.1 Συμβολισμός μεγάλου Ο 67
1.7.2 Κατηγορίες της τάξης των αλγορίθμων 68
1.7.3 Πειραματική ανάλυση του χρόνου εκτέλεσης 71
1.7.4 Επίλυση αναδρομικής σχέσης με αντικατάσταση 71
1.8 Παραγωγή Τυχαίων Αριθμών 73
1.8.1 Τυχαίοι αριθμοί στη C 74
1.8.2 Τυχαίοι αριθμοί στην Python 76
1.9 Ερωτήσεις-Ασκήσεις 80


κεφάλαιο 2
Δοµές Δεδοµένων

2.1 Γενικά - Δομές Δεδομένων 85
2.1.1 Σύνθετοι τύποι δεδομένων οριζόμενοι από τον χρήστη 86
2.1.2 Αναφορά στα πεδία δομής 87
2.1.3 Πίνακας με στοιχεία δομές 88
2.1.4 Δημιουργία σύνθετων δομών στην Python 89
2.1.5 Ένθετες δομές 92
2.1.6 Δείκτες σε δομές και δυναμικές δομές 92
2.1.7 Αναδρομικές δομές 94
2.1.8 Ενδιαφέροντα χαρακτηριστικά δομής 94
2.1.9 Αφηρημένοι Τύποι Δεδομένων (ΑΤΔ) 95
2.2 Η Στοίβα ως ΑΤΔ 97
2.2.1 Προγραμματιστική υλοποίηση στοίβας με πίνακα 98
2.2.2 Εφαρμογές στοίβας 101
2.2.3 Στοίβες στην Python και εφαρμογές 102
2.2.4 Υλοποίηση αναδρομικών αλγορίθμων με χρήση στοίβας 109
2.3 Η Ουρά ως ΑΤΔ (Quene) 111
2.3.1 Η Ουρά σε προγραμματιστικό περιβάλλον 112
2.3.2 Υλοποίηση Ουράς αναμονής 113
2.3.3 Ουρά στην Python 116
2.3.4 Εφαρμογές και παραδείγματα Ουράς 117
2.4 Συνδεδεμένη Λίστα (Linked list) 123
2.4.1 Απλά συνδεδεμένη λίστα (Simply linked list) 125
2.4.2 Δυναμική υλοποίηση συνδεδεμένης λίστας 127
2.4.3 Διατεταγμένη συνδεδεμένη λίστα 139
2.4.4 Διπλά συνδεδεμένη λίστα 143
2.4.5 Εφαρμογές συνδεδεμένης λίστας 147
2.4.6 Κυκλικά συνδεδεμένη λίστα 151
2.4.7 Συνδεδεμένη λίστα σε Python 152
2.4.8 Σύγκριση συνδεδεμένης λίστας και πίνακα 155
2.5 Ερωτήσεις-Ασκήσεις 156


κεφάλαιο 3
Αλγόριθµοι Αναζήτησης, Ταξινόµησης
και Εφαρµογές

3.1 Ταξινόμηση (Sorting) 161
3.1.1 Κριτήρια κατηγοριοποίησης αλγορίθμων ταξινόμησης 162
3.1.2 Κριτήρια επιλογής αλγορίθμου 168
3.1.3 Ταξινόμηση με εισαγωγή (insertion sort) 169
3.1.4 Ταξινόμηση επιλογής (selection sort) 174
3.1.5 Ταξινόμηση φυσαλλίδας (bubble sort) 177
3.1.6 Σύνοψη συγκριτικών απλών αλγορίθμων ταξινόμησης 180
3.1.7 Μη συγκριτικός αλγόριθμος απαριθμητικής
ταξινόμησης (counting sort) 180
3.2 Αναζήτηση (Search) 185
3.2.1 Σειριακή αναζήτηση 186
3.2.2 Σειριακή αναζήτηση με βήμα σε ταξινομημένο πίνακα 189
3.2.3 Δυαδική αναζήτηση σε ταξινομημένα στοιχεία 191
3.2.4 Αναζήτηση σε Python με χρήση ενσωματωμένων
μεθόδων 194
3.3 Αλγόριθμοι Επιλογής και Διαμέρισης 195
3.3.1 Διαμέριση πίνακα 195
3.3.2 Διμερής διαμέριση πίνακα 197
3.3.3 Τριμερής διαμέριση 201
3.3.4 Διάμεσος πίνακα με Επιλογή 208
3.3.5 Το πρόβλημα της επιλογής (selection problem) 212
3.3.6 Συγχώνευση γραμμικών δομών 214
3.3.7 Συγχώνευση ταξινομημένων λιστών σε Python 220
3.4 Ερωτήσεις-Ασκήσεις 221

κεφάλαιο 4
Δενδρικές Δοµές

4.1 Δένδρα Γενικά 227
4.1.1 Βασικοί ορισμοί και ιδιότητες 228
4.1.2 Είδη και δομές δένδρων 233
4.2 Δυαδικά Δένδρα (Binary trees) 233
4.2.1 Μαθηματικές ιδιότητες και προτάσεις για δυαδικά
δένδρα 234
4.2.2 Αναπαράσταση δυαδικού δένδρου 235
4.2.3 Κατασκευή δυαδικού δένδρου και πράξεις 236
4.2.4 Δυαδικά δένδρα αναζήτησης (ΔΔΑ) - Binary search
tree (BST) 240
4.2.5 Διάσχιση ή διέλευση ή επίσκεψη δυαδικού δένδρου 243
4.2.6 Προβλήματα και εφαρμογές 249
4.2.7 Βασικές πράξεις σε ΔΔΑ 252
4.2.8 Αυξητικά ΔΔΑ (Augmented BST) 263
4.2.9 Δυαδικό δένδρο αναζήτησης (ΔΔΑ) σε Python 266
4.3 AVL Δένδρου 268
4.3.1 Υπολογισμός τάξης του ύψους για AVL δένδρο 271
4.3.2 Περιστροφές AVL 272
4.3.3 Δομή κόμβου και υπολογισμός παράγοντα ισορροπίας 273
4.3.4 Κατασκευή δένδρου AVL από ταξινομημένη ακολουθία 274
4.4 Ουρά Προτεραιότητας και Σωρός (heap) 277
4.4.1 Δυαδικός σωρός 279
4.4.2 Υλοποίηση δυαδικού σωρού 282
4.4.3 Αλγόριθμος ταξινόμησης σωρού (Heapsort) 288
4.4.4 Εφαρμογή: Εύρεση της διαμέσου μιας σειράς
στοιχείων με heap 290
4.5 Β-Δένδρα (Δένδρα Αναζήτησης Πολλαπλής Διακλάδωσης) 293
4.5.1 Εξωτερική αναζήτηση και ευρετήρια 293
4.5.2 Ορισμοί και κατηγορίες Β-Δένδρων 296
4.6 Τrie Tree 300
4.7 Ερυθρόμαυρα Δένδρα (Red-Black trees) 303
4.8 Διωνυμικές Δομές 308
4.8.1 Διωνυμικά δένδρα 308
4.8.2 Διωνυμικοί Σωροί – ουρές (ΔΣ) 311
4.8.3 Πράξεις σε διωνυμικούς σωρούς 314
4.8.4 Σωροί Fibonacci 320
4.9 Ερωτήσεις-Ασκήσεις 323


κεφάλαιο 5
Σχεδίαση και Ανάλυση Αλγορίθµων

Αλγόριθµοι 329
5.1 Γενικά Χαρακτηριστικά & Κατηγορίες Αλγορίθμων 329
5.1.1 Κατηγορίες αλγορίθμων και ορολογία 330
5.2 Ανάλυση Αλγορίθμων 343
5.2.1 Συμβολισμοί Θ και Ω 343
5.2.2 Το κεντρικό θεώρημα ή θεώρημα κυριαρχίας 345
5.2.3 Χρονική πολυπλοκότητα και είσοδος δεδομένων
προβλήματος 349
5.2.4 Παραδείγματα απαιτητικών προβλημάτων 355
5.2.5 Η κλάση προβλημάτων P 356
5.2.6 Η κλάση προβλημάτων NP 356
5.2.7 Η κλάση των NP-hard και NP-complete προβλημάτων 357
5.3 Σχεδίαση Αλγορίθμων 359
5.3.1 Διαίρει και κυρίευε (ή βασίλευε) 359
5.3.2 Ταξινόμηση με συγχώνευση 361
5.3.3 Γρήγορη ταξινόμηση (Quick Sort) 364
5.3.4 Δυναμικός προγραμματισμός 369
5.3.5 Άπληστοι αλγόριθμοι 385
5.3.6 Παράδειγμα ευρηματικού αλγορίθμου 387
5.4 Αλγόριθμοι Κατακερματισμού 389
5.4.1 Συνάρτηση κατακερματισμού 392
5.5 Δομή Λεξικό (στην Python) 407
5.6 Ασκήσεις 410


κεφάλαιο 6
Θεωρία και Αλγόριθµοι Γράφων

Γενικά 415
6.1 Ορισμοί και Ιδιότητες Γράφων 419
6.1.1 Τοπολογική ταξινόμηση (Topological sorting) 437
6.2 Γράφοι Euler & Hamilton 440
6.2.1 Ο κύκλος Euler 440
6.2.2 Γράφος Hamilton 442
6.3 Αναπαράσταση Γράφων 447
6.3.1 Πίνακας γειτονικών κόμβων ή πίνακας συνδέσεων 447
6.3.2 Λίστα γειτονικών κόμβων ή λίστα γειτνίασης 452
6.4 Ελάχιστα Συνδετικά Δένδρα Κάλυψης (minimal spanning trees) 459
6.4.1 Δένδρα επικάλυψης γράφου (συνδετικά δένδρα) 460
6.4.2 Ελάχιστα δένδρα επικάλυψης (MST) 460
6.5 Ελάχιστο Μονοπάτι (Shortest Path) ή Ελαφρύτατες Απλές
Διαδρομές 468
6.5.1 Βασικοί αλγόριθμοι για ελάχιστα μονοπάτια 470
6.5.2 Πίνακας αποστάσεων για κάθε ζεύγος κόμβων
γράφου (Floyd-Warshall) 476
6.5.3 Mέγιστη διαδρομή σε γράφο (Longest path) 482
6.6 Διάσχιση ή Επίσκεψη Γράφου 484
6.6.1 Αναζήτηση με προτεραιότητα βάθους (DFS) 485
6.6.2 Επίσκεψη ή αναζήτηση κατά πλάτος (BFS) 493
6.7 Μέγιστη Ροή (Max flow) 499
6.8 Ενδιαφέροντα Προβλήματα Γράφων 507
6.8.1 Ταίριασμα (matching) 507
6.8.2 Ανεξάρτητο Σύνολο 509
6.8.3 Χρωματισμός κορυφών γράφου 510
6.8.4 Κατηγοριοποίηση βασικών προβλημάτων γράφων 512
6.9 Ασκήσεις-Ερωτήσεις 513

Βιβλιογραφία 517
Συµβολισµοί 519