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

Κωνσταντίνος Τσίχλας
Ιωάννης Μανωλόπουλος
Αναστάσιος Γούναρης

ISBN: 978-960-603-465-7

Το παρόν έργο αδειοδοτείται υπό τους όρους της άδειας Creative Commons Αναφορά Δημιουργού - Μη Εμπορική Χρήση - Όχι Παράγωγα Έργα 3.0. Για να δείτε ένα αντίγραφο της άδειας αυτής επισκεφτείτε τον ιστότοπο https://creativecommons.org/licenses/by-nc-nd/3.0/gr/

Περιεχόμενα

Πίνακας Συντομεύσεων - Ακρωνύμια
Πρόλογος
1 Εισαγωγή
2 Θεωρητικό Υπόβαθρο
3 Γεννήτριες Συναρτήσεις
4 Βασικοί Αλγόριθμοι
5 Αλγόριθμοι Χαμηλού Επιπέδου
6 Αλγοριθμικές Τεχνικές
7 Αλγόριθμοι Αναζήτησης
8 Αλγόριθμοι Ταξινόμησης
9 Επιμερισμένη Ανάλυση
10 Βασικά Στοιχεία Πολυπλοκότητας
11 Αλγόριθμοι Γραφημάτων
12 Αλγόριθμοι Συμβολοσειρών
13 Τυχαίοι Αλγόριθμοι
Βιβλιογραφία
Ευρετήριο

Κατάλογος Σχημάτων

1.1 Πολλαπλασιασμός αλά ρωσικά.
1.2 Ταξινόμηση Επιλογής για ένα Πίνακα Α…
1.3 Κόσκινο του Ερατοσθένη για $n=80$
1.4 Το πρόβλημα του μαγικού τετραγώνου.
2.1 Γραφική αναπαράσταση του $\rm O$ .
2.2 Γραφική αναπαράσταση του $\Omega$ .
2.3 Γραφική αναπαράσταση του $\Theta$ .
2.4 Φάσμα υπολογιστικής πολυπλοκότητας
2.5 Δένδρο Αναδρομής
2.6 Το πρόβλημα με τα πλακάκια.
2.7 Παράδειγμα λύσης Άσκησης 27 όπου $k=3$ .
2.8 Το πρόβλημα με τα μαύρα τετράγωνα.…
4.1 Σειρά κλήσεων για την fib1(4).
4.2 Puzzle των πύργων του Ανόι για…
4.3 Σειρά κλήσεων για την power3(a,5).
4.4 Κλήσεις για τον υπολογισμό του comb1(4,2).
4.5 Γραμμικό πρόβλημα πύργων Ανόι για τρεις…
5.1 Πρόσθεση αριθμών σε δεκαδικό και δυαδικό…
5.2 Αφαίρεση αριθμών σε δεκαδικό και δυαδικό…
5.3 Πολλαπλασιασμός αριθμών σε δυαδικό σύστημα.
5.4 Διαίρεση αριθμών σε δυαδικό σύστημα.
5.5 Το πρόβλημα του πίνακα matrix.
6.1 Το εγγύτερο ζεύγος είναι αυτό μέσα…
6.2 Τα δύο σύνολα $S_{1}$ και $S_{2}$ κατά…
6.3 Προσοχή ότι το σχήμα (β) δεν…
6.4 Φαίνονται οι αναδρομικές κλήσεις για τον…
6.5 Ο χάρτης της Ελλάδας και ένας…
6.6 Ένα μέρος του δένδρου καταστάσεων -…
6.7 Η αρχή του δένδρου καταστάσεων για…
6.8 Λύση του προβλήματος της τοποθέτησης των…
6.9 Παράδειγμα επίλυσης του προβλήματος των 4…
6.10 Λύση με διακλάδωση και περιορισμό.
6.11 Παράδειγμα γράφου.
6.12 Το πρόβλημα του τριγώνου.
7.1 Αλγόριθμος σειριακής αναζήτησης.
7.2 Αλγόριθμος σειριακής αναζήτησης για ταξινομημένους πίνακες.…
7.3 Επαναληπτικός αλγόριθμος δυαδικής αναζήτησης. Η $\div$ αναπαριστά την ακέραια…
7.4 Αναδρομικός αλγόριθμος δυαδικής αναζήτησης.
7.5 Παράδειγμα Δυαδικής Αναζήτησης για το στοιχείο…
7.6 Απλός αλγόριθμος για αναζήτηση παρεμβολής.
7.7 Αναζήτηση παρεμβολής.
7.8 Aλγόριθμος αναζήτησης δυαδικής παρεμβολής.
7.9 Αναζήτηση δυαδικής παρεμβολής.
7.10 Βελτίωση με αναζήτηση άλματος.
7.11 Ομαλή κατανομή.
7.12 Η διαδικασία ένθεσης στον γραμμικό κατακερματισμό.…
7.13 Κατακερματισμός με γραμμική αναζήτηση.
7.14 Η διαδικασία εύρεσης ενός στοιχείου $k e y$ στον γραμμικό κατακερματισμό.…
7.15 Τετραγωνικός κατακερματισμός.
7.16 Η διαδικασία ένθεσης ενός στοιχείου $k e y$ στον τετραγωνικό κατακερματισμό.…
7.17 Διπλός κατακερματισμός.
7.18 Η διαδικασία ένθεσης ενός στοιχείου $k e y$ στον διπλό κατακερματισμό.…
7.19 Κατακερματισμός με αλυσίδες.
7.20 Η διαδικασία εύρεσης ενός στοιχείου $k e y$ στον κατακερματισμό με…
8.1 Παράδειγμα Ταξινόμησης με Εισαγωγή
8.2 (i) Ευσταθής και (ii) Ασταθής Ταξινόμηση…
8.3 Διαδικασία διαμερισμού.
8.4 Κλήσεις για τον υπολογισμό του ελάχιστου…
8.5 Διαίρεση σε πεντάδες. Τα στοιχεία του…
8.6 Σειρά κλήσεων της merge_sort.
8.7 Σειρά κλήσεων της merge.
8.8 Ταξινόμηση με μειούμενες αυξήσεις.
8.9 Ταξινόμηση με μειούμενες αυξήσεις.
8.10 Δένδρο αποφάσεων.
8.11 Ταξινόμηση με κάδους.
9.1 Οι τρεις πράξεις που υποστηρίζονται από…
9.2 Οι πράξεις επέκτασης και σύντμησης σε…
9.3 Εφαρμογή εξάρθρωσης στον κόμβο $x$ . i) Zig:…
9.4 Παραδείγματα εφαρμογής εξάρθρωσης. i) Έξάρθρωση στον κόμβο…
9.5 Γραμμική Λίστα: $access\left(3\right)$ με κόστος 3…
9.6 Γραμμική Λίστα: Αντιμετάθεση των στοιχείων 3…
9.7 Παραδείγματα αναστροφών - $\left(28,34\right),\left(28,2\right),\left(34,2\right),\left(6,13\right)$
9.8 Παράδειγμα δημιουργίας αναστροφής μετά από αντιμετάθεση…
9.9 Οι $L_{i-1}$ και $L_{i-1}^{*}$ αμέσως…
10.1 Ο αλγόριθμος για το πρόβλημα $\Pi_{1}$ μέσω αναγωγής στο…
10.2 Γράφος για την Άσκηση 4.
11.1 Παραδείγματα γράφων.
11.2 Υπογράφοι των γράφων $G_{1}$ και $G_{2}$ .
11.3 Πίνακες διπλανών κορυφών.
11.4 Λίστες διπλανών κορυφών.
11.5 Πολλαπλή λίστα διπλανών κορυφών.
11.6 Μη κατευθυνόμενος γράφος και λίστα διπλανών…
11.7 Dag και αντίστοιχο δένδρο.
11.8 Εναλλακτικές γραμμικές διατάξεις.
12.1 Παράδειγμα εκτέλεσης του αλγορίθμου ταιριάσματος συμβολοσειρών…
12.2 Παράδειγμα εκτέλεσης του αλγορίθμου ταιριάσματος συμβολοσειρών…
13.1 Διαγραφή κόμβων από δένδρο αναζήτησης.
13.2 Μία απλή αριστερή περιστροφή.
13.3 Διαγραφή (και αντιστρόφως εισαγωγή) ενός στοιχείου…
13.4 Συνδεδεμένες λίστες με επιπλέον δείκτες.
13.5 Εισαγωγή σε λίστα παράλειψης.
13.6 Πλήρες τριαδικό δένδρο με $n=9$ .
13.7 Ένα τριαδικό δέντρο πλειοψηφίας με βάθος…

Κατάλογος Πινάκων

1.1 Κοστολόγηση ταξινόμησης επιλογής
1.2 Κοστολόγηση ταξινόμησης εισαγωγής
2.1 Συσχέτιση ασυμπτωτικών συμβολισμών.
2.2 Σύγκριση πολυπλοκότητας αλγορίθμων
2.3 Κατηγοριοποίηση αναδρομικών εξισώσεων.
3.1 Γεννήτριες συναρτήσεις ευρείας χρήσης
4.1 Υπολογισμός δύναμης
6.1 Μέγιστο άθροισμα υποακολουθίας.
6.2 Μέγιστο άθροισμα υποακολουθίας (Διαίρει και Βασίλευε).…
6.3 Εξεταζόμενες ακμές, κόστος, και ενέργεια
6.4 Τιμές συνάρτησης J για τον υπολογισμό…
6.5 Το πρόβλημα με τα 9 κέρματα.…
7.1 Πιθανότητα σύγκρουσης σε πίνακα 1000 θέσεων…
8.1 Ταξινόμηση με μέτρημα (αρχικός πίνακας).
8.2 Ταξινόμηση με μέτρημα (βοηθητικός πίνακας).
8.3 Ταξινόμηση με βάση τη ρίζα.
8.4 Το πρόβλημα της ευθείας εισαγωγής δύο…
12.1 Πίνακας μετατοπίσεων για το αλφάβητο $\{A,G,C,T\}$ και το πρότυπο…
13.1 Διατεταγμένη λίστα.
13.2 Εκτελούμενες ενέργειες σε λίστα παράλειψης.