Εισαγωγή στην Πληροφορική

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Εισαγωγή στο μάθημα και ιστορική αναδρομή

Καλώς ήρθατε

Εισαγωγή στην Πληροφορική

Τι περιλαμβάνει το μάθημα

  1. Εισαγωγή στο μάθημα και ιστορική αναδρομή
  2. Παράσταση δεδομένων
  3. Δομικά στοιχεία υπολογιστών
  4. Βασικές αρχιτεκτονικές
  5. Προγραμματισμός σε επίπεδο μηχανής
  6. Λειτουργικά συστήματα
  7. Αλγόριθμοι, δεδομένα και διαδικασίες
  8. Γλώσσες προγραμματισμού
  9. Διερμηνευτές και μεταγλωττιστές
  10. Τεχνολογία λογισμικού
  11. Προγραμματιστικά παραδείγματα
  12. Στοιχεία θεωρητικής πληροφορικής
  13. Βάσεις δεδομένων
  14. Γραφικά με υπολογιστή
  15. Εφαρμογές γραφείου
  16. Επεξεργασία δεδομένων
  17. Επιστημονολογική θεώρηση
  18. Εισαγωγή στον προγραμματισμό
  19. Υπολογισμοί με σταθερές
  20. Μεταβλητές και εκχωρήσεις
  21. Επιλογές και επαναλήψεις
  22. Διαδικασίες και συναρτήσεις
  23. Οργάνωση προγραμμάτων
  24. Λάθη και τεχνικές αποσφαλμάτωσης
  25. Ανασκόπηση - επανάληψη

Τρόπος διδασκαλίας

Οι σημειώσεις

Το σημερινό μάθημα

Πρόδρομοι της πληροφορικής

Η βάση της διαφορικής μηχανής

Υπολογισμοί με πολυώνυμα

f(x) = x^2

1
     3
4         2
     5
9         2
     7
16        2
     9
25        2
     11
36

f(x) = 3*x^2 + 2*x + 5

10
     11
21        6
     17
38        6
     23
61        6
     29
90

Το παράδειγμα με τα ρολόγια

Clock A      Clock B      Clock C
1            3            2
+3           +2
4            5            2
+5           +2
9            7            2
+7           +2
16           9            2

Ακαδημαϊκές προσπάθειες Η/Υ

Πρώτοι εμπορικοί Η/Υ

Θεωρητικό υπόβαθρο

Τεχνολογική εξέλιξη

Η επιστήμη της πληροφορικής

(Βασισμένο στο σύστημα ταξινόμησης ACM Computing Reviews.)

Γενική βιβλιογραφία

Βιβλιογραφία

Θέματα για σκέψη

  1. Πόσοι ηλεκτρονικοί υπολογιστές υπάρχουν στη Σάμο; Πως χρησιμοποιούνται; (Μην ξεχάσετε τους υπολογιστές που αποτελούν τμήματα συσκευών ή ολοκληρωμένων εφαρμογών.)
  2. Ποιά είναι η σχέση της πληροφορικής με τα μαθηματικά;
  3. Ποιά είναι η σχέση των μαθηματικών με την πληροφορική;
  4. Πως συνδέονται οι εφαρμογές της πληροφορικής με την παραγωγικότητα και την ανεργία;

Παράσταση δεδομένων

Προηγούμενα θέματα για σκέψη

  1. Πόσοι ηλεκτρονικοί υπολογιστές υπάρχουν στη Σάμο; Πως χρησιμοποιούνται; (Μην ξεχάσετε τους υπολογιστές που αποτελούν τμήματα συσκευών ή ολοκληρωμένων εφαρμογών.)
  2. Ποιά είναι η σχέση της πληροφορικής με τα μαθηματικά;
  3. Ποιά είναι η σχέση των μαθηματικών με την πληροφορική;
  4. Πως συνδέονται οι εφαρμογές της πληροφορικής με την παραγωγικότητα και την ανεργία;

Φυσικός κόσμος και πληροφορική

Φυσικός κόσμος

  1. Αντικείμενα
  2. Ενέργειες

Πληροφορική

  1. Δεδομένα (data)
  2. Αλγόριθμοι (algorithms)

Αλφάβητα και κωδικοποίηση

Παραδείγματα κωδικοποίησης

Παράσταση χαρακτήρων

Ιστορία αριθμητικών συστημάτων

Συστήματα παράστασης

Το δυαδικό σύστημα

Ακέραιοι αριθμοί

Μετατροπές

Πράξεις

Αριθμοί κινητής υποδιαστολής

Προγράμματα

Βιβλιογραφία

Ασκήσεις

  1. Μετατρέψτε τους αριθμούς 15, -7 και 24 σε δυαδικό σύστημα 4 bit.
  2. Μετατρέψτε τους αριθμούς 1010 και 0101 από παράσταση 4 bit (με αρνητικούς) στο δεκαδικό σύστημα.
  3. Υπολογίστε 1101 + 1111. Μετατρέψτε τα στοιχεία και σε δεκαδικό σύστημα.
  4. Υπολογίστε 1101 - 1. Μετατρέψτε τα στοιχεία και σε δεκαδικό σύστημα.
  5. Υπολογίστε 1010 * 101. Εκτιμήστε το χρόνο που απαιτεί ο πολλαπλασιασμός σε σχέση με την πρόσθεση σε έναν ηλεκτρονικό υπολογιστή. Μπορεί να υπάρξει τρόπος ο πολλαπλασιασμός να εκτελεστεί ταχύτερα; Η πρόσθεση;
  6. Μετατρέψτε τους αριθμούς 53, -543 από το οκταδικό σύστημα στο δεκαεξαδικό.
  7. (K. Zuse 1936) Υπάρχει τρόπος να παρασταθούν αριθμοί κινητής υποδιαστολής p bit χρησιμοποιώντας p-1 bits με μια μικρή απώλεια στους επιτρεπόμενους εκθέτες. Πως;

Δομικά στοιχεία υπολογιστών

Προηγούμενα θέματα για σκέψη

  1. Παράσταση αριθμών κινητής υποδιαστολής.
  2. Μετατρέψτε τους αριθμούς 15, -7 και 24 σε δυαδικό σύστημα 4 bit.
  3. Μετατρέψτε τους αριθμούς 1010 και 0101 από παράσταση 4 bit (με αρνητικούς) στο δεκαδικό σύστημα.
  4. Υπολογίστε 1101 + 1111. Μετατρέψτε τα στοιχεία και σε δεκαδικό σύστημα.
  5. Υπολογίστε 1101 - 1. Μετατρέψτε τα στοιχεία και σε δεκαδικό σύστημα.
  6. Υπολογίστε 1010 * 101. Εκτιμήστε το χρόνο που απαιτεί ο πολλαπλασιασμός σε σχέση με την πρόσθεση σε έναν ηλεκτρονικό υπολογιστή. Μπορεί να υπάρξει τρόπος ο πολλαπλασιασμός να εκτελεστεί ταχύτερα; Η πρόσθεση;

Λογικές πύλες

Βιβλιογραφία

Ασκήσεις

Τεχνολογία λογισμικού

Προηγούμενα θέματα για σκέψη

Εισαγωγή

Η τεχνολογία λογισμικού (software engineering) είναι ο κλάδος αυτός της πληροφορικής που έχει ως σκοπό την εξεύρεση τεχνικών και εργαλείων που η χρησιμοποίησή τους στην παραγωγή λογισμικού να εξασφαλίζει για το παραγόμενο προϊόν:
  1. συμμόρφωση με τις προδιαγραφές,
  2. παράδοση στο προδιαγεγραμμένο χρόνο,
  3. κατασκευή στο προδιαγεγραμμένο κόστος,
  4. προσιτή συντήρηση.

Ο κύκλος ζωής του λογισμικού

Το μοντέλο του καταρράκτη (waterfall model)

Προσδιορισμός απαιτήσεων

Σχεδίαση

Κωδικοποίηση

Έλεγχος

Διοίκηση, οργάνωση και κοστολόγηση

Διασφάλιση ποιότητας

Περιβάλλοντα και γλώσσες ανάπτυξης

Βιβλιογραφία

Ασκήσεις

Στοιχεία θεωρητικής πληροφορικής

Προηγούμενα θέματα για σκέψη

Επαλήθευση αλγορίθμων

Παράδειγμα

Είσοδος:
  Α(1..Ν): πίνακας ακεραίων
  N : ακέραιος
Έξοδος:
  Β(1..Ν): πίνακας ακεραίων

Προϋποθέσεις:
  Ν >= 1
Μετασυνθήκες:
  Β(1..Ν) περιέχει τις τιμές του Α(1..Ν)

Μεταβλητές
  Ι : Ακέραιος

I := 1
Όσο Ι <= Ν
  Β(Ι) := Α(Ι)
  Αναλοίωτη συνθήκη: Β(1..Ι) := Α(1..Ι)
  Συνθήκη σύγκλισης: Ν - Ι
  Ι := Ι + 1
Τέλος

Αποδοτικότητα των αλγορίθμων

Πολυπλοκότητα

Μη υπολογισιμότητα

Το πρόβλημα του τερματισμού (halting problem)

Τερματίζει(Πρόγραμμα, Δεδομένα)
Είσοδος: Πρόγραμμα, Δεδομένα
Έξοδος: Αληθές αν το πρόγραμμα τερματίζει με τα δεδομένα,
αλλιώς ψευδές.

Δοκιμή(Πρόγραμμα, Δεδομένα)
Αν Τερματίζει(Πρόγραμμα, Δεδομένα) Τότε
  Όσο αληθές
  Τέλος (Όσο)
Αλλιώς
  Δοκιμή := ψευδές
Τέλος (Αν)

Δοκιμή(Δοκιμή ..., Δοκιμή ...)

Αλγοριθμική οικουμενικότητα

Πεπερασμένα αυτόματα (Finite automata)

Πεντάδα Α = (Ι, Ο, S, λ, δ)
  1. Ι : Τιμές εισόδου
  2. Ο : Τιμές εξόδου
  3. S : Πεπερασμένο σύνολο εσωτερικών καταστάσεων
  4. λ : S X I -> S Συνάρτηση επόμενης κατάστασης
  5. δ : S X I -> O Συνάρτηση επόμενης τιμής εξόδου

Η μηχανή του Turing

  1. Πεπερασμένο αλφάβητο: Α
  2. Πεπερασμένο σύνολο καταστάσεων: Μ
  3. Άπειρη ταινία
  4. Κεφαλή γραφής και ανάγνωσης
  5. Διάγραμμα μετάπτωσης: (Α Χ Μ) -> (Α X {Δ, Α, Σ}) Χ Μ

Παραδείγματα

Η θέση των Church/Turing

Πιθανοτικοί αλγόριθμοι

Δειπνούντες φιλόσοφοι

Για πάντα
   Πέτα νόμισμα και περίμενε το ανάλογο πηρούνι
   Αν υπάρχει και το άλλο πηρούνι Τότε
      πάρε το άλλο πηρούνι
      φάε
   Αλλιώς
      Άσε τα πηρούνια
   Τέλος
Τέλος

Λειτουργική και προσδιοριστική σημασιολογία

Λειτουργική σημασιολογία (Operational semantics)

Αλγοριθμικός ορισμός ενός διερμηνευτή για τη συγκεκριμένη γλώσσα.

Προσδιοριστική σημασιολογία (Denotational semantics)

Ορισμός μιας συνάρτησης που εκφράζει το αποτέλεσμα εκτέλεσης οποιουδήποτε προγράμματος στη συγκεκριμένη γλώσσα.

Βιβλιογραφία

Ασκήσεις

Προσθέστε 5 στο μισό των δύο τελευταίων ψηφίων του Α.Μ. σας. Υπολογίστε (σε s, ώρες, μέρες, χρόνια) τον ελάχιστο χρόνο που θα κάνει για να εκτελέσει ένας υπολογιστής με χρόνο εκτέλεσεης εντολής 100ns αλγορίθμους με την παρακάτω πολυπλοκότητα χρόνου:

Εφαρμοσμένη πληροφορική

Προηγούμενα θέματα για σκέψη

Προσθέστε 5 στο μισό των δύο τελευταίων ψηφίων του Α.Μ. σας. Υπολογίστε (σε s, ώρες, μέρες, χρόνια) τον ελάχιστο χρόνο που θα κάνει για να εκτελέσει ένας υπολογιστής με χρόνο εκτέλεσεης εντολής 100ns αλγορίθμους με την παρακάτω πολυπλοκότητα χρόνου:

Γραφικά με υπολογιστή

Επικοινωνία ανθρώπου-μηχανής

Αυτοματισμός

Προσομοίωση

Προσομοίωση (simulation) είναι η αναπαράσταση μιας διεργασίας με τη βοήθεια ενός μοντέλου. Η αναπαράσταση αυτή μπορεί να είναι: από την πραγματική διεργασία.

Βάσεις δεδομένων

Εφαρμογές γραφείου

Εμπειρα συστήματα

Η δομή ενός έμπειρου συστήματος (expert system)

Προβλήματα

Βιβλιογραφία

Ασκήσεις

Εισαγωγή στον προγραμματισμό

Αρχίζοντας ...

Ο διορθωτής

Το περιβάλλον εργασίας

Το πρώτο μου πρόγραμμα

Το παρακάτω πρόγραμμα τυπώνει "hello, world" στην οθόνη.
program hello;

begin
	writeln('hello, world')
end.
Μπορούμε να το αλλάξουμε για να τυπώσει:

Βιβλιογραφία

Υπολογισμοί με σταθερές

Σταθερές στην Pascal

Ορμαθοί χαρακτήρων (Character strings)
'hello, world'   'John''s PC'
Τιμές τύπου real (πραγματικοί)
3.1415127 1.0 1.6384E4
Τιμές τύπου integer (ακέραιοι)
42 -5 +4096

Πράξεις

+
Πρόσθεση
-
Αφαίρεση
*
Πολλαπλασιασμός
/
Διαίρεση
div
Ακέραια διαίρεση
mod
Υπόλοιπο ακέραιας διαίρεσης
( )
Παρενθέσεις για καθορισμό της σειράς εκτέλεσης.
Πρώτα εκτελούνται οι πολλαπλασισμοί και οι διαιρέσεις, μετά οι προσθέσεις και αφαιρέσεις.

Συναρτήσεις

sqr(x)
Τετράγωνο
sqrt(x)
Τετραγωνική ρίζα
ln(x)
Φυσικός λογάριθμος
exp(x)
e^x
sin(x)
Ημίτονο
cos(x)
Συνημίτονο
tan(x)
Εφαπτομένη
arctan(x)
Τόξο εφαπτομένης
abs(x)
Απόλυτη τιμή

Βιβλιογραφία

Μεταβλητές και εκχωρήσεις

Δήλωση μεταβλητών