Ένα ξεχωριστό ανάγνωσμα που απευθύνεται σε μαθητές που θέλουν να συμμετάσχουν στον Πανελλήνιο Διαγωνισμό Πληροφορικής αλλά και άλλους διαγωνισμούς αλγορίθμων (όπως TopCoder, CodeChef, Google Code Jam, κ.α.) είναι το «Αλγοριθμιάδα», του Χρήστου Μαλλιαράκη.
Τι θα βρείτε σε αυτό το βιβλίο
Ο καθηγητής -ορθά πράττοντας- ξεκινάει την «Αλγοριθμιάδα» με μια εισαγωγή στη γλώσσα προγραμματισμού C++, μιας και αυτή χρησιμοποιείται κατά κόρων στους αλγοριθμικούς διαγωνισμούς πληροφορικής. Παρουσιάζει τις βασικές δομές του προγραμματισμού (των προγραμμάτων υπολογιστών), τη δομή Αν, τη δομή επανάληψης, τη δομή επιλογής και τις μεταβλητές. Ξεκινάει δηλαδή από την αρχή-αρχή απευθυνόμενος σε όσους έρχονται για πρώτη φορά σε επαφή με αυτό το πεδίο της επιστήμης.
Στη συνέχεια παρουσιάζει πιο προχωρημένα θέματα της γλώσσας C++, όπως πίνακες, υπορουτίνες (συναρτήσεις), θέματα εισόδου και εξόδου αρχείων δεδομένων, καθώς και δείκτες που είναι οι βάσεις για πιο σύνθετες δομές δεδομένων και για λήψη των δεδομένων εισόδου και εξαγωγή των αποτελεσμάτων.
Κατόπιν παρουσιάζει διάφορες πτυχές της θεωρίας αλγορίθμων, όπως ασυμπτωτική πολυπλοκότητα, ουρές και στοίβες, αλγόριθμους αναζήτησης, γράφοι (διαγράμματα συνδεσιμότητας). Οι πτυχές αυτές αναπτύσσονται σε θέματα αυξανόμενου επιπέδου πολυπλοκότητας σε πιο σύνθετες έννοιες, με την ανάπτυξη των θεμάτων να περιλαμβάνει όλο και πιο προχωρημένες έννοιες.
Προχωρώντας, και με βάση τις πρώτες πτυχές, αναπτύσσονται όλο και πιο προχωρημένα θέματα αλγορίθμων όπως άπληστοι αλγόριθμοι, δυναμικός προγραμματισμός, θεωρία παιγνίων, θεωρία αριθμών και πιθανοτική ανάλυση πολυπλοκότητας. Καθώς και διάφορες ακόμα πιο πολύ προχωρημένες δομές δεδομένων που σχετίζονται με αυτά τα θέματα.
Αξιοσημείωτο είναι το γεγονός πως για κάθε θέμα που πραγματεύεται ο Χρήστος Μαλλιαράκης στην «Αλγοριθμιάδα» παρουσιάζει παράλληλα και τα θεμελιώδη (βασικά) θεωρήματα που υποστηρίζουν την ανάλυση που κάνει. Το βιβλίο είναι χωρισμένο στις παρακάτω τρεις ενότητες:
Ενότητα 1: Σε αυτή την ενότητα παρουσιάζονται οι βασικές δομές του προγραμματισμού και πως αυτές γράφονται (αναπαρίστανται) στην γλώσσα C++
Ενότητα 2: Στην συνέχεια, ο συγγραφέας κάνει μια ευρεία εισαγωγή στην ανάλυση και σχεδίαση ασυμπτωτικά βέλτιστων αλγορίθμων, καθώς και στις δομές δεδομένων που αυτοί χρησιμοποιούν.
Ενότητα 3: Τέλος, παραθέτει τα θέματα της πρώτης, δεύτερης και τρίτης φάσης του πανελληνίου διαγωνισμού πληροφορικής (http://www.pdp.gr) τα τελευταία έτη, ήτοι από το 2006-7 έως και το 2016-17.
Για να αγοράσετε το «Αλγοριθμιάδα», του Χρήστου Μαλλιαράκη, κάντε κλικ εδώ!
Πίνακας περιεχομένων βιβλίου
Περιεχόμενα
Εισαγωγή
Α’ ΜΕΡΟΣ
Βασικές Δομές και Έννοιες Προγραμματισμού
Κεφάλαιο 1 Δομή Ακολουθίας και Μεταβλητές
Κεφάλαιο 2 Δομή επιλογής
Κεφάλαιο 3 Δομή επανάληψης
Κεφάλαιο 4 Πίνακες
Κεφάλαιο 5 Συναρτήσεις
Κεφάλαιο 6 Αρχεία
Κεφάλαιο 7 Δείκτες
Β΄ ΜΕΡΟΣ
Προχωρημένες Δομές Προγραμματισμού, Τεχνικές Επίλυσης Προβλημάτων και Αλγόριθμοι
Κεφάλαιο 8 Πολυπλοκότητα
8.1 Μετρώντας εντολές
8.2 Ανάλυση χειρότερης περίπτωσης
8.3. Ασυμπτωτική συμπεριφορά
8.4 Πολυπλοκότητα
8.5 Συμβολισμός Big-O
8.6 Λογάριθμοι
8.7 Αναδρομική πολυπλοκότητα
8.8 Λογαριθμική πολυπλοκότητα
8.9 Βέλτιστη ταξινόμηση
Κεφάλαιο 9 Δομές Δεδομένων
9.1 Δυναμικοί πίνακες
9.2 Map structures
9.3 Δομή συνόλων
9.4 Iteators
9.5 Άλλες δομές
Ουρές (Queues)
Ουρές προτεραιότητας (priority queues)
Στοίβες (Stacks)
Bitsets
Κεφάλαιο 10 Αναζήτηση
10.1 Υποσύνολα
10.2 Αντιμεταθέσεις
10.3 Backtracking
Κεφάλαιο 11 Άπληστοι Αλγόριθμοι
11.1 Χρονοδρομολόγηση (scheduling)
Κεφάλαιο 12 Δυναμικός Προγραμματισμός
12.1 πρόβλημα νομίσματος
12.2 Η αναδρομή ως βέλτιστη λύση
Κεφάλαιο 13 Θεωρία Γράφων
13.1 Ορολογία γράφων
13.2 Αναπαραστάσεις γράφων σε αλγορίθμους
Κεφάλαιο 14 Διάσχιση Γράφων
14.1 Αναζήτηση πρώτα κατά βάθος (Depth-first search)
14.2 Αναζήτηση πρώτα κατά πλάτος (Breadth-first search)
14.3 Εφαρμογές
Κεφάλαιο 15 Δέντρα
15.1 Διάσχιση δέντρου
15.2 Διάμετρος
15.3 Δυαδικά δέντρα
Κεφάλαιο 16 Θεωρία Αριθμών
16.1 Πίνακας συμβόλων
16.2 Υπόλοιπο
Πράξεις με υπόλοιπο
16.3 Πρώτοι αριθμοί
Ύπαρξη πρώτου διαιρέτη μικρότερου της ρίζας
Το μικρό θεώρημα του Fermat
16.4 Ο αλγόριθμος του Ευκλείδη
Επέκταση του αλγορίθμου του Ευκλείδη
Λύση Διοφαντικών εξισώσεων
Εύρεση πολλαπλασιαστικού αντιστρόφου
16.5 Κόσκινα
Κόσκινο του Ερατοσθένη
Κόσκινο πολλαπλασιαστικών αντιστρόφων
16.6 Γενικά
Επιπλέον για τους πρώτους αριθμούς
Επιπλέον κόσκινα
Αποδείξεις
Κεφάλαιο 17 Πιθανοτικοί Αλγόριθμοι
17.1 Quicksort
17.2 Merge heap
17.3 Καρτεσιανό δέντρο
17.4 Treap
17.5 Χρήσιμα μαθηματικά
17.6 Προβλήματα με λύσεις
Monte (BOSPRE 2016, παραλλαγή)
Quickselect
Κεφάλαιο 18 Θεωρία Παιγνίων
18.1 Καταστάσεις παιχνιδιού
Κεφάλαιο 19 Το πρόβλημα με το κολιέ
19.1 Διατύπωση του προβλήματος
19.2 Μερικές σκέψεις για τη λύση του προβλήματος
19.3 Ξεκινώντας τη λύση: αναπαριστώντας το πρόβλημα
19.4 Πολυπλοκότητα αλγορίθμου
Γ’ ΜΕΡΟΣ
Θέματα προηγούμενων διαγωνισμών Πληροφορικής
19ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Α’ Φάση: Πατρόκλεια Τείχη
Β’ Φάση: Κυκλαδικές Διαδρομές
Γ’ Φάση: 2ο θέμα – Μπάλες Υάλου
Γ’ Φάση: 3ο θέμα – Θέα Στη Θάλασσα
20ός Πανελλήνιος Διαγωνισμός Πληροφορικής
Α’ Φάση: Φρυκτωρίες
Β΄ Φάση: Σαμποτάζ στον Γοργοπόταμο
Γ’ Φάση: 1ο Θέμα – Data Blocks
Γ’ Φάση: 2ο Θέμα – Sonar
21ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Α’ Φάση: Το Ψηφιδωτό του Μεγάλου Αλεξάνδρου
Β’ Φάση: Χαλκιδικό Αλφάβητο
Β’ Φάση: Αναχαιτίσεις στο Αιγαίο
Γ’ Φάση: 1ο Θέμα – 1o HydroloGIS
Γ’ Φάση: 2ο Θέμα – Aegean
Γ’ Φάση: 3ο Θέμα – CPU
22ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Α’ Φάση: Αυτοκίνητα Υδρογόνου
Β’ Φάση: Οι φωτιές στην Ελλάδα
Β’ Φάση: Πρόβλημα στον “Έξυπνο” Διαδραστικό Πίνακα
Γ’ Φάση: 1ο Θέμα – Lines man
Γ’ Φάση: 2ο Θέμα – Servers
Γ’ Φάση: 3ο Θέμα – Get out!
23ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Α’ Φάση: Μεγιστοποίηση Κέρδους
Β’ Φάση: Εταιρική Ιεραρχία
Β’ Φάση: Χιονοδρομίες στα “Τρία – Πέντε Πηγάδια”
Γ’ Φάση: 1ο Θέμα – prevdiv
Γ’ Φάση: 2ο Θέμα – fishboats
Γ’ Φάση: 3ο Θέμα – anneal
24ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Α’ Φάση: Υπολογιστικά Νέφη
Β’ Φάση: Τελεστικοί Ενισχυτές
Γ’ Φάση: Ραδιοαστέρες (Pulsars)
25ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Α’ Φάση: Αναζητώντας Εξωγήινη Νοημοσύνη
Β’ Φάση: Ανασύσταση της Βοιβηίδος λίμνης
Β’ Φάση: Οι μυστικοί αριθμοί
Γ’ Φάση: 1ο Θέμα – Τρίγωνο
Γ’ Φάση: 2ο Θέμα – Ήχοι και σιωπές
Γ’ Φάση: 3ο Θέμα – Τηλεπικοινωνιακά κόστη
26ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Α’ Φάση: Δομές Κοινωνικής Αλληλεγγύης
Β’ Φάση: Ρυθμική Γυμναστική
Β’ Φάση: Ηλιακός Άνεμος
Γ’ Φάση: 1ο Θέμα – Άθροισμα ζευγών
Γ’ Φάση: 2ο Θέμα – Επισκευή δρόμου
Γ’ Φάση: 3ο Θέμα – μετατροπή αριθμών
27ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Α’ Φάση: Το κυλικείο του σχολείου
Β’ Φάση: Άθροισμα τετραγώνων
Β’ Φάση: Η μοιρασιά
Γ’ Φάση: 1ο Θέμα – Παρέες αριθμών
Γ’ Φάση: 2ο Θέμα – Εφημερίδες
Γ’ Φάση: 3ο Θέμα – Σουπερμάρκετ
28ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Α’ Φάση: Υπερυπολογιστής ARIS
Β’ Φάση: Χαρταετός
Β’ Φάση: Μονοδιάστατο Scrabble
Γ’ Φάση: 1ο Θέμα – Εκδρομή για σκι
Γ’ Φάση: 2ο Θέμα – Δίκτυο σχολείων
Γ’ Φάση: 3ο Θέμα – Star Wars
29ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Α’ Φάση: Πανελλήνιο Σχολικό Δίκτυο
Β’ Φάση: Πολύχρωμη κορδέλα
Β’ Φάση: Κάρτες Απεριορίστων Πτήσεων
Γ’ Φάση: 1ο Θέμα – Ακολουθίες DNA
Γ’ Φάση: 2ο Θέμα – Οδικό δίκτυο
Γ’ Φάση: 3ο Θέμα – Πάω διακοπές
Βιβλιογραφία
Για να αγοράσετε το «Αλγοριθμιάδα», του Χρήστου Μαλλιαράκη, κάντε κλικ εδώ!
Κριτική και εντυπώσεις
Όπως ήδη αναφέραμε, η «Αλγοριθμιάδα» του Χρήστου Μαλλιαράκη, απευθύνεται κυρίως σε μαθητές που θέλουν να συμμετάσχουν στον Πανελλήνιο Διαγωνισμό Πληροφορικής, στις Ολυμπιάδες Πληροφορικής IOI, BOI, JBOI, EJOI αλλά και στους Διεθνείς Διαγωνισμούς Google Code Jam & ACM-ICPC.
Η στοιχειοθέτηση της “Αλγοριθμιάδας” είναι ιδανική ώστε να μην είναι κουραστική η ανάγνωσή του, αντιθέτως να είναι ευχάριστη. Έχοντας τον απαραίτητο “αέρα” γίνεται πιο κατανοητό το κείμενο αλλά και δεν φαίνεται βαρύ και δύσκολο. Έχει επιλεγεί δε η πολύχρωμη εκτύπωση -εύγε στις εκδόσεις Ελληνοεκδοτική- τόσο για αισθητικούς όσο και για πρακτικούς λόγους!
Αξίζει να σημειώσουμε ότι τα θέματα παλιών διαγωνισμών πληροφορικής -που παρουσιάζονται στο τρίτο μέρος του βιβλίου- συνοδεύονται από τις βέλτιστες λύσεις που έδωσαν μαθητές οι οποίοι συμμετείχαν στον διαγωνισμό.
Ερχόμενο να καλύψει έναν χώρο στον οποίο υπάρχει έλλειψη βοηθητικών βιβλίων αλλά μεγάλο ενδιαφέρον από πλευράς των μαθητών, η «Αλγοριθμιάδα» του Χρήστου Μαλλιαράκη θα κάνει πολλούς μαθητές χαρούμενους μιας και διαβάζοντάς το θα τους βοηθήσει ουσιαστικά!
Αν είστε μαθητής που θα θέλατε να μάθετε πως να προγραμματίζετε αλλά και να έχετε εικόνα για το πως είναι τα θέματα σε διαγωνισμούς πληροφορικής ή αν έχετε στο περιβάλλον σας ένα ανερχόμενο αστέρι της πληροφορικής, τότε σπεύσατε στο πιο κοντινό βιβλιοπωλείο –ή δώστε την ηλεκτρονική σας παραγγελία εδώ– και αποκτήστε το!
Οπισθόφυλλο:
Με αυτό το βιβλίο ως οδηγό θα μπορέσετε να αποκτήσετε τις απαραίτητες γνώσεις για την εκμάθηση του προγραμματισμού, να εισαχθείτε στη λογική βασικών αλγορίθμων, να γνωρίσετε ορισμένες πιο πολύπλοκες έννοιες και να τις κατανοήσετε.
Αφού μάθετε τα βασικά βήματα του προγραμματισμού και εξοικειωθείτε με τα πιο σύνθετα, σας δίνεται η δυνατότητα να δοκιμαστείτε σε προβλήματα που ανέδειξαν τους Ολυμπιονίκες Πληροφορικής, αυτούς που στελέχωσαν την Εθνική Ομάδα Πληροφορικής και έλαβαν μεγάλες διεθνείς διακρίσεις.
Στο χέρι σας είναι να διακριθείτε, ακολουθώντας το “ταξίδι” των Ολυμπιονικών, όπως αυτό χαρτογραφείται αναλυτικά σε κάθε κεφάλαιο του βιβλίου.
Στο βιβλίο παρουσιάζονται:
Στο Α’ Μέρος (Αρχάριοι):
Η δομή ακολουθίας, η δομή επιλογής, η δομής επανάληψης, οι πίνακες, οι συναρτήσεις, τα αρχεία και οι δείκτες.
Στο Β’ Μέρος (Προχωρημένοι):
Πολυπλοκότητα, Ασυμπτωτική συμπεριφορά αλγορίθμων, αναδρομική και λογαριθμική πολυπλοκότητα, δυναμικοί πίνακες, δομή συνόλων, στοίβες, ουρές, αναζήτηση δεδομένων, άπληστοι αλγόριθμοι, δυναμικός προγραμματισμός, γράφοι, μοντελοποίηση και διάσχιση των γράφων, δέντρα, θεωρία αριθμών, πιθανοτικοί αλγόριθμοι (Quicksort, Merge Heap, Treap και καρτεσιανά δέντρα), θεωρία παιγνίων, στρατηγικές επίλυσης προβλημάτων στο πρότυπο Διεθνών Διαγωνισμών Πληροφορικής.
Στο Γ’ Μέρος:
Παλαιά θέματα του Πανελλήνιου Διαγωνισμού Πληροφορικής και οι λύσεις τους.
Για να αγοράσετε το «Αλγοριθμιάδα», του Χρήστου Μαλλιαράκη, κάντε κλικ εδώ!
Ταυτότητα βιβλίου
Τίτλος βιβλίου
Αλγοριθμιάδα
Μαθαίνω_Προγραμματισμό
Συγγραφέας
Χρήστος Μαλλιαράκης
Εκδοτικός οίκος
Εκδόσεις Ελληνοεκδοτική
Ημερομηνία έκδοσης
Ιούλιος 2018
Αριθμός σελίδων
598
ISBN
978-960-563-202-1
Συντάκτης άρθρου
Α. Α.