Ανάπτυξη βιβλιοθηκών σε C/C++ για τον διαγωνισμό CodeJam

Developing C/C++ libraries for CodeJam (Αγγλική)

  1. MSc thesis
  2. Στεργιόπουλος, Βάιος
  3. Μεταπτυχιακή Εξειδίκευση στα Πληροφοριακά Συστήματα (ΠΛΣ)
  4. 22 Σεπτεμβρίου 2018 [2018-09-22]
  5. Ελληνικά
  6. 168
  7. Ρεφανίδης, Ιωάννης
  8. sports programming | competitive programming | CodeJam | Google | C | C++ | algorithmic problems contest
  9. 24
  10. 0
    • Η παρούσα Δ.Ε. έχει ως αντικείμενο τον διαγωνισμό CodeJam που διεξάγεται από την Google εδώ και αρκετά χρόνια, ως ένας διαγωνισμός “Competitive Programming” ή αλλιώς “Sports Programming”. Σκοπός του είναι, η βέλτιστη επίλυση αλγοριθμικών προβλημάτων σε πολύ περιορισμένο χρόνο. Η επίλυση των προβλημάτων απαιτεί αλγορίθμους γραμμικής ή χαμηλής πολυωνυμικής πολυπλοκότητας, καθώς το μέγεθος των δεδομένων εισόδου είναι τέτοιο ώστε, ένας απλός brute-force αλγόριθμος να αποτυγχάνει να λύσει το σύνολο του προβλήματος στον διαθέσιμο χρόνο. Κατά την εκπόνηση της Δ.Ε, μελετήθηκε σε βάθος όλη η γκάμα προβλημάτων που έχουν ζητηθεί στον εν λόγω διαγωνισμό τα έτη 2008-17. Στη συνέχεια, δημιουργήθηκε μια μεγάλη βάση δεδομένων (βιβλιοθήκη) έτοιμου κώδικα C/C++ με άξονα τις συναρτήσεις που χρησιμοποιήθηκαν για την επίλυση των προβλημάτων αυτών. Έχοντας την βιβλιοθήκη έτοιμου κώδικα C/C++ ως εργαλείο, συμμετείχα στον φετινό διαγωνισμό CodeJam 2018. Η αρχή έγινε με το Qualification Round και συνεχίστηκε στο Round 1. Η εμπειρία και τα συμπεράσματα ήταν μοναδικά και ενδιαφέροντα, γι’αυτό και καταγράφονται αναλυτικά στα επόμενα κεφάλαια.
    • This present thesis is studying the subject of the CodeJam contest, run by Google for several years as a "Competitive Programming" or "Sports Programming" competition. Its purpose is to optimally solve algorithmic problems in a very limited time. Problem solving requires algorithms of linear or low polynomial complexity, as the size of the input data is such that a simple brute-force algorithm fails to solve the whole problem in the available time. During the preparation of this thesis, the whole range of problems that were requested in this competition in the years 2008-17 was thoroughly studied. Then, a large database of C / C ++ ready-made (library) library was created, with the functions used to solve these problems. Having the C / C ++ ready-made codebook as a tool, I participated in this year's CodeJam 2018 competition. The beginning of the competition was with the Qualification Round and continued in Round 1. The experience and the conclusions were unique and interesting, so they are detailed in the following chapters.
  12. Αναφορά Δημιουργού-Μη Εμπορική Χρήση 4.0 Διεθνές