of 25 /25
1 Κεφάλαιο 0: «Εισαγωγή» Εισαγωγή στην Επιστήμη των Η/Υ Καθ. Κ. Κουρκουμπέτης Οι διαφάνειες βασίζονται σε μεγάλο βαθμό σε αυτές που συνοδεύονται με το προτεινόμενο σύγγραμμα.

Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

1 Κεφάλαιο 0: «Εισαγωγή»

Εισαγωγή στην Επιστήµη των Η/Υ

Καθ. Κ. Κουρκουµπέτης

Οι διαφάνειες βασίζονται σε µεγάλο βαθµό σε αυτές που συνοδεύονται µε το προτεινόµενο σύγγραµµα.

Page 2: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

2 Κεφάλαιο 0: «Εισαγωγή»

Εισαγωγή στην Επιστήµη των Η/Υ

Εισαγωγή

Page 3: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

3 Κεφάλαιο 0: «Εισαγωγή»

ΚΕΦΑΛΑΙΟ 0: «Εισαγωγή»

!   Ο ρόλος των αλγορίθµων !   Η ιστορική εξέλιξη των υπολογιστικών µηχανών !   Η επιστήµη των αλγορίθµων !   Αφαίρεση !   Μια περιγραφή της µελέτης µας !   Κοινωνικές επιπτώσεις

Page 4: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

4 Κεφάλαιο 0: «Εισαγωγή»

Αλγόριθµοι: Ορισµοί

!   Ως αλγόριθµο ορίζουµε το σύνολο των βηµάτων τα οποία καθορίζουν τον τρόπο εκτέλεσης µίας εργασίας.

!   Πρόγραµµα είναι η αναπαράσταση του αλγορίθµου σε µορφή συµβατή προς µία µηχανή (υπολογιστή).

!   Η διαδικασία της ανάπτυξης ενός προγράµµατος ονοµάζεται προγραµµατισµός.

!   Λογισµικό (software) είναι τα προγράµµατα και οι αλγόριθµοι ενώ υλικό (hardware) ο υλικός εξοπλισµός.

Page 5: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

5 Κεφάλαιο 0: «Εισαγωγή»

«Ο αλγόριθµος για ένα µαγικό κόλπο»

Το κόλπο: Ο ταχυδακτυλουργός τοποθετεί µερικά χαρτιά από µια απλή τράπουλα αναποδογυρισµένα σε ένα τραπέζι, και τα ανακατεύει πολύ καλά απλώνοντας τα στην επιφάνεια του τραπεζιού. Κατόπιν, καθώς το κοινό ζητάει τραπουλόχαρτα είτε µαύρου είτε κόκκινου χρώµατος, ο ταχυδακτυλουργός αποκαλύπτει χαρτιά µε το ζητούµενο χρώµα.

Το τέχνασµα και τα λόγια: Βήµα 1. Από µια απλή τράπουλα, επίλεξε δέκα κόκκινα και δέκα

µαύρα φύλλα. Τοποθέτησε τα (ανοιχτά) σε δύο στοίβες στο τραπέζι σύµφωνα µε το χρώµα τους.

Βήµα 2. Ανακοίνωσε ότι έχεις επιλέξει µερικά κόκκινα φύλλα και µερικά µαύρα φύλλα.

Βήµα 3. Πάρε τα κόκκινα φύλλα. Προσποιούµενος ότι τα στοιχίζεις, κράτησε τα αναποδογυρισµένα στο αριστερό σου χέρι και χρησιµοποίησε τον αντίχειρα και το δείκτη του δεξιού σου χεριού για να πιέσεις τον σωρό έτσι ώστε κάθε χαρτί να καµπυλωθεί ελαφρά προς τα έξω. Κατόπιν τοποθέτησε το σωρό των κόκκινων φύλλων αναποδογυρισµένο στο τραπέζι καθώς λες “Σε αυτόν το σωρό έχουµε τα κόκκινα φύλλα”.

Page 6: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

6 Κεφάλαιο 0: «Εισαγωγή»

Βήµα 4. Πάρε τα µαύρα φύλλα. Με τρόπο παρόµοιο µε του βήµατος 3, δώσε στα φύλλα µία ελαφρά καµπύλη προς τα µέσα. Κατόπιν επέστρεψε το σωρό των φύλλων στο τραπέζι (αναποδογυρισµένο) λέγοντας “Kαι σε αυτόν το σωρό έχουµε τα µαύρα φύλλα”.

Βήµα 5. Μόλις τοποθετήσεις τα µαύρα φύλλα στο τραπέζι, ανακάτεψε και µε τα δύο σου χέρια τα κόκκινα και τα µαύρα φύλλα (τα οποία είναι ακόµη αναποδογυρισµένα) απλώνοντάς τα στην επιφάνεια του τραπεζιού. Εξήγησε στο κοινό ότι ανακατεύεις τα χαρτιά πολύ καλά.

Βήµα 6. Εφόσων υπάρχουν αναποδογυρισµένα φύλλα στο τραπέζι, εκτέλεσε τα ακόλουθα βήµατα επαναλαµβανόµενα: 6.1. Βάλε το κοινό να ζητήσει ένα κόκκινο ή ένα µαύρο φύλλο. 6.2. Αν το κοινό ζητήσει κόκκινο χρώµα και υπάρχει κάποιο κοίλο αναποδογυρισµένο φύλλο, σήκωσε το και πες “Να ένα κόκκινο φύλλο”. 6.3. Αν το κοινό ζητήσει µαύρο χρώµα και υπάρχει κάποιο κυρτό αναποδογυρισµένο φύλλο, σήκωσε το και πες “Να ένα µαύρο φύλλο”. 6.4. Αλλιώς, ανακοίνωσε ότι δεν υπάρχουν άλλα φύλλα µε το ζητούµενο χρώµα και αποκάλυψε τα υπόλοιπα φύλλα για να αποδείξεις τον ισχυρισµό σου.

«Ο αλγόριθµος για ένα µαγικό κόλπο»

Page 7: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

7 Κεφάλαιο 0: «Εισαγωγή»

Ιστορία των αλγορίθµων

!   Η µελέτη των αλγορίθµων ξεκίνησε ως µαθηµατικό θέµα. –  Οι αλγόριθµοι µελετούνταν πολύ πριν την εµφάνιση των σύγχρονων υπολογιστών.

!   Στόχος ήταν η εύρεση ενός µοναδικού συνόλου οδηγιών για την επίλυση όλων των προβληµάτων ενός συγκεκριµένου είδους.

!   Παραδείγµατα πρώτων αλγορίθµων –  Αλγόριθµος διαίρεσης πολυψήφιων αριθµών. –  Ευκλείδιος αλγόριθµος.

!   Θεώρηµα της µη πληρότητας του Gödel: κάποια προβλήµατα δεν µπορούν να επιλυθούν µε αλγορίθµους.

Page 8: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

8 Κεφάλαιο 0: «Εισαγωγή»

«Ο Ευκλείδιος αλγόριθµος για την εύρεση του µέγιστου κοινού διαιρέτη δύο θετικών ακεραίων»

Περιγραφή: Αυτός ο αλγόριθµος υποθέτει ότι η είσοδος του είναι δύο θετικοί αριθµοί, και σκοπός του είναι να υπολογίσει το µέγιστο κοινό διαιρέτη αυτών των δύο τιµών.

Διαδικασία: Βήµα 1. Αντιστοίχισε στα Μ και Ν την τιµή της µεγαλύτερης και της

µικρότερης εισόδου, αντίστοιχα. Βήµα 2. Διαίρεσε το Μ µε το Ν, και ονόµασε το υπόλοιπο Υ. Βήµα 3. Αν το Υ είναι διάφορο του 0, αντιστοίχισε στο Μ την τιµή

του Ν, αντιστοίχισε στο Ν την τιµή του Υ, και επέστρεψε στο βήµα 2, διαφορετικάֹ ο µέγιστος κοινός διαιρέτης είναι η τιµή που έχει αντιστοιχιστεί στο Ν τη δεδοµένη στιγµή.

Page 9: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

9 Κεφάλαιο 0: «Εισαγωγή»

Διαγραµµατική αναπαράσταση του αλγορίθµου του Ευκλείδη

Page 10: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

10 Κεφάλαιο 0: «Εισαγωγή»

Ιστορική εξέλιξη των υπολογιστικών µηχανών

!  Πρώτες υπολογιστικές µηχανές: –  Άβακας: η θέση των χαντρών αναπαριστά τα αποθηκευµένα δεδοµένα.

–  Βασισµένες στην τεχνολογία γραναζιών (1600s-1800s) •  H θέση των γραναζιών αναπαριστά αριθµούς. •  Blaise Pascal, Wilhelm Leibniz, Charles Babbage

Page 11: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

11 Κεφάλαιο 0: «Εισαγωγή»

Ο άβακας

Page 12: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

12 Κεφάλαιο 0: «Εισαγωγή»

Ιστορική εξέλιξη των υπολογιστικών µηχανών

!   Πρώτη αναπαράσταση αλγορίθµου σε χαρτί: οπές σε χάρτινες κάρτες. –  Ο Joseph Jacquard (1801) όρισε µοτίβα σε έναν αργαλειό για την παραγωγή υφαντών.

–  Οδηγίες για την Αναλυτική Μηχανή του Babbage.

–  Δηµοφιλής τεχνική το ’70.

Page 13: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

13 Κεφάλαιο 0: «Εισαγωγή»

Ο αργαλειός του Jacquard

Page 14: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

14 Κεφάλαιο 0: «Εισαγωγή»

Πρώτοι Υπολογιστές

!  Βασισµένοι σε ηλεκτρονικά ελεγχόµενους µηχανικούς διακόπτες (ρελέ): –  1940: Stibitz στα Εργαστήρια Bell. –  1944: ο υπολογιστής Mark I, από τον H. Aiden και οµάδα τεχνικών της IBM στο Ηarvard.

!  Βασισµένοι σε τεχνολογία λυχνιών κενού: –  1937-1941: υπολογιστής ABC στο Κολέγιο της Αϊόβα. –  1940s: Colossus από τον T. Flowers για την αποκωδικοποίηση των γερµανικών µηνυµάτων.

–  1940s: ENIAC από J. Mauchly και P. Eckert στο Πανεπιστήµιο της Πενσυλβάνια.

Page 15: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

15 Κεφάλαιο 0: «Εισαγωγή»

Ο υπολογιστής Mark I στο Πανεπιστήµιο Harvard

Page 16: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

16 Κεφάλαιο 0: «Εισαγωγή»

Προσωπικοί Υπολογιστές

!  Στην αρχή υπήρξαν αυτοσχέδιοι υπολογιστές. !  1976: ίδρυση της Apple Computers. !  1981: η ΙΒΜ παρουσιάζει τον πρώτο προσωπικό υπολογιστή (Personal Computer) ή PC. –  Άµεση εµπορική αποδοχή. –  Αποτέλεσε πρότυπο για τους µεταγενέστερους υπολογιστές.

–  Συνήθως χρησιµοποιεί λογισµικό της Microsoft.

Page 17: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

17 Κεφάλαιο 0: «Εισαγωγή»

IBM PC 1981

Page 18: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

18 Κεφάλαιο 0: «Εισαγωγή»

Η επιστήµη των αλγορίθµων

!   Προετοίµασε το έδαφος για την εµφάνιση της επιστήµης των υπολογιστών.

!   Αντλεί στοιχεία από άλλες επιστήµες –  Μαθηµατικά –  Μηχανική –  Ψυχολογία –  Βιολογία –  Διοίκηση Επιχειρήσεων –  Γλωσσολογία.

Page 19: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

19 Κεφάλαιο 0: «Εισαγωγή»

Κεντρικά ερωτήµατα της Επιστήµης των Υπολογιστών

!   Ποια προβλήµατα µπορούν να επιλυθούν µε αλγοριθµικές διαδικασίες;

!   Πώς µπορεί να γίνει ευκολότερη η επινόηση αλγορίθµων;

!   Με ποιον τρόπο µπορούν να βελτιωθούν οι τεχνικές αναπαράστασης και µετάδοσης των αλγορίθµων;

!   Με ποιόν τρόπο µπορεί να εφαρµοστεί η γνώση µας και η τεχνολογία για τους αλγορίθµους ώστε να δηµιουργηθούν καλύτερες µηχανές;

!   Πώς µπορούν να αναλυθούν και να συγκριθούν τα χαρακτηριστικά διαφορετικών αλγορίθµων;

Page 20: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

20 Κεφάλαιο 0: «Εισαγωγή»

Ο κεντρικός ρόλος των αλγορίθµων στην επιστήµη των υπολογιστών.

!!"#$#%& 0 "%'#()(* 32

!"#$, µ$% &$#%'(') #"*+ &,$#")µ* "(+ -,./.'$#"0+ ,12,&$ +% #-µ,&1$/%µ-

34+&$ 2+% &51.6 7&µ4"(+, µ$% &1'%#8% "*+ .,.8% 7% ,1.#,%7)#.-µ& +% 921.--

µ& #& ,21%6 #"% :&94/%$% ,.- %:./.-7.5+. ;& :47& ,&18,"(#*, . #"<=.6 µ%6

&8+%$ +% ,%1.-#$4#.-µ& "$6 :&+"1$:26 $>2&6 :47& 72µ%".6, "% "12=.+"% ,&>8%

21&-+%6, :%706 :%$ µ&1$:26 %,< "$6 &9%1µ.?<µ&+&6 "&=+$:26 '$% "*+ :%/5"&1*

:%"%+<*#* :47& ".µ2%. @& "2".$% ,.$:$/8% 7&µ4"(+, &8+%$ &5:./. +% =4#.-µ&

"* '&+$:) &$:<+%. A% :4+.-µ& /.$,<+ µ$% ,%5#* '$% +% #-':&+"10#.-µ& "$6

#:2B&$6 µ%6, &,$#*µ%8+.+"%6 :4,.$% &1(")µ%"% "% .,.8% 7% µ%6 3.*7)#.-+ +%

&#"$4#.-µ& "* µ&/2"* µ%6.

• C.$% ,1.3/)µ%"% µ,.1.5+ +% &,$/-7.5+ µ& %/'.1$7µ$:26 >$%>$:%#8&6;

• C06 µ,.1&8 +% '8+&$ &-:./<"&1* * &,$+<*#* %/'.187µ(+;

• @& ,.$.+ "1<,. µ,.1.5+ +% 3&/"$(7.5+ .$ "&=+$:26 %+%,%14#"%#*6 :%$ :%"%+<*#*6 "(+ %/'.187µ(+;

• C06 µ,.1.5+ +% %+%/-7.5+ :%$ +% #-':1$7.5+ "% =%1%:"*1$#"$:4 >$%-9.1&"$:0+ %/'.187µ(+;

• C06 µ,.1.5+ +% =1*#$µ.,.$*7.5+ %/'<1$7µ.$ '$% ". =&$1$#µ< ,/*1.9.-1$0+;

• C06 µ,.1.5+ +% &9%1µ.#".5+ %/'<1$7µ.$ '$% "*+ ,%1%'(') &-9-.56 #-µ,&1$9.146;

• @& ,.$.+ "1<,. &,*1&4?&$ "*+ :.$+(+8% * &9%1µ.') "(+ %/'.187µ(+;

C%1%"*1)#"& <"$ . :.$+<6 ,%1.+.µ%#")6 </(+ %-"0+ "(+ &1("*µ4"(+ &8+%$ *

µ&/2"* "(+ %/'.187µ(+ (;=)µ% 0.3).

!"#µ$ 0.3 ! "#$%&'"() &(*+) %,$ -*.+&/0µ,$ 1%2$ #3'1%4µ2 %,$ 53+*+.'1%6$

Page 21: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

21 Κεφάλαιο 0: «Εισαγωγή»

Αφαίρεση

!   Ο όρος αφαίρεση (abstraction) αναφέρεται στη διάκριση µεταξύ των εξωτερικών ιδιοτήτων µιας οντότητας και των λεπτοµερειών της εσωτερικής της σύνθεσης.

!   Αφηρηµένα εργαλεία είναι τα συστατικά στοιχεία ενός συστήµατος, των οποίων αγνοούµε την εσωτερική τους σύνθεση

Page 22: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

22 Κεφάλαιο 0: «Εισαγωγή»

Χρήσεις της αφαίρεσης

!   Η αφαίρεση µας επιτρέπει να χρησιµοποιούµε πολύπλοκα συστήµατα ως ενιαίες καταληπτές µονάδες.

!   Επίσης, µας επιτρέπει να σχεδιάσουµε και να κατασκευάσουµε τέτοια πολύπλοκα συστήµατα.

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

Page 23: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

23 Κεφάλαιο 0: «Εισαγωγή»

Περιεχόµενα µαθήµατος

!   Σχεδιασµός και κατασκευή µηχανών για την εκτέλεση αλγορίθµων: –  Κεφάλαιο 1: Αποθήκευση δεδοµένων –  Κεφάλαιο 2: Χειρισµός δεδοµένων

!   Κεφάλαιο 3: Λειτουργικά συστήµατα !   Κεφάλαιο 4: Δίκτυα και διαδίκτυο !   Κεφάλαιο 5: Αλγόριθµοι

Page 24: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

24 Κεφάλαιο 0: «Εισαγωγή»

Μία περιγραφή της µελέτης µας

!   Κεφάλαιο 6: Γλώσσες προγραµµατισµού !   Οργάνωση δεδοµένων:

–  Κεφάλαιο 8: Αφαιρέσεις δεδοµένων –  Κεφάλαιο 9: Συστήµατα βάσεων δεδοµένων

!   Κεφάλαιο 12: Θεωρία υπολογισµών

Page 25: Εισαγωγή στην Επιστή τωνpages.cs.aueb.gr/courses/epl131/files/Ch00_Introduction.pdfαποκαλύπτει χαρτιά µε το ζητούµενο χρώµα

25 Κεφάλαιο 0: «Εισαγωγή»

Κοινωνικές/οικονοµικές επιπτώσεις

!   Η επιστήµη των υπολογιστών δηµιουργεί νέες δραστηριότητες αλλά εγείρει επίσης νέα ερωτήµατα:

–  Νοµικά: δικαιώµατα και υποχρεώσεις ιδιοκτησίας λογισµικού

–  Ηθικά: αµφισβήτηση παραδοσιακών αρχών –  Διακυβερνήσεως: βαθµός ελέγχου της τεχνολογίας των υπολογιστών και δικτύων από το κράτος

–  Κοινωνικά: επίδραση των υπολογιστών στην καθηµερινή µας ζωή

–  Οικονοµικά: κίνητρα για την χρήση/ανταγωνισµό τεχνολογιών