progintro @ dit

Με τις πρώτες μας εργασίες γράψαμε προγράμματα που διαχειρίζονται ακεραίους και εξοικειωθήκαμε με τις βασικές προγραμματιστικές δομές. Σε αυτήν την εργασία θα αρχίσουμε να λύνουμε πιο ρεαλιστικά προβλήματα και ταυτόχρονα θα συνεχίσουμε να χτίζουμε την εμπειρία μας με άλλους τύπους, προγράμματα και μεθόδους εισόδου και εξόδου. Συγκεκριμένα, στοχεύουμε σε εμπειρία με τα ακόλουθα:

1. Χρήση πινάκων, χαρακτήρων και συμβολοσειρών

2. Χρήση δεικτών και δυναμικής μνήμης

3. Διάβασμα/γράψιμο δεδομένων από/σε αρχεία

4. Μεταγλώττιση προγραμμάτων με πάνω από ένα αρχεία

5. Έκθεση σε προγραμματιστικές τεχνικές

Υποβολή Εργασίας.

Όπως πάντα, όλες οι υποβολές των εργασιών θα γίνουν μέσω GitHub. Προκειμένου να ξεκινήσεις, μπορείς να δεχτείς αυτήν την πρόσκληση (DIT, χ.χ.).

Προβλέποντας το Μέλλον (future - 50 Μονάδες)

Είναι δύσκολοή ίσως αδύνατονα προβλέψουμε το μέλλον. Παρ’όλες τις δυσκολίες όμως, ένα σημαντικό μέρος του πληθυσμού ασχολείται καθημερινά με τις προβλέψεις (Wikipedia, χ.χ.d). Οι προβλέψεις αυτές ποικίλουν ανάλογα με το πεδίο εφαρμογής, από τον καιρό μέχρι … καφεμαντεία και από το ποια θα είναι η επόμενη λέξη σε αυτήν την πρόταση (Wikipedia, χ.χ.f) μέχρι την ύπαρξη σωματιδίων στον χώρο της θεωρητικής φυσικής. Ανεξαρτήτως του πεδίου εφαρμογής, όλες οι προβλέψεις αξιολογούνται για την ποιότητά τους με ένα κοινό κριτήριο: το πόσο ακριβείς είναι. Όσο πιο ακριβείς οι προβλέψεις, τόσο πιο αξιόπιστη θεωρείται η πηγή τους. Aν αυτή η ακρίβεια διατηρηθεί σε βάθος χρόνου, τότε η διαδικασία πρόβλεψης μπορεί να προαχθεί σε αποδεκτό θεώρημα ή νόμο της φυσικής (YouTube, χ.χ.).

Σε αυτήν την άσκηση, θα υλοποιήσουμε έναν αλγόριθμο που χρησιμοποιείται κατεξοχήν για να κάνουμε προβλέψεις (Wikipedia, χ.χ.a), τον κινούμενο μέσο όρο (Simple Moving Average - SMA) (Wikipedia, χ.χ.g). Ο κινούμενος μέσος όρος είναι παρεμφερής με τον κανονικό μέσο όρο, με μια διαφορά: ο κινούμενος μέσος όρος απαιτεί και ένα “παράθυρο” (window), δηλαδή τον αριθμό των τιμών (μετρώντας από το τέλος) που θέλουμε να λάβουμε υπόψη μας στον υπολογισμό του μέσου όρου. Για παράδειγμα, ας υποθέσουμε ότι έχουμε αυτές τις 10 τιμές:

9  7  7  1  4  4  4  38  8  4

Ο μέσος όρος αυτών των τιμών είναι $\frac{9 + 7 + 7 + 1 + 4 + 4 + 4 + 38 + 8 + 4}{10} = 8.60$. Για να υπολογίσουμε τον κινούμενο μέσο, πρέπει να επιλέξουμε ένα παράθυρο, έστω

1. Τότε ο κινούμενος μέσος με παράθυρο 3 για αυτά τα στοιχεία λαμβάνει υπόψη του μόνο τα τελευταία 3:

και επομένως $SMA_3 = \frac{38 + 8 + 4}{3} = 16.67$. Αντίστοιχα, μπορούν να οριστούν κινούμενοι μέσοι με μικρότερα παράθυρα (π.χ., παράθυρο 1 σημαίνει μόνο το τελευταίο στοιχείο) ή μεταλύτερα παράθυρα (π.χ., παράθυρο 10 θα λάμβανε υπόψη του όλες τις τιμές παραπάνω).

Σε αυτήν την άσκηση λοιπόν, καλείστε να υλοποιήσετε ένα πρόγραμμα το οποίο θα υπολογίζει τον κινούμενο μέσο όρο για μια σειρά από δεδομένα και να τον εκτυπώνει ως πρόβλεψη. Οι τεχνικές προδιαγραφές ακολουθούν.

Τεχνικές Προδιαγραφές

• Repository Name: progintro/hw2-<YourUsername>

• C Filepath: future/src/future.c

• Το πρόγραμμά θα πρέπει να παίρνει ως κυρίως όρισμα το όνομα του αρχείου που περιέχει τα δεδομένα μας. Προαιρετικά, μπορεί να παίρνει και άλλα δύο ορίσματα προκειμένου να ορίσουμε το μέγεθος του “παραθύρου” που θέλουμε για τον κινούμενο μέσο όρο. Για παράδειγμα αν το τρέξουμε ως

  ./future data.txt –window 42

  , σημαίνει υπολόγισε τον κινούμενο μέσο όρο με παράθυρο 42 για τα δεδομένα του αρχείου data.txt. Αν δεν δοθεί παράμετρος για το μέγεθος του παραθύρου, τότε το (default) παράθυρο πρέπει να είναι μεγέθους 50. Αν το πρόγραμμα εκτελεστεί με ορίσματα που δεν ακολουθούν τις παραπάνω προδιαγραφές, πρέπει να εκτυπώσει αντίστοιχο μήνυμα όπως στα παρακάτω παραδείγματα και να επιστρέφει με κωδικό εξόδου (exit code) 1.

• Το αρχείο με τα δεδομένα θα περιέχει αριθμούς κινητής υποδιαστολής με μέχρι δύο ψηφία ακριβείας. Γενικά, δεν θα σας ζητηθεί να χρησιμοποιήσετε μεγαλύτερη ακρίβεια από double.

• Αν το παράθυρο είναι μικρότερο από 1 ή μεγαλύτερο από τον συνολικό αριθμό δεδομένων, το πρόγραμμά σας πρέπει να τερματίζει με μήνυμα σφάλματος όπως στα παραδείγματα. Το μήνυμά σας πρέπει να τυπώνεται στο stderr του προγράμματος. Το μέγεθος του παραθύρου δεν θα υπερβεί το 10¹⁸.

• Το αρχείο C που θα υποβληθεί πρέπει να μεταγλωττίζεται χωρίς ειδοποιήσεις για λάθη και με κωδικό επιστροφής (exit code) που να είναι 0. Συγκεκριμένα, το αρχείο σας πρέπει να μπορεί να μεταγλωττιστεί επιτυχώς με την ακόλουθη εντολή σε ένα από τα μηχανήματα του εργαστηρίου (linuxXY.di.uoa.gr):

  gcc -Os -Wall -Wextra -Werror -pedantic -o future future.c
  

• README Filepath: future/README.md

• Πρέπει να ολοκληρώνει την εκτέλεση μέσα σε: 1 δευτερόλεπτο.

Παραδείγματα εκτέλεσης ακολουθούν:

$ ./future
Usage: ./future <filename> [--window N (default: 50)]
$ cat values.txt
9 7 7 1 4 4 4 38 8 4
$ ./future values.txt --window 10
8.60
$ echo $?
0
$ ./future values.txt --window 3
16.67
$ ./future values.txt --window 1
4.00
$ ./future values.txt --window 0
Window too small!
$ echo $?
1
$ ./future values.txt --window 0 2> out
$ cat out
Window too small!
$ ./future values.txt --window 12
Window too large!
$ echo $?
1
$ ./future values.txt --window 1000000000000
Failed to allocate window memory

Φυσικά οι ίδιοι έλεγχοι μπορούν να γίνουν με πραγματικά δεδομένα και να δείτε αν οι προβλέψεις του προγράμματός μας είναι καλές (Το αρχείο dow_jones.txt βρίσκεται στο https://github.com/progintro/data):

$ ./future dow_jones.txt
43471.71
$ ./future dow_jones.txt --window 200
40677.19
$ ./future dow_jones.txt --window 1000
35273.61
$ wc -l dow_jones.txt
8302 dow_jones.txt
$ ./future dow_jones.txt --window 8000
15447.33

Στο αρχείο README.md πρέπει να προσθέσετε οποιεσδήποτε παρατηρήσεις σας κατά την διεκπεραίωση της άσκησης. Ο κώδικας απαιτείται να είναι καλά τεκμηριωμένος με σχόλια καθώς αυτό θα είναι μέρος της βαθμολόγησης.

Bonus (Προαιρετικό)

Πιστεύετε πως μπορείτε να φτιάξετε αλγορίθμους που προβλέπουν πως θα κινηθεί ένα οικονομικό asset καλύτερα από τον κινούμενο μέσο; Αν ναι, προσθέστε ένα easter egg option στο πρόγραμμά σας ονόματι

και θα μπείτε αυτόματα στον διαγωνισμό μας. Η αξιολόγηση θα γίνει με πραγματικά δεδομένα από χρηματιστήρια του κόσμου. Η διεπαφή θα είναι παρόμοια με παραπάνω, απλά υπολογίζετε την καλύτερή σας πρόβλεψη για την επόμενη τιμή σε μια σειρά δεδομένων:

$ ./future dow_jones.txt --compete
43455.32

Οι τρεις καλύτερες υποβολές θα λάβουν 100%, 70% και 40% έξτρα βαθμολογία σε αυτήν την άσκηση. Αν σας φάνηκε ενδιαφέρον αυτό το πρόβλημα, υπάρχουν πολλά σχετικά προβλήματα με πραγματικές εφαρμογές στον χώρο των οικονομικών (Wikipedia, χ.χ.c; Quantiacs, χ.χ.).

Το Καλύτερο GPS (jabbamaps - 50 Μονάδες)