Computers for All

Diomidis Spinellis
Department of Management Science and Technology
Athens University of Economics and Business
Athens, Greece
dds@aueb.gr

Administrativia

Welcome

Computers for All

Goals

Understand so as to be able to (What should an educated person know about computers)

Overview

Notes

Assessment

Other paedagogical elements

Books

Coursework Instructions

Deadlines

The deadline for all exercises is 2005.01.17 23:59:00 local (Athens) time. Submissions of exercise 2 received before 2005.01.06 10:00 (am) will receive a small bonus grade. The above deadlines are hard: late submissions will not be marked.

Exercise 1: Create your Home Page

The assignment will be marked from the contents of your home page, in the form it appears on the lab's web server. Don't forget to include your name in the page you create.

To setup your page on the lab's web server, hand in the file(s) to Spiros Kallinikos (mailto:skallin@aueb.gr), who will upload your files to the server's directory.

Exercise 2: Excel Christmas Tree

Submissions must be sent as an Excel spreadsheet by email to xmas-tree@istlab.dmst.aueb.gr (mailto:xmas-tree@istlab.dmst.aueb.gr). The sheet must contain conspicuous instructions for running the program that will create the tree, as well as your name.

Essay: Select, Install, Use, and Review an Open Source Application

Submit a printed copy of the essay and the completed questionnaire to the course's secretariat.

Selecting an Open Source Application

  1. Visit http://sourceforge.net (http://sourceforge.net) to browse through its 92000 registered projects.
  2. Select a Free/Libre open source application you perceive as useful to do your job.
  3. Make sure the application can run on your computing platform.
  4. Make sure none of your colleagues has selected the specific application. Have a look at the page http://istlab.dmst.aueb.gr/cfa-reservations.txt (http://istlab.dmst.aueb.gr/cfa-reservations.txt) to see which projects have already been taken.
  5. Reserve the application, by sending email to cfa-reservations@istlab.dmst.aueb.gr (mailto:cfa-reservations@istlab.dmst.aueb.gr).

Essay Outline

Your essay should use the following outline. The proposed contents of each section are indicative; feel free to expand them, or limit them if you do not have enough data.
  1. Application Overview

    Start with the application's name and sourceforge.net URL. Continue with a short summary of the application.

  2. Application Functionality

    Describe what the application does. Include screen dumps here, if appropriate.

  3. Development History

    Describe the history behind this application. How long is it being developed? Is it derived from another application?

  4. Development Team

    Describe the application's development model and team. Is this a lone developer, or an organized team? How is the team organized? Who can participate? If the above are not document in the application's web pages, just say so.

  5. Documentation Overview

    Describe the documentation that comes with the application. Does it contain a user manual, a reference manual, a FAQ list, technical information? Is on-line help available? Can you print it in a nice format? Is it available for browsing over the web?

  6. Source Code Overview

    Try to unpack and browse the application's source code. Most likely, its size and complexity will ovewhelm you; this is expected. If, you notice something worth reporting, include it here.

  7. Support Options

    If you have a problem with the application how can you obtain support? Is there a mailing list, a newsgroup, or an open forum for sending questions? Are these qustions answered promptly? Is there a company providing paid support?

  8. Application Quality

    You may find some of the following criteria (derived from ISO/IEC 9126) useful for discussing the application's quality.

  9. Software License

    How is the application licensed? Does it affect the way you use it?

  10. Critical Evaluation

    Evaluate the application in the context of your work and time constraints. Was installing and learning the application a waste of time, or did you benefit from it?

  11. Appendix A: Detailed Logbook

    Log your work in a logbook. Adopt the following format, and submit it as an appendix. Be honest, this part will be graded for its completeness, but its actual contents will not affect your grade. Do not try to impress us with an entry indicating you worked on New Year's day.
    DateTimeAction
    2004.12.2313:14Work session start
    2004.12.2313:15Browse sourceforge.net, looking for application
    2004.12.2313:38Start downloading Fingerprint manager
    2004.12.2313:42Install application
    2004.12.2313:43Installation failed
    2004.12.2313:45Work session start
    2004.12.2313:46Browse sourceforge.net, looking for another application
    2004.12.2313:55Work session end
    2004.12.2620:03Work session start
    2004.12.2620:10Download Mozilla
    2004.12.2620:15Install application
    2004.12.2620:30Send my first email message
    2004.12.2620:30Work session end

  12. Appendix B: Questionnaire

    This part is also not used in the grade, but its completion is compulsorily.

Questionnaire

Please print out and complete this questionnaire after completing the rest of your essay. Answer the following questions, based on your (we know, limited) experience with downloading and using an open-source application.

Disagree               Agree
I find an open source application easy to use12345
Using an open source application would make it easier to do my job12345
I intend to install and use an open source application on my computer12345
All things considered, using an open source application in my job is a good idea12345
Using an open source application would enhance my effectiveness of the job12345
Learning to operate an open source application is easy to me12345
I intend to use an open source application as a primary function in my job12345
All things considered, using an open source application in my job is a positive idea12345
Using an open source application in my job would increase my productivity12345
I find it easy to get an open source application to do what I want to do12345
Using an open source application in my job would enable me to accomplish tasks more quickly 12345
It is easy for me to become skillful at using an open source application12345
I would find an open source application useful in my job12345
My interaction with an open source application is clear and understandable12345
I intend to use an open source application frequently in my job12345
I find an open source application to be flexible to interact with 12345
All things considered, using an open source application in my job is a beneficial idea12345
I intend to use an open source application in doing my job12345
All things considered, using an open source application in my job is a wise idea12345

Coursework Advice

Technical work, especially that involving computers, often runs into unforseen difficulties. Programs can crash, computers can stop working, ugly bugs can force your to work around a problem. Therefore:

Anatomy of a Computer; Computer Architecture

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

Ο αλγόριθμος ΜΚΔ του Ευκλείδη

Θέλουμε να βρούμε το μέγιστο κοινό διαιρέτη των Α και Β, Α > Β (Π.χ. ΜΚΔ των 18 και 24 είναι το 6, ΜΚΔ των 378 και 216 είναι το 54)
  1. Διαιρούμε ακέραια το Α με το Β και έχουμε ένα υπόλοιπο Υ
  2. Αν το Υ είναι 0 τότε ο Β είναι ο ΜΚΔ
  3. Αν το Υ δεν είναι 0 τότε υπολογίζουμε ως ΜΚΔ τον ΜΚΔ του Β και Υ

Ο αστρολάβος των Αντικηθύρων


Μηχανικός υπολογιστής του William von Schickard


Η διαφορική μηχανή του Charles Babbage


Η αναλυτική μηχανή του Charles Babbage


Διάτρητη κάρτα (1950)

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

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

f(x) = x2

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

f(x) = 3x2 + 2x + 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

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


ENIAC (1946-1955)


Colossus Mark I (1943)


Ο πίνακας οργάνων του υπολογιστή Whirlwind (1947)

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


Ένα από τα 4000 αρθρώματα του IBM 704

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

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


Από αριστερά:


Μνήμη φερριτικού πυρήνα


Λογικό κύκλωμα με λυχνία (IBM Pluggable Units - 1950)


Λογικό κύκλωμα με τρανζίστορ (1960)

Τεχνολογία ημιαγωγών


Τεχνολογία CMOS 7S και έξι επιστρώματα χαλκού


Ο επεξεργαστής 750 της αρχιτεκτονικής IBM Power PC υλοποιημένος με την τεχνολογία χαλκού CMOS 7S


Πυρίτιο σε γερμάνιο (τομή)


Κύκλωμα κατασκευασμένο με την τεχνολογία πυριτίου σε μονωτικό υλικό (silicon on insulator (SOI)) σε ηλεκτρονικό μικροσκόπιο

Οι εικόνες προέρχονται από τον τόπο IBM Microelectronics Gallery (http://www.chips.ibm.com/gallery/index.html).

Δομικά στοιχεία

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

Μερικές φορές θα συναντήσετε και παλαιότερα σύμβολα για τις ίδιες πύλες όπως αυτά που απεικονίζονται στο διάγραμμα που ακολουθεί:

Αθροιστές

Με βάση τις πύλες μπορούν να κατασκευστούν κυκλώματα που κάνουν υπολογισμούς.

Αριθμητική και λογική μονάδα

Η αριθμητική και λογική μονάδα (arithmetic and logical unit (ALU)) εκτελεί αριθμητικές και λογικές πράξεις ανάμεσα σε δύο τελεστέους.
Πράξεις που εκτελεί η ALU 74AS181


Υλοποίηση της ALU 74AS181

Δομή ενός υπολογιστή


Κεντρική μονάδα επεξεργασίας


O κύκλος εντολών

  1. Ανάκληση εντολής (Instruction fetch)
  2. Αποκωδικοποίηση εντολής (Instruction decode)
  3. Εκτέλεση εντολής (Instruction execution)
  4. Πρόσβαση μνήμης (Memory access)
  5. Εγγραφή

Κύρια μνήμη


Περιφερειακή μνήμη


Μονάδα σκληρού δίσκου


Μονάδα ταινίας

Συσκευές εισόδου


Συσκευές εξόδου


Σχεδιογράφος

Συσκευές επικοινωνίας


MODEM


Τερματισμός οπτικών ινών

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

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

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

Γενικές πηγές στο διαδίκτυο

Πηγές στο διαδίκτυο

Data: Representing Information

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

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

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

Πληροφορική

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

Χάρτης καιρού


Εύρεση του κυρτού φλοιού

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

Ορολογία

Bit (b)
0 ή 1
Byte (B)
8 bit - 28 = 256 τιμές
Word
φυσική ομάδα από bit(π.χ. 16, 32, 36, 48, 64). Στους υπολογιστές που χρησιμοποιούμε 32.
KiB/KB
Kibi/Kilo - 1024 (210)
MiB/MB
Mebi/Mega - 1.028.576 (220)
GiB/GB
Gibi/Giga - 1.073.741.824 (230)
TiB/TB
Tebi/Tera - 1.099.511.627.776 (240)
PiB/PB
Peti/Peta - 1.125.899.906.842.624 (250)

Μνημονικός κανόνας

210 είναι περίπου ίσο με 103
2N * 10 είναι περίπου ίσο με 10N * 3

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

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

Παράσταση των χαρακτήρων "HELLO, WORLD! ABCDEFGHIJKLM 0123456789" σε διάτρητη κάρτα.

 ________________________________________________
/HELLO, WORLD! ABCDEFGHIJKLM 0123456789          |
|]]         ]  ]]]]]]]]]                         |
|  ]]]   ]]]            ]]]]                     |
|     ] ]    ]               ]                   |
|11111111111111]11111111]11111]111111111111111111|
|222222222222222]22222222]22222]22222222222222222|
|33]]3]3333]33333]33333333]33333]3333333333333333|
|44444444444]44444]44444444]44444]444444444444444|
|5]5555555555555555]55555555555555]55555555555555|
|6666]66]]6666666666]66666666666666]6666666666666|
|777777777777]7777777]77777777777777]777777777777|
|]8888]888888]88888888]88888888888888]88888888888|
|999999999]999999999999]99999999999999]9999999999|
|________________________________________________|

Παράσταση των χαρακτήρων "HELLO, WORLD! ABCDEFGHIJKLM 0123456789" σε διάτρητη ταινία.

___________
| o  o.   |
| o   .o o|
| o  o.o  |
| o  o.o  |
| o  o.ooo|
|  o o.o  |
|  o  .   |
| o o .ooo|
| o  o.ooo|
| o o . o |
| o  o.o  |
| o   .o  |
|  o  .  o|
|  o  .   |
| o   .  o|
| o   . o |
| o   . oo|
| o   .o  |
| o   .o o|
| o   .oo |
| o   .ooo|
| o  o.   |
| o  o.  o|
| o  o. o |
| o  o. oo|
| o  o.o  |
| o  o.o o|
|  o  .   |
|  oo .   |
|  oo .  o|
|  oo . o |
|  oo . oo|
|  oo .o  |
|  oo .o o|
|  oo .oo |
|  oo .ooo|
|  ooo.   |
|  ooo.  o|
___________

Εμφάνιση χαρακτήρων

Simple rendering
Simple rendering

Anti-aliased rendering
Anti-aliased rendering

ClearType rendering
ClearType rendering

Παράσταση ιστοσελίδων με HTML

H HTML είναι μια εφαρμογή της SGML για την περιγραφή σελίδων στο Web. Περιοχές του κειμένου σημειώνονται με ετικέτες (tags). Κάθε ετικέτα περιλαμβάνει το όνομά της και παραμέτρους. Οι ετικέτες γράφονται ως εξής:
<όνομα ετικέτας παράμετροι>
Μια περιοχή του κειμένου μπορεί να σημειωθεί ως εξής:
<ετικέτα>
περιοχή που σημειώνεται
</ετικέτα>
Βασικές ετικέτες που υποστηρίζει η HTML είναι οι παρακάτω:
html
περιγραφή ολόκληρης σελίδας
head
επικεφαλίδα της σελίδας
body
κείμενο της σελίδας
h1-h6
επικεφαλίδες του κειμένου
p
Παράγραφος
ul
λίστα με τελείες
ol
αριθμημένη λίστας
li
στοιχείο λίστας
br
αλλαγή γραμμής
hr
οριζόντια γραμμή
img
εικόνα
a
(anchor) σημείο πρόσβασης από ή σε υπερκείμενο
pre
προστοιχειοθετημένο κείμενο
dl, dt, dd
λίστα περιγραφών, περιγραφές
i
πλάγιοι χαρακτήρες
b
έντονοι χαρακτήρες
table, tr, th/td
Πίνακας, γραμμή, επικεφαλίδα / δεδομένα
<!-- κείμενο -->
σχόλιο
Παράδειγμα σελίδας:
<!doctype html public "-//IETF//DTD HTML//EN">
<html>
<head>
<title>Τίτλος της σελίδας</title>

<meta NAME="GENERATOR" CONTENT="thread.pl">
<meta NAME="AUTHOR" CONTENT="Diomidis Spinellis">
<meta HTTP-EQUIV="Content-type" CONTENT="text/html; charset=ISO-8859-7">
<link REV="made" HREF="mailto:dds@aueb.gr"> 
<link REL="ToC" href="./web/index.htm">
<link REV="Subdocument" href="./web/index.htm">
<link REL="previous" href="./web/http.htm">
<link REL="next" href="./web/cgi.htm">

</head>

<body>
<h1>Επικεφαλίδα πρώτου επιπέδου</h1><hr />
<p>
Κείμενο που περιέχει ένα σημείο κατάληξης υπερκειμένου
<a name="G42"> (<em>με έντονο κείμενο</em>)</a> 
και μια λίστα:
<ul>
<li> στοιχείο 1 </li>
<li> στοιχείο 2 </li>
</ul>
</p>

<p>
Νέα παράγραφος με ένωση υπερκειμένου στο
<a href="http://www.aueb.gr">Οικονομικό Πανεπιστήμιο</a>
</p>

<hr />
</body>
</html>
Αυτή θα εμφανιστεί ως εξής:

Επικεφαλίδα πρώτου επιπέδου


Κείμενο που περιέχει ένα σημείο κατάληξης υπερκειμένου (με έντονο κείμενο) και μια λίστα:

Νέα παράγραφος με ένωση υπερκειμένου στο Οικονομικό Πανεπιστήμιο (http://www.aueb.gr)


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

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

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

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

Μετατροπές

Πρόσθεση και πολλαπλασιασμός

Πρόσθεση

Ψηφίο 1Ψηφίο 2'AθροισμαΚρατούμενο
0000
0110
1010
1101

Παράδειγμα:

  1110
+10111
------
100101
Δηλαδή 11102 + 101112 = 1001012 ή 1410 + 2310 = 3710

Πολλαπλασιασμός

Παράδειγμα:
  1011
X   11
------
  1011
+1011
------
100001
Δηλαδή 10112 + 112 = 1000012 ή 1110 + 310 = 3310

Αρνητικοί αριθμοί και αφαίρεση

Αφαίρεση με το μέθοδο του συμπληρώματος

Παράδειγμα 1
X      = 4 - 3        <=>
X + 10 = 4 + (10 - 3) <=>
X + 10 = 4 + 7        <=>
X      = 4 + 7 - 10   <=>
X      = 11 - 10      <=>
X      = 1
Παράδειγμα 2
X       = 45 - 23         <=>
X + 100 = 45 + (100 - 23) <=>
X + 100 = 45 + 77         <=>
X       = 45 + 77 - 100   <=>
X       = 122 - 100       <=>
X       = 22
Η εύρεση του συμπληρώματος (complement) ως προς ένα ΒN (π.χ. 10 - 3 ή 100 - 23) και η απαλειφή του όρου ΒN στο τέλος είναι πράξεις εύκολες. Αν θεωρήσουμε πως όλοι οι αριθμοί μας είναι μικρότεροι από ΒN/2 και στο τέλος κάθε πράξης απαλείφουμε τον όποιο όρο ΒN τότε μπορούμε να παριστάνουμε τους αρνητικούς αριθμούς ως θετικούς με βάση το συμπλήρωμά τους από το ΒN (π.χ. το -3 ως 7 για ΒN = 101 ή το -23 ως 77 για ΒN = 102) και να κάνουμε πρόσθεση αντί για αφαίρεση.

Εύρεση του συμπληρώματος στο δυαδικό σύστημα

Παράδειγμα για τον αριθμό 01002 και ΒN = 24 (100002):
10000
-0100
-----
 1100
Στο δυαδικό σύστημα το αποτέλεσμα της αφαίρεσης του αριθμού Α από το ΒN (δηλαδή η παράσταση του -Α με το μέθοδο του συμπληρώματος) μπορεί να υπολογιστεί εύκολα με δύο ισοδύναμους τρόπους:
  1. Αντιστρέφουμε τα 0 σε 1 και 1 σε 0 και προσθέτουμε 1:
    0100 -> 1011
    1011 + 1 = 1100
    
  2. Αντιγράφουμε από δεξιά προς τα αριστερά όλα τα 0 και το πρώτο 1 και αντιστρέφουμε τα υπόλοιπα 0 σε 1 και 1 σε 0:
    0 -> 0 (αντιγραφή)
    0 -> 0 (αντιγραφή)
    1 -> 1 (αντιγραφή)
    0 -> 1 (αντιστροφή)
    

Παράδειγμα παράστασης

Για ΒN = 24 οι αριθμοί που μπορούν να παρασταθούν είναι οι -8...7:
 0 0000
 1 0001
 2 0010
 3 0011
 4 0100
 5 0101
 6 0110
 7 0111
-8 1000
-7 1001
-6 1010
-5 1011
-4 1100
-3 1101
-2 1110
-1 1111
Παρατηρούμε πως οι θετικοί αριθμοί έχουν ως πρώτο ψηφίο 0 και οι αρνητικοί αριθμοί έχουν ως πρώτο ψηφίο 1.

Παράδειγμα αφαίρεσης

Το αποτέλεσμα του 510 - 210 θα βρεθεί ως 0101 + 1110:
 0101
+1110
-----
10011
Με την απαλειφή του όρου 100002 το αποτέλεσμα είναι 112 δηλαδή 310.

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

Το πρότυπο IEEE-488

Ο τρόπος παράστασης του αριθμού κινητής υποδιαστολής μπορεί να διαφέρει σε πολλά σημεία από υπολογιστή σε υπολογιστή (μήκος σημαινόμενου και εκθέτη, παράσταση αρνητικού σημαινόμενου και εκθέτη, κανονικοποίηση του σημαινόμενου). Σήμερα οι περισσότεροι υπολογιστές παριστάνουν τους αριθμούς κινητής υποδιαστολής σύμφωνα με το πρότυπο IEEE-488. Για αριθμούς διπλής ακρίβειας π.χ. Έτσι ο αριθμός καταλαμβάνει συνολικά 64 bit:
Π ΕΕΕΕΕΕΕΕΕΕΕ ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
Για παράδειγμα το π στο δυαδικό σύστημα εφράζεται ως:
11.0010 0100 0011 1111 0110 1010 1000 1000 1000 0101 1010 0011 0000 10.... και στο πρότυπο ΙΕΕΕ-488 με εκθέτη 1 (που παριστάνεται ως 1024) ως:
Π ΕΕΕΕΕΕΕΕΕΕΕ ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
0 10000000000 1001001000011111101101010100010001000010110100011000

Προγράμματα

Συμπίεση δεδομένων χωρίς απώλειες

Για τη συμπίεση δεδομένων (data compression) χωρίς απώλειες (lossless) χρησιμοποιούνται οι παρακάτω τρόποι: Εφαρμογές:

Συμπίεση δεδομένων με απώλειες

Εφαρμογές:

Ανίχνευση και διόρθωση λαθών

Έλεγχος λαθών

Διόρθωση λαθών

Απόσταση Hamming είναι ο αριθμός των bit κατά τον οποίο διαφέρουν δύο λέξεις.
Α	000000
Β	001111
Γ	010011
Δ	011100
Ε	100110
Ζ	101001
Θ	110101
Ι	111010
Αν η απόσταση είναι N μπορούμε να διαπιστώσουμε λάθη N-1 bit και να διορθώσουμε λάθη N-2 bit.

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

Παράρτημα: ο πίνακας ASCII

Ο παρακάτω πίνακας εμφανίζει τους χαρακτήρες του πίνακα ASCII που μπορούν να εμφανιστούν στην οθόνη μαζί με την τιμή τους σε δεκαεξαδικό σύστημα και την αντίστοιχη περιγραφή.
        20    Space
 !      21    Exclamation mark
 "      22    Quotation mark
 #      23    Number sign
 $      24    Dollar sign
 %      25    Percent sign
 &      26    Ampersand
 '      27    Apostrophe
 (      28    Left parenthesis
 )      29    Right parenthesis
 *      2a    Asterisk
 +      2b    Plus sign
 ,      2c    Comma
 -      2d    Hyphen-minus
 .      2e    Full stop
 /      2f    Solidus
 0      30    Digit zero
 1      31    Digit one
 2      32    Digit two
 3      33    Digit three
 4      34    Digit four
 5      35    Digit five
 6      36    Digit six
 7      37    Digit seven
 8      38    Digit eight
 9      39    Digit nine
 :      3a    Colon
 ;      3b    Semicolon
 <      3c    Less-than sign
 =      3d    Equals sign
 >      3e    Greater-than sign
 ?      3f    Question mark
 @      40    Commercial at (papaki)
 A      41    Latin capital letter a
 B      42    Latin capital letter b
 C      43    Latin capital letter c
 D      44    Latin capital letter d
 E      45    Latin capital letter e
 F      46    Latin capital letter f
 G      47    Latin capital letter g
 H      48    Latin capital letter h
 I      49    Latin capital letter i
 J      4a    Latin capital letter j
 K      4b    Latin capital letter k
 L      4c    Latin capital letter l
 M      4d    Latin capital letter m
 N      4e    Latin capital letter n
 O      4f    Latin capital letter o
 P      50    Latin capital letter p
 Q      51    Latin capital letter q
 R      52    Latin capital letter r
 S      53    Latin capital letter s
 T      54    Latin capital letter t
 U      55    Latin capital letter u
 V      56    Latin capital letter v
 W      57    Latin capital letter w
 X      58    Latin capital letter x
 Y      59    Latin capital letter y
 Z      5a    Latin capital letter z
 [      5b    Left square bracket
 \      5c    Reverse solidus
 ]      5d    Right square bracket
 '      5e    Circumflex accent
 _      5f    Low line
 `      60    Grave accent
 a      61    Latin small letter a
 b      62    Latin small letter b
 c      63    Latin small letter c
 d      64    Latin small letter d
 e      65    Latin small letter e
 f      66    Latin small letter f
 g      67    Latin small letter g
 h      68    Latin small letter h
 i      69    Latin small letter i
 j      6a    Latin small letter j
 k      6b    Latin small letter k
 l      6c    Latin small letter l
 m      6d    Latin small letter m
 n      6e    Latin small letter n
 o      6f    Latin small letter o
 p      70    Latin small letter p
 q      71    Latin small letter q
 r      72    Latin small letter r
 s      73    Latin small letter s
 t      74    Latin small letter t
 u      75    Latin small letter u
 v      76    Latin small letter v
 w      77    Latin small letter w
 x      78    Latin small letter x
 y      79    Latin small letter y
 z      7a    Latin small letter z
 {      7b    Left curly bracket
 |      7c    Vertical line
 }      7d    Right curly bracket
 ~      7e    Tilde

Παράρτημα: οι νεοελληνικοί χαρακτήρες στο πρότυπο Unicode

Ο παρακάτω πίνακας εμφανίζει τους νεοελληνικούς χαρακτήρες στο πρότυπο κωδικοποίησης Unicode μαζί με την τιμή τους σε δεκαεξαδικό σύστημα και την αντίστοιχη περιγραφή.
'Α  0386 Capital alpha with acute
 Έ  0388 Capital epsilon with acute
 Ή  0389 Capital eta with acute
 Ί  038a Capital iota with acute
 Ό  038c Capital omicron with acute
 Ύ  038e Capital upsilon with acute
 Ώ  038f Capital omega with acute
 ΐ  0390 Small iota with acute and diaeresis
 Α  0391 Capital alpha
 Β  0392 Capital beta
 Γ  0393 Capital gamma
 Δ  0394 Capital delta
 Ε  0395 Capital epsilon
 Ζ  0396 Capital zeta
 Η  0397 Capital eta
 Θ  0398 Capital theta
 Ι  0399 Capital iota
 Κ  039a Capital kappa
 Λ  039b Capital lamda
 Μ  039c Capital mu
 Ν  039d Capital nu
 Ξ  039e Capital xi
 Ο  039f Capital omicron
 Π  03a0 Capital pi
 Ρ  03a1 Capital rho
 Σ  03a3 Capital sigma
 Τ  03a4 Capital tau
 Υ  03a5 Capital upsilon
 Φ  03a6 Capital phi
 Χ  03a7 Capital chi
 Ψ  03a8 Capital psi
 Ω  03a9 Capital omega
 ϊ  03aa Capital iota with diaeresis
 ϋ  03ab Capital upsilon with diaeresis
 ά  03ac Small alpha with acute
 έ  03ad Small epsilon with acute
 ή  03ae Small eta with acute
 ί  03af Small iota with acute
 ΰ  03b0 Small upsilon with acute and diaeresis
 α  03b1 Small alpha
 β  03b2 Small beta
 γ  03b3 Small gamma
 δ  03b4 Small delta
 ε  03b5 Small epsilon
 ζ  03b6 Small zeta
 η  03b7 Small eta
 θ  03b8 Small theta
 ι  03b9 Small iota
 κ  03ba Small kappa
 λ  03bb Small lamda
 μ  03bc Small mu
 ν  03bd Small nu
 ξ  03be Small xi
 ο  03bf Small omicron
 π  03c0 Small pi
 ρ  03c1 Small rho
 ς  03c2 Small final sigma
 σ  03c3 Small sigma
 υ  03c4 Small tau
 υ  03c5 Small upsilon
 φ  03c6 Small phi
 χ  03c7 Small chi
 ψ  03c8 Small psi
 ω  03c9 Small omega
 ϊ  03ca Small iota with diaeresis
 ϋ  03cb Small upsilon with diaeresis
 ό  03cc Small omicron with acute
 ύ  03cd Small upsilon with acute
 ώ  03ce Small omega with acute

Introduction to Programming

Υλικό και λογισμικό

Ιστορική ανασκόπηση

Η διεργασία του προγραμματισμού

Το περιβάλλον της Visual Basic

Το περιβάλλον υλοποίησης της Visual Basic στο Excel έχει την παρακάτω μορφή:

Πως γράφουμε απλά προγράμματα

Πως το Excel μπορεί να γράψει προγράμματα για εμάς

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

Το πρώτο πρόγραμμα έχει ως στόχο να εμφανίσει στην οθόνη το μήνυμα "hello, world". Έχει την παρακάτω μορφή:
Sub main()
    MsgBox "hello, world"
End Sub
Για να το εκτελέσουμε, πατάμε το πλήκτρο F5 και, αν δεν έχουμε κάνει κάποιο λάθος, θα δούμε στην οθόνη μας το παρακάτω αποτέλεσμα:

Μορφή του προγράμματος

Σταθερές

Εκτύπωση τιμών

Απλές πράξεις

Οι αριθμητικές τιμές της Visual Basic μπορούν να συνδυαστούν με τη χρήση των παρακάτω τελεστών (operators):
Πράξη Τελεστής της Visual Basic
Πρόσθεση +
Αφαίρεση -
Πολλαπλασιασμός *
Διαίρεση /
Υπόλοιπο ακέραιας διαίρεσης mod
Ύψωση σε δύναμη ^

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

Μεταβλητές

Τελεστές σύγκρισης

Οι αριθμητικές τιμές της Visual Basic μπορούν να συγκριθούν με τη χρήση των παρακάτω τελεστών:
Σύγκριση Τελεστής της Visual Basic
Ίσο =
Διάφορο <>
Μικρότερο <
Μεγαλύτερο >
Μικρότερο ή ίσο <=
Μεγαλύτερο ή ίσο >=

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

MsgBox 1 + 1 = 2        '  Εμφανίζει True
MsgBox 1 > 2            '  Εμφανίζει False
MsgBox 5 <> 5           '  Εμφανίζει False
MsgBox 1 <= 5           '  Εμφανίζει True
MsgBox 1 <= 1           '  Εμφανίζει True
MsgBox 1 <= 0           '  Εμφανίζει False

Βρόχοι με την εντολή do while

Η εντολή for

Λογικοί τελεστές

Τα λογικά αποτελέσματα στη Visual Basic μπορούν να συνδυαστούν με τη χρήση των παρακάτω λογικών τελεστών:
Λογική πράξη Τελεστής της Visual Basic
σύζευξη (and) (και) And
διάζευξη (or) (ή) Or
άρνηση (not) (όχι) Not
αποκλειστική διάζευξη (exclusive or) Xor
ισοδυναμία (equivalence) Eqv
συνεπαγωγή (implication) Imp

Παράδειγμα

Ο παρακάτω βρόχος μπορεί να αποτελεί τμήμα του προγράμματος ελέγχου ενός τραπεζικού μηχανήματος αυτομάτων συναλλαγών:
    Dim PIN As Integer
    Dim Tries As Integer
    
    Const CorrectPIN = 1234
    Const MaxTries = 4
    
    Tries = 0
    Do
        PIN = InputBox("Πληκτρολογήστε τον κωδικό εισόδου")
        Tries = Tries + 1
    Loop Until PIN = CorrectPIN Or Tries = MaxTries
Με τον προσδιορισμό Const μπορούμε να αντιστοιχούμε ονόματα σε σταθερές τιμές. Με τον τρόπο αυτό το πρόγραμμα διαβάζεται και συντηρείται ευκολότερα.

Λογικές τιμές

Η εντολή if-else

Ο τύπος της συμβολοσειράς

Συναρτήσεις για συμβολοσειρές

Στη Visual Basic μπορούμε να χειριστούμε συμβολοσειρές με τη χρήση διάφορων συναρτήσεων (έχουμε δει πως μπορούμε να ενώσουμε δύο συμβολοσειρές με τον τελεστή +). Οι πιο σημαντικές συναρτήσεις είναι οι παρακάτω:
Len(string)
Επιστρέφει το μήκος μιας συμβολοσειράς
Left(string, length)
Επιστρέφει length χαραρακτήρες από αριστερά
Right(string, length)
Επιστρέφει length χαραρακτήρες από δεξιά
Mid(string, start[, length])
Επιστρέφει length χαρακτήρες από τη θέση start (ή όλη τη συμβολοσειρά από τη θέση start και μετά).
LTrim(string)
Αφαιρεί κενά στο αριστερό μέρος της συμβολοσειράς
RTrim(string)
Αφαιρεί κενά στο δεξί μέρος της συμβολοσειράς
Trim(string)
Αφαιρεί κενά αριστερά και δεξιά της συμβολοσειράς
Τέλος, η εντολή
Mid(stringvar, start[, length]) = string
επιστρέπει την αλλαγή ενός μέρους μιας συμβολοσειράς (από τη θέση start και για length χαρακτήρες) με μια άλλη.

Αριθμητικοί τύποι

Η Visual Basic παρέχει αρκετούς διαφορετικούς τύπους για το χειρισμό αριθμών. Είναι σημαντικό να επιλέξουμε τον κατάλληλο τύπο σύμφωνα με τις ανάγκες μας. Ο παρακάτω πίνακας μπορεί να μας οδηγήσει στην κατάλληλη επιλογή:
Integer -32,768 to 32,767
Long (long integer) -2,147,483,648 to 2,147,483,647
Single (single-precision floating-point) -3.402823E38 to -1.401298E-45 for negative values; 1.401298E-45 to 3.402823E38 for positive values
Double (double-precision floating-point) -1.79769313486232E308 to -4.94065645841247E-324 for negative values; 4.94065645841247E-324 to 1.79769313486232E308 for positive values
Currency (scaled integer) -922,337,203,685,477.5808 to 922,337,203,685,477.5807
Decimal +/-79,228,162,514,264,337,593,543,950,335 with no decimal point; +/-7.9228162514264337593543950335 with 28 places to the right of the decimal; smallest non-zero number is +/-0.0000000000000000000000000001
Αξίζει να προσέξουμε τα παρακάτω:

Μαθηματικές συναρτήσεις

Οι βασικές μαθηματικές συναρτήσεις της Visual Basic είναι οι παρακάτω:
Abs
Απόλυτη τιμή
Sgn
Πρόσημο
Fix
Αφαίρεση του δεκαδικού τμήματος (στρογγύλευση προς το 0)
Int
Στρογγύλευση προς τα κάτω
Sqr
Τετραγωνική ρίζα
Log
Φυσικός λογάριθμος
Exp
e υψωμένο σε δύναμη
Rnd
Ψευδοτυχαίος αριθμός 0 <= χ < 1. Αρνητικό όρισμα θέτει νέα αρχή για παραγωγή αριθμών, θετικό επιστρέφει τον επόμενο αριθμό της σειράς.
Sin
Ημίτονο
Cos
Συνημίτονο
Tan
Εφαπτομένη
Atn
Αντίστροφη εφαπτομένη

Λογιστικές συναρτήσεις

Η Visual Basic παρέχει μια σειρά από συναρτήσεις για υπολογισμούς λογιστικής φύσης σύμφωνα με τον παρακάτω πίνακα:
ΥπολογισμόςΣυνάρτηση
Calculate the future value of an annuity based on periodic, fixed payments and a fixed interest rate. FV(rate, nper, pmt[, pv[, type]])
Calculate the depreciation of an asset for a specific time period using the double-declining balance method or some other method you specify. DDB(cost, salvage, life, period[, factor])
Calculate the interest payment for a given period of an annuity based on periodic, fixed payments and a fixed interest rate. IPmt(rate, per, nper, pv[, fv[, type]])
Calculate the internal rate of return for a series of periodic cash flows (payments and receipts). IRR(values()[, guess])
Calculate the modified internal rate of return for a series of periodic cash flows (payments and receipts). MIRR(values(), finance_rate, reinvest_rate)
Calculate the number of periods for an annuity based on periodic, fixed payments and a fixed interest rate. NPer(rate, pmt, pv[, fv[, type]])
Calculate the net present value of an investment based on a series of periodic cash flows (payments and receipts) and a discount rate. NPV(rate, values())
Calculate the payment for an annuity based on periodic, fixed payments and a fixed interest rate. Pmt(rate, nper, pv[, fv[, type]])
Calculate the principal payment for a given period of an annuity based on periodic, fixed payments and a fixed interest rate. PPmt(rate, per, nper, pv[, fv[, type]])
Calculate the present value of an annuity based on periodic, fixed payments to be paid in the future and a fixed interest rate. PV(rate, nper, pmt[, fv[, type]])
Calculate the interest rate per period for an annuity. Rate(nper, pmt, pv[, fv[, type[, guess]]])
Calculate the straight-line depreciation of an asset for a single period. SLN(cost, salvage, life)
Calculate the sum-of-years' digits depreciation of an asset for a specified period. SYD(cost, salvage, life, period)

Μετατροπή αριθμών σε συμβολοσειρές

Η συνάρτηση Format επιτρέπει τον ακριβή καθορισμό της μετατροπής αριθμητικών τιμών σε συμβολοσειρές. Η σύνταξή της είναι:
Format(έκφραση[, εμφάνιση])
όπου η "εμφάνιση" είναι μια συμβολοσειρά που καθορίζει θα μετατραπεί η αντίστοιχη έκφραση σύμφωνα με τους παρακάτω κανόνες:
0
Εμφανίζει ένα ψηφίο ή 0
#
Εμφανίζει ένα ψηφίο ή κενό
.
Καθορίζει το σημείο εμφάνισης των δεκαδικών τιμών
,
Καθορίζει το διαχωρισμό των χιλιάδων
%
Εμφανίζει το πηλίκο του αριθμού με το 100 ως ποσοστό
E+
Εμφανίζει τον αριθμό σε εκθετική μορφή με πρόσημο στους θετικούς εκθέτες
E-
Εμφανίζει τον αριθμό σε εκθετική μορφή χωρίς πρόσημο στους θετικούς εκθέτες
"σύμβολα"
Εμφανίζει τα σύμβολα μέσα στα εισαγωγικά
Παράδειγμα:
Sub main()
    Dim x As Currency
    
    x = 1500000
    MsgBox ("Κερδίσατε " + Format(x, "0,0.00 ""EUR""!"))
End Sub
Εμφανίζει:

Ορισμός διαδικασίας

Ορίσματα

Ορισμός συνάρτησης

Στοιχεία αντικεμενοστρεφούς προγραμματισμού

Προγραμματισμός με αντικείμενα

Σύνδεση με το Excel

Η σύνδεση με το Excel μας επιτρέπει να δημιουργήσουμε αυτόματα φύλλα εργασίας ή να διαβάσουμε υπάρχοντα. Η πρόσβαση στο Excel γίνεται μέσα από το αντικείμενο Excel.Application και τις κλάσεις που το αποτελούν. Ο παρακάτω πίνακας των βασικών κλάσεων προέρχεται από την τεκμηρίωση που παρέχει η Microsoft:

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

Sub main()
    Dim xl As Excel.Application
    Dim ws As Excel.Worksheet
    Dim wb As Excel.Workbook
    Dim regions(41) As String

    regions(00) = "Europe"
    regions(10) = "Americas"
    regions(20) = "Asia"
    regions(30) = "Africa"


    Set xl = New Excel.Application
    xl.Visible = True
    Set wb = xl.Workbooks.Add
    Set ws = wb.Worksheets(1)

    ws.Range("A2:A5") = regions
    For i = 2 To 5
        ws.Range("B" & Format(i)).Value = i * 110 * Rnd
    Next i

    Dim chart As Excel.chart
    Dim rn As Range

    Set rn = ws.Range("A1:B5")

    Set chart = wb.Charts.Add
    chart.ChartWizard rn, xl3DPie, 7, xlColumns, 111"Sales by area""Areas""Sales"
End Sub

Χειρισμός χρόνου

Το παρακάτω παράδειγμα μας δείχνει πως μπορούμε με πρόγραμμα να δημιουργήσουμε μια καθυστέριση ορισμένων δευτερολέπτων.
' Delay the specified number of seconds
Sub delay(t As Integer)
    Dim i As Integer
    For i = 1 To t
        delayHalfSecond
    Next i
End Sub

' Delay a period between (0-1) second
Sub delayHalfSecond()
    Dim start As Date

    start = Now
    Do While Second(start) = Second(Now)
        ' Let the computer do something else
        DoEvents
    Loop
End Sub

Πρόσβαση στο πρόχειρο

Το πρόχειρο (clipboard) των Windows συχνά περιέχει κείμενο το οποίο έχουμε αντιγράψει, αποκόψει ή θέλουμε να επικολήσουμε σε άλλες εφαρμογές. Μπορούμε να έχουμε πρόσβαση στο πρόχειρο με το αντικείμενο (object) ClipBoard και τη μέθοδο (method) GetText ως εξής:
Dim Result as String

Result = Clipbboard.GetText
Αντίστοιχα, μπορούμε να κάνουμε το πρόχειρο να περιέχει μια συμβολοσειρά με τις μεθόδους Clear και SetText:
Clipboard.Clear
Clipboard.SetText("These are the new clipboard contents")

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

Παράρτημα: Χαρακτηριστικές αλγοριθμικές γλώσσες

Σε μια αλγοριθμική (imperative) γλώσσα το πρόγραμμα εκφράζει άμεσα τα βήματα που επιθυμούμε να εκτελέσει ο υπολογιστής.

Παράρτημα: Χαρακτηριστικές δηλωτικές γλώσσες

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

Γλώσσες βασισμένες στη λογική

Γλώσσες βασισμένες σε συναρτήσεις

Παράρτημα: Βασικά γλωσσικά εργαλεία

Προετοιμαστής/Διορθωτής (Editor)
Επιτρέπει τη συγγραφή και την αλλαγή του προγράμματος.
Προεπεξεργαστής (Preprocessor)
Επεξεργάζεται το πρόγραμμα εκτελώντας απλούς συμβολικούς μετασχηματισμούς και παράγει ένα αντίστοιχο πρόγραμμα. Χρησιμοποιείται σε συμβολικές γλώσσες, τη Fortran (Ratfor), τη C, και τη C++.
Συμβολομεταφραστής (Assembler)
Μετατρέπει τη συμβολική γλώσσα του επεξεργαστή σε γλώσσα μηχανής.
Μεταγλωττιστής (Compiler)
Μεταφράζει μια γλώσσα υψηλού επιπέδου σε γλώσσα επιπέδου μηχανής.
Διερμηνευτής (Interpreter)
Εκτελεί άμεσα ένα πρόγραμμα σε γλώσσα υψηλού επιπέδου.
Συνδέτης (Linker)
Συρράφει τμήματα ενός προγράμματος που έχουν μεταγλωττιστεί ξεχωριστά σε ένα συνεχές πρόγραμμα.
Φορτωτής (Loader)
Φορτώνει το πρόγραμμα στη μνήμη του επεξεργαστή διορθώνοντας αναφορές σε σχετικές θέσεις μνήμης. Συνήθως τμήμα του λειτουργικού συστήματος.
Αποσφαλματωτής (Debuger)
Επιτρέπει την εκτέλεση του προγράμματος βήμα-βήμα, την εξέταση και αλλαγή μεταβλητών του και γενικά ενέργειες που αποσκοπούν στην ανίχνευση λαθών που μπορεί να περιέχει το πρόγραμμα.
Διερμηνευτής (Interpreter)
Εκτελεί απευθείας τις εντολές του προγράμματος χωρίς ενδιάμεσο στάδιο μεταγλώττισης.

Παράρτημα: Είσοδος στοιχείων

Παράρτημα: Βρόχοι με την εντολή loop while

Παράρτημα: Προσδιορισμός της συνθήκης με τη χρήση της Until

Παράρτημα: Έξοδος από το βρόχο

Παράρτημα: H εντολή select

Παράρτημα: Σύγκριση συμβολοσειρών

Με τον τελεστή Like μπορούμε να συγκρίνουμε αν μια συμβολοσειρά μοιάζει με ένα συγκεκριμένο πρότυπο. Τα πρότυπα καθορίζονται με τη χρήση των παρακάτω χαρακτήρων:
?
Ταιριάζει με οποιοδήποτε ένα χαρακτήρα
*
Ταιριάζει με μηδέν ή περισσότερους χαρακτήρες
#
Ταιριάζει με οποιοδήποτε ψηφίο
[λίστα]
Ταιριάζει με οποιοδήποτε χαρακτήρα στη λίστα (π.χ. [aeiyuio])
[!λίστα]
Ταιριάζει με οποιοδήποτε χαρακτήρα δεν περιέχεται στη λίστα
Η λίστα μπορεί να περιέχει χαρακτήρες ή μια περιοχή χαρακτήρων με τη σύνταξη χαρακτήρας-χαρακτήρας (π.χ. [A-Z]. Αν θέλουμε η λίστα να περιέχει το -, τότε αυτό πρέπει να εμφανίζεται πρώτο στη λίστα.

Παράδειγμα (ο βρόχος ελέγχει αν ο ταχυδρομικός κώδικας είναι γραμμένος σωστά):

Sub main()
    Dim PostCode As String
    Dim CodeOk As Boolean
    
    Do
        PostCode = InputBox("Δώστε ταχυδρομικό κώδικα")
        CodeOk = (PostCode Like "##[- ]###" Or PostCode Like "###[- ]##")
        If Not CodeOk Then
                MsgBox "Λάθος ταχυδρομικός κώδικας, δοκιμάστε ξανά."
        End If
    Loop Until CodeOk
End Sub

Theoretical Computer Science; Algorithms and Data Structures

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

Παράδειγμα

Είσοδος:
  Α(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

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

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

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

Γλώσσες προγραμματισμού

Γλώσσα μηχανής

89 D9 
B8 01 00 
83 F9 00 
74 05 
F7 E1 
49 
EB F6

Συμβολική γλώσσα

; Παραγοντικό του BX στο AX
        MOV  CXBX             ; Μετρητής στο CX
        MOV  AX1              ; Αρχική τιμή 1
LOOP:   CMP  CX0              ; Τέλος;
        JZ   DONE               ; Ναι, έξοδος
        MUL  CX                 ; Όχι, πολλαπλασίασε ΑΧ με CX
        DEC  CX                 ; Επόμενη τιμή του CX
        JMP  LOOP               ; Πίσω στο βρόχο
DONE:

Fortran 77

C Return factorial of N
C
      FUNCTION IFACTORIAL(N)
      INTEGER N
      INTEGER IFACTORIAL
      INTEGER IRESULT, I

      IRESULT = 1
      DO I = 1, N
        IRESULT = IRESULT * I
      END DO
      IFACTORIAL = IRESULT

      END

Fortran 95

! Return factorial of n
function factorial(n) result (nfac)
        integerintent(in) :: n
        integer :: factorial
        integer :: i

        nfac = 1
        do i = 1, n
                nfac = nfac * i
        end do
end function factorial

C

/* Παραγοντικό */
int
factorial(int n)
{
        int result;
        int count;

        count = n;
        result = 1;
        while (count > 0) {
                result = result * count;
                count = count - 1;
        }
        return (result);
}

/* Παραγοντικό (με λιγότερες εντολές) */
int
factorial(int n)
{
        int result = 1;

        for (; n; n--)
                result *= n;
        return (result);
}

Prolog

factorial(0, 1).

% To N_Factorial είναι ισοδύναμο με Ν!
factorial(N, N_Factorial) :-
        N > 0,
        M is N - 1,
        factorial(M, M_Factorial),
        N_Factorial is M_Factorial * N.

Lisp

;; Επιστρέφει το παραγοντικό του n
(define (factorial n)
  (if (= n 1)
    1
    (* n (factorial (- n 1)))))

Basic

500 REM Return factorial of N in variable FACT
510 FACT = 1
520 FOR I = 1 TO N
530 FACT = FACT * I
540 NEXT I
550 RETURN

Visual Basic

' Παραγοντικό του Ν
FUNCTION Factorial(N AS INTEGER) AS INTEGER
        DIM Count AS INTEGER
        DIM Result AS INTEGER

        Count = N
        Result = 1
        WHILE Count > 0
                Result = Result * Count
                Count = Count - 1
        WEND

END FUNCTION

Pascal

(* Παραγοντικό του Ν *)
function factorial(N : Integer) : Integer;
var
  Count, Result : Integer;
begin
     Count := N;
     Result := 1;
     While Count > 0 Do
     begin
           Result := Result * Count;
           Count := Count - 1
     end;
     Factorial := Result
end (* Factorial *);

Java

// Υπολογισμός ν παραγοντικού
public int παραγοντικό(int ν) {
        int αποτέλεσμα;
        int μετρητής;

        μετρητής = ν;
        αποτέλεσμα = 1;
        while (μετρητής > 0) {
                αποτέλεσμα = αποτέλεσμα * μετρητής;
                μετρητής = μετρητής - 1;
        }
        return (αποτέλεσμα);
}

Πίνακες

Παράδειγμα

class Sum {
        static int sum(int a[]) {
                int i, sum = 0;

                for (i = 0; i < a.length; i++)
                        sum += a[i];
                return sum;
        }

        static int testdata[] = {12345};

        public static void main(String args[]) {
                System.out.println(sum(testdata));
        }
}

Εγγραφές

Παράδειγμα

struct point {
        double x;       /* X coordinate */
        double y;       /* Y coordinate */
};

struct customer {
        char name[50];  /* Customer name */
        int balance;    /* Account balance */
};

struct customer customer_list[100];

main()
{
        struct point a, b;

        a.x = 5;
        a.y = 9;
        b.x = 12;
        b.y = 19;
}

Δομές με δείκτη

Παράδειγμα (C)

struct s_int_list {
	int val;
	struct s_int_list *next;
};

Διαδικασίες, συναρτήσεις και τάξεις

Παράδειγμα συνάρτησης και διαδικασίας σε Pascal

program fun;

(* Παραγοντικό του Ν *)
function factorial(N : Integer) : Integer;
var
  Count, Result : Integer;
begin
     Count := N;
     Result := 1;
     While Count > 0 Do
     begin
           Result := Result * Count;
           Count := Count - 1
     end;
     Factorial := Result
end (* Factorial *);

procedure clear_screen;
const number_of_lines = 24;
var i : integer;

begin
  for i := 0 to number_of_lines do
      writeln('');
end (*clear_screen*);

begin
  clear_screen;
  writeln(factorial(5));
end.

Παράδειγμα κλάσης σε Java

class Point extends Object {
   private int x;
   private int y;

   public void MoveTo(int x, int y) {
     this.x = x;
     this.y = y;
  }

  public int GetX() {
    return (x);
  }
}

Αναδρομικές τεχνικές

Παράδειγμα

class Recurse {
        static void russian_doll(int size) {
                int i;

                System.out.print("[");
                for (i = 0; i < size; i++)
                        System.out.print("-");
                System.out.println("]");
                if (size > 1)
                        russian_doll(size - 1);
        }

        static int factorial(int n) {
                if (n == 0)
                        return (1);
                else
                        return (n * factorial(n - 1));
        }

        public static void main(String args[]) {
                System.out.println(factorial(5));
                russian_doll(10);
        }
}

Αποτελέσματα

120
[----------]
[---------]
[--------]
[-------]
[------]
[-----]
[----]
[---]
[--]
[-]

Οι πύργοι του Ανόι

import java.util.*;

public class Hanoi {
        static Stack A, B, C;

        /** Display the contents of a collection with a given name */
        static void showCollection(String name, Collection c) {
                Iterator i;

                System.out.print(name + ": ");
                for (i = c.iterator(); i.hasNext(); )
                        System.out.print(i.next() + " ");
                System.out.println();
        }

        /** Display the hanoi towers */
        static void showConfiguration() {
                showCollection("A", A);
                showCollection("B", B);
                showCollection("C", C);
                System.out.println();
        }

        /** Move n blocks from to using tmp */
        static void move(int n, Stack from, Stack to, Stack tmp) {
                if (n == 1) {
                        to.push(from.pop());
                        showConfiguration();
                } else {
                        move(n - 1, from, tmp, to);
                        to.push(from.pop());
                        showConfiguration();
                        move(n - 1, tmp, to, from);
                }
        }

        public static void main(String args[]) {
                final int N = 4;
                A = new Stack();
                B = new Stack();
                C = new Stack();

                for (int i = N; i > 0; i--)
                        A.push(new Integer(i));
                showConfiguration();
                move(N, A, C, B);
        }
}

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

Database Systems

Advantages

Problems and Limitations

Levels of Abstraction

Physical schema
Defines how data is stored
Conceptual schema or logical schema
Defines data in terms of a data model
External schema or view level
Defines a number of simplified domain-specific views

DBMS Levels of Abstraction

DBMS Levels of Abstraction

Data Independence

The three different levels of abstraction allow us to:

Database Design

  1. Requirements analysis
  2. Conceptual database design: develop high level description
  3. Logical database design: map description into the specific DBMS
  4. Schema refinement: identify and solve potential problems
  5. Physical database design: optimize for specific workloads
  6. Security design

Entities and Attributes

Entity
Object in the real world
Attributes
Describe each entity
Entity set
Group of similar entities (share same attributes)
Attribute domain
Values that can be used for the attribute
Key
Minimal set of attributes that uniquely identify an entity
Primary key
Designated among a number of candidate keys

The books entity set

The books entity set

The Entity Relationship Model

Relationship
Association between two entities
Relationship set
Group of similar relationships
Descriptive attributes
can identify a relationsip
A relationship can be identified as:

The Published relationship

The Published relationship

The Relational Model

Relation Schema

Relation Instance

(Table of rows with the same number of fields)
ISBNTitlePrice
0-387-02620-7Beyond Fear29.00
0-201-79940-5Code Reading49.95
0-07-246535-2Database Management Systems40.00
0-19-502402-8The Timeless Way of Building60.00

Redundancy

Storing redundant information in a database results in:

Example

ISBNTitlePriceDiscountReduced Price
0-387-02620-7Beyond Fear30.001027.00
0-201-79940-5Code Reading50.002040.00
0-07-246535-2Database Management Systems40.002038.00
0-19-502402-8The Timeless Way of Building60.001054.00

Dependencies are resolved by decomposing the relations.

The Structured Query Language

Language used for relational DBMSs.

Used:

SQL Table Definition and Data Manipulation

Create the Table

CREATE TABLE Books (
        isbn CHAR(13),
        title CHAR(100),
        price real)

Add a Record

INSERT
INTO Books (isbn, title, price)
VALUES ("0-201-79940-5""Code Reading"49.95)

Modify Records

UPDATE Books B
SET B.price = B.price * 1.1

Delete a Record

DELETE
FROM Books B
WHERE ISBN="0-201-79940-5"

SQL Queries

Display the Details for a Record

SELECT *
FROM Books
WHERE ISBN="0-201-79940-5"

Display Records Based on a Condition

SELECT title, price
FROM Books
WHERE price > 50 AND price > 10

Perform an Aggregate Calculation

SELECT AVG(price)
FROM Books

Join Two Tables

SELECT title, authorname
FROM Books, Authors
WHERE Books.authorid = Authors.authorid

Query By Example

Query by Example in Microsoft Access
SELECT BOOKS.title, BOOKS.price, BOOKS.price, BOOKS.isbn
FROM BOOKS
WHERE (((BOOKS.price)&gt;100)) OR (((BOOKS.price)&lt;10))
ORDER BY BOOKS.title;

Additional SQL Query Constructs

SQL provides many sophisticated capabilities:

Views

By defining appropriate views on a schema we
CREATE VIEW BrowseBooks(isbn, title)
        AS SELECT B.isbn, B.title
        FROM Books B
        WHERE B.price &lt; 100

Indexes

An index is an auxilliary data structure used to speed up operations that are not efficiently supported by a table's record organisation.
CREATE INDEX IndPrice ON Books
WITH STRUCTURE = BTREE
KEY = (price)
To design the index structure take into account:

Security Issues

Our goal in designing a secure database is to achieve: Discretionary access control provides us the capability to give (and revoke) rights to specific users or groups.

Examples

GRANT SELECT
ON BrowseBooks
TO WebUsers

REVOKE INSERTDELETE
ON Books
From Alice

GRANT INSERTDELETE
ON Books
TO InventoryGroup

GRANT UPDATE(price)
ON Books
TO MarketingGroup

GRANT UPDATE(title, isbn)
ON Books
TO MaintenanceGroup

Transaction Management

Four important properties (ACID):
Atomic
Database ensures that all actions are carried out, or none
Consistency
Users ensure that transactions leave the data in a consistent state
Isolation
Users to not have to worry about concurrently executing transactions
Durability
Completed transactions persist after a crash even if the database has not been updated

Crash Recovery

The Database Administrator

Coordinates all the activities of the database system; the database administrator has a good understanding of the enterprise's information resources and needs.

The database administrator's duties include:

User Profiles

Users are differentiated by the way they expect to interact with the system
Application programmers
interact with system through DML calls
Sophisticated users
form requests in a database query language
Specialized users
write specialized database applications that do not fit into the traditional data processing framework
Naive users
invoke one of the permanent application programs that have been written previously

RAID Storage

Redundant arrays of independent disks (RAID) are used to overcome two bottlenecks associated with disk storage: By using additional redundant disks we can increase both. The following are some typically identified RAID levels:
0: Nonredundant
Data is distributed across different disks to increase performance
1: Mirrored
A second disk set keeps a copy of the data (50% overhead)
0+1 (or 10): Striping and mirroring
Data is distributed across a second disk set to increase performance
2: Error correcting codes
Additional check disks (4:3, 10:4, 25:5) are used to provide redundancy with a smaller overhead (e.g. 57%, 71%, 83%)
3: Bit-interleaved parity
A single additional check disk is used to recover the data by distributing bits across all disks
4: block-interleaved parity
The check disk contains the parity on a block level: higher read throughput
5: block-interleaved distributed parity
Block parity is distributed across all disks: higher read and write throughput
6: higher redundancy
Like 5 with an additional check disk guarding against a second failure

XML Concepts

XML Syntax

An XML document is structured on the following building blocks:
Elements
Delimited by starting and ending tags
Example:
        <title>The Lord of the Rings</title>
Elements can also be empty; a special shortcut makes them smaller:
Example:
        <dvd></dvd>
is the same as
        <dvd />
Attributes
Name=valua pairs in the starting tag, that can be used for metadata
Example:
        <title lang="english">The Lord of the Rings</title>
Entity references
Are used to refer to special (reserved) symbols
SymbolEntity reference
<&lt;
>&gt;
&&amp;
"&quot;
'&apos;
Comments
Delimited by the <!-- and -> sequence
Example:
        <!-- this is a comment ->

Example

<!-- List of shipped books -->
<booklist>
        <book>
                <isbn>0-387-02620-7</isbn>
                <title>Beyond Fear</title>
                <author>
                        <givenname>Bruce</givenname>
                        <familyname>Schneier</familyname>
                </author>
                <price>30.00</price>
        </book>
        <book>
                <isbn>0-201-79940-5</isbn>
                <title>Code Reading</title>
                <author>
                        <givenname>Diomidis</givenname>
                        <familyname>Spinellis</familyname>
                </author>
                <price>50.00</price>
        </book>
        <book>
                <isbn>0-07-246535-2</isbn>
                <title>Database Management Systems</title>
                <author>
                        <givenname>Raghu</givenname>
                        <familyname>Ramakrishnan</familyname>
                </author>
                <author>
                        <givenname>Johannes</givenname>
                        <familyname>Gehrke</familyname>
                </author>
                <price>40.00</price>
        </book>
        <book>
                <isbn>0-19-502402-8</isbn>
                <title>The Timeless Way of Building</title>
                <author>
                        <givenname>Cristopher</givenname>
                        <familyname>Alexander</familyname>
                </author>
                <price>60.00</price>
        </book>
        <book>
                <isbn>3-8218-0479-3</isbn>
                <title lang="german">Lexikon der Populaeren Irrtuemer</title>
                <author>
                        <givenname>Walter</givenname>
                        <familyname>Kraemer</familyname>
                </author>
                <author>
                        <givenname>Goetz</givenname>
                        <familyname>Trenkler</familyname>
                </author>
                <price>40.00</price>
        </book>
</booklist>

Document Type Definitions

Example:
  <!ELEMENT booklist (book)*>
    <!ELEMENT book (isbn,title,author+,price,edition?)*>
      <!ELEMENT isbn (#PCDATA)>
      <!ELEMENT title (#PCDATA)>
      <!ATTLIST title lang (german|english) "german">
      <!ELEMENT author (givenname,familyname)>
        <!ELEMENT givenname (#PCDATA)*>
        <!ELEMENT familyname (#PCDATA)>
      <!ELEMENT price (#PCDATA)>
      <!ELEMENT edition (#PCDATA)>

Bibliography

Operating Systems

Ορισμός και λειτουργίες

Το λειτουργικό σύστημα (operating system) είναι το βασικό πρόγραμμα συστήματος ενός ηλεκτρονικού υπολογιστή. Ελέγχει τη διαχείριση των πόρων του υπολογιστή και θέτει τα θεμέλεια για τη λειτουργία των προγραμμάτων εφαρμογών.

Βασικά στοιχεία

Διεργασίες

Είσοδος και έξοδος στοιχείων

Διαχείριση μνήμης

Σύστημα αρχείων

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

Computer Networks

Εισαγωγή, το μοντέλο αναφοράς OSI

Φυσικό επίπεδο

Επίπεδο σύνδεσης

Επίπεδο δικτύου

Επίπεδο μεταφοράς

Επίπεδο συνόδου

Επίπεδο παρουσίασης

Επίπεδο εφαρμογής

Τα πρωτόκολλα του Internet

Εφαρμογή

Το επίπεδο εφαρμογής στο Internet καλύπτει τα επίπεδα εφαρμογής και παρουσίασης του OSI. Τα πιο συχνά πρωτόκολλα που χρησιμοποιούνται από τους χρήστες είναι:
Telnet
χρήση από απόσταση
FTP
μεταφορά αρχείων
SMTP
μεταφορά email
POP/IMAP
ανάγνωση email
HTTP/HTML
πρόσβαση στο Web

Μια σειρά από πρωτόκολλα στο επίπεδο αυτό υποστηρίζουν τη λειτουργία και τη διαχείριση του δικτύου:

DNS
Κατανεμημένος κατάλογος ονομάτων
SNMP
Διαχείριση από απόσταση
BOOTP
Αρχικό φόρτωμα κώδικα
RARP
Αντίστροφη μετατροπή διευθύνσεων

Μεταφορά

Στο επίπεδο της μεταφοράς χρησιμοποιούνται δύο πρωτόκολλα:
TCP
Transmission Control Protocol
UDP
User Datagram Protoco

Δίκτυο

Στο επίπεδο του δικτύου το Internet Protocol (IP) μαζί με το Internet Control Message Protocol εξασφαλίζουν τη μεταφορά δεδομένων από τον αποστολέα στον παραλήπτη. Το παρακάτω σχήμα παριστάνει τη σχέση ανάμεσα στα διάφορα πρωτόκολλα του internet:
                                    
	 +------+ +-----+ +-----+     +-----+  
	 |Telnet| | FTP | | TFTP| ... | ... |  
	 +------+ +-----+ +-----+     +-----+  
	       |   |         |           |     
	      +-----+     +-----+     +-----+  
	      | TCP |     | UDP | ... | ... |  
	      +-----+     +-----+     +-----+  
		 |           |           |     
	      +--------------------------+----+
	      |    Internet Protocol & ICMP   |
	      +--------------------------+----+
			     |                 
		+---------------------------+  
		|   Local Network Protocol  |  
		+---------------------------+  
Σημείωση: Τα σχήματα της ενότητας αυτής προέρχονται από τα έντυπα RFC που αναφέρονται στη βιβλιογραφία.

IP

Πακέτα στο επίπεδο του δικτύου internet έχουν την παρακάτω μορφή:
    0                   1                   2                   3   
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |Version|  IHL  |Type of Service|          Total Length         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Identification        |Flags|      Fragment Offset    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Time to Live |    Protocol   |         Header Checksum       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Source Address                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Destination Address                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Options                    |    Padding    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Οι διευθύνσεις αποστολέα και παραλήπτη περιγράφονται με 32 bit που παριστάνονται για ευκολία με 4 δεκαδικούς αριθμούς (π.χ. 192.168.135.4). Ένας αρχικός αριθμός από bit (π.χ. 24) παριστάνει το δίκτυο στο οποίο ανήκει ένας συγκεκρικένος υπολογιστής, ενώ τα υπόλοιπα ξεχωρίζουν τον υπολογιστή από τους υπόλοιπους στο ίδιο δίκτυο.

TCP

Το πρωτόκολλο TCP (Transmission Control Protocol) επιτρέπει τη σύνδεση δύο διεργασιών και τη μεταξύ τους επικοινωνία. Το TCP θεωρεί ότι το δίκτυο στο οποίο βασίζεται παρέχει τη δυνατότητα μεταφοράς πακέτων χωρίς εγγυήσεις σχετικά με τη σειρά που θα παραδοθούν, την απώλεια πακέτων ή τη διπλή παράδοσή τους. Πάνω από ένα τέτοιο δίκτυο το TCP παρέχει αξιόπιστη μεταφορά δεδομένων. Οι βασικές υπηρεσίες που παρέχει το TCP είναι οι παρακάτω: Η μορφή της επικεφαλίδας του TCP είναι η παρακάτω:
    0                   1                   2                   3   
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |          Source Port          |       Destination Port        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Sequence Number                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Acknowledgment Number                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Data |           |U|A|P|R|S|F|                               |
   | Offset| Reserved  |R|C|S|S|Y|I|            Window             |
   |       |           |G|K|H|T|N|N|                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           Checksum            |         Urgent Pointer        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Options                    |    Padding    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                             data                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Τα bit URG...FIN έχουν τους παρακάτω ρόλους:
URG
Το πεδίο Urgent Pointer περιέχει δεδομένα
ACK
Το πεδίο Acknowledgment περιέχει δεδομένα
PSH
Λειτουργία Push
RST
Επαναρύθμιση της σύνδεσης
SYN
Συγχρονισμός των αριθμών της σειράς
FIN
Δεν υπάρχουν άλλα δεδομένα από τον αποστολέα

Αρχιτεκτονική του παγκόσμιου ιστού

Προσδιορισμός στοιχείων με URI

Ο προσδιορισμός στοιχείων στο Web γίνεται με τη χρήση των Uniform Resource Locators. Διακρίνονται σε απόλυτα (π.χ. http://www.amazon.com) και σχετικά (π.χ. info.gif). Αποτελούνται από Η χρήση τους επιτρέπει τον προσδιορισμό άλλων σελίδων τοπικά, σε άλλα μηχανήματα, καθώς και ερωτήσεων:
http://www.dmst.aueb.gr/dds/
index.html
http://sourceforge.net/softwaremap/trove_list.php?form_cat=187&discrim=165

Το πρωτόκολλο HTTP

Το πρωτόκολλο HTTP υποστηρίζει τις παρακάτω μεθόδους επικοινωνίας: Παράδειγμα:
GET /pub/WWW/TheProject.html HTTP/1.1
Host: www.w3.org

Ενεργό περιεχόμενο

Υπάρχουν διάφορες τεχνολογίες για να εμφανίσουμε ενεργό περιεχόμενο (active content) στο Web όπως: Προγράμματα που χρησιμοποιούν τις τεχνολογίες αυτές δημιουργούν δυναμικά τις σελίδες HTML ανάλογα με τα στοιχεία του χρήστη.

Αναζήτηση πληροφοριών στον παγκόσμιο ιστό

Οι σελίδες στον παγκόσμιο ιστό μετριούνται σε εκατομμύρια. Για την αποδοτική χρήση τους χρησιμοποιούμε διάφορες προσεγγίσεις.

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

System Security Roadmap

Security Infrastructure

Security Infrastructure Investment

Getting the management commitment

Management-related Security Problems

Security Mission Statement

The security mission statement is determined by a number of factors:

Security Support Personnel Duties

Auditing

Help an organization balance resources expended against the most likely areas of weaknesses.
Audit Type Reason
New System Installation Security Audits Ensure conformance to existing policies and a standard system configuration.
Regular Automated System Audit Checks Reveal a "visitation" by an intruder or illicit activity by insiders.
Random Security Audit Checks
  • Test for conformance to security policies and standards (by finding illicit activity) ,
  • Check for the existence of a specific class of problems (e.g., the presence of a vulnerability reported by a vendor).
Nightly Audits of Critical Files
  • Assess the integrity of critical files (e.g., the password file)
  • Integrity of databases (e.g., payroll or sales and marketing information).
User Account Activity Audits Detect dormant, invalid, misused accounts.
Periodic audits and vulnerability assessments Determine overall state of your security infrastructure.

Internet Attack Methods

Incident Response

Incident Response Centers

CERT(sm) Coordination Center
http://www.cert.org/
email cert@cert.org or call +1 412 268-7090

GRNET-CERT

Computer Emergency Responce Team for the Greek National Research Network

E-Mail: grnet-cert@grnet.gr (mailto:grnet-cert@grnet.gr)

Network Operations Center, University of the Aegean, 30 Voulgaroktonou str, Athens 114 72, Greece

Telephone: +30 - 210 - 649 - 2056
Telefax: +30 - 210 - 649 - 2499
World Wide Web: http://cert.grnet.gr (http://cert.grnet.gr)

Network Management Center
National Technical University of Athens
Iroon Polytechnioy 9
Zografou, GR 157 80
Athens
Greece
phone [+30-210] 772.1860
fax [+30-210] 772.1866
http://www.ntua.gr/grnet-cert/grnet-cert.html (http://www.ntua.gr/grnet-cert/grnet-cert.html)

Software Installation Practices

Modify default software installation to Develop standard installation guidelines for all operating systems and applications used by the organization.

Authentication Practices

Backup Practices

Port Filtering Practices

Evaluating Vulnerabilities

For each vulnerability we need to now:

Common Unix Vulnerabilities

(From the Twenty Most Critical Internet Security Vulnerabilities
2004
Copyright 2001-2004, The SANS Institute
http://www.sans.org/top20.htm (http://www.sans.org/top20.htm))

Common Windows Vulnerabilities

(From the Twenty Most Critical Internet Security Vulnerabilities
2004
Copyright 2001-2004, The SANS Institute
http://www.sans.org/top20.htm (http://www.sans.org/top20.htm))

Home-user Tips

(Excerpted from http://www.nipc.gov/warnings/computertips.htm (http://www.nipc.gov/warnings/computertips.htm))

System Administrator Best Practices

Low-cost Security Improvements

Doing it on a shoestring basis:

Free Tool Repositories

Security Web Sites

Security Books

Articles

Cryptology

Cryptology

Cryptography:
Generalized methods to hide (encrypt) and authenticate information
Cryptanalysis:
Generalized methods to expose and substitute information

Algorithm Uses and Properties

Algorithm Types

Algorithm applications

Maintaining Confidentiality

Transposition Ciphers

Example
1 2 3 4
T R A N
S P O T
I T I O
N X X X
Take-off as 2, 4, 3, 1: RPTXNTOXAOIXTSIN
Try RAYXPAIXYNSXCTLS

Transposition Cryptanalysis

Substitution Ciphers

Polyalphabetic Ciphers

Rotor Machines

The Enigma machine

The Playfair Cipher

Example:
A -> B
B -> I
O -> P
R -> U
T -> A
X -> V
L -> O
A -> I
N -> L
D -> G
I -> Y
N -> L
G -> H
X -> W

SP Networks

Example: 4 bit S-box design with a single permutation

The Data Encryption Standard (DES)

DES structure

The Advanced Encryption Standard (AES)

Hash Function Properties

Hash functions compress a n (abritrarily) large number of bits into a small number of bits (e.g. 512).

Properties

Common Hash Functions

Hash Function Applications

Asymmetric Ciphers

The Diffie-Hellman Protocol

Case Study: Public Key Cryptography

The following example is based on the OpenSSL (http://www.openssl.org/) open-source cryptography library and command-line tool.
#!/bin/sh

################
# Key generation

# Create Alice's key pair
openssl genrsa >alice.private
# Obtain Alice's public key
openssl rsa -pubout <alice.private >alice.public

# Create Bob's key pair
openssl genrsa >bob.private
# Obtain Bob's public key
openssl rsa -pubout <bob.private >bob.public

##########################################
# Alice sends a short confidential message

# Secret message Alice wants to send to Bob
echo "Alice loves you" >message.plain

# Alice encrypts the message using Bob's public key
openssl rsautl -encrypt -in message.plain -out message.encrypted -pubin -inkey bob.public

# Bob decrypts Alice's message using his private key
openssl rsautl -decrypt -in message.encrypted -out message.decrypted -inkey bob.private

##################################
# Bob sends a short signed message

# Message Bob wants to sign
echo "Will you marry me?" >message.plain

# Bob signs the message using his private key
openssl rsautl -sign -in message.plain -out message.signed -inkey bob.private

# Alice verifies Bob's message using his public key
openssl rsautl -verify -in message.signed -out message.verified -pubin -inkey bob.public


#####################################################
# Alice sends a large signed and confidential message

# Secret message Alice wants to send to Bob
cat  >message.plain <<EOF
                       Marital AGREEMENT

THIS AGREEMENT, made this thirteen day of June, 2004 is between Bob
and Alice

1. PURPOSE. The parties expect to be married to death do them part,
   and hear by enter into this agrement vouluntarily.

2. EFFECT OF AGREEMENT. The parties agree that if one or the other
   commits infidelity during the duration of the marriage, that the person
   guilty of said act shall in effect and wholey forsake all material
   property, assets and rights to act as a parent of any children.

3. DEFINITON OF INFEDELITY. Infedelity is defined as follows: Any
   socializing with the intent to establish a realtionship, and/or
   physical contact with other person.

4. JOINT PROPERTY, ETC. This Agreement does not restrict, prohibit
   or condition any conveyance or transfer by the parties, or either of
   them alone, of the Separate Property of either party into tenancy in
   common, joint tenancy, tenency by the entireties or any other form of
   concurrent and/or undivided estate or ownership between the parties,
   or the acquisition of any property in any such form of ownership by the
   parties. The incidents and attributes of ownership and other rights
   of the parties with respect to any property so conveyed, transferred
   or acquired shall be determined under State law and shall not be
   governed by or otherwise determined with reference to this Agreement.

5. SEPARATE PROPERTY. The parties agree that there is no seperate
   property.

6. WAIVER OF RIGHTS. Except as otherwise provided in this Agreement,
   each party hereby waives, releases and relinquishes any and all right,
   title or interest whatsoever, whether arising by common law or present
   or future statute of any jurisdiction or otherwise.

7. DISSOLUTION/SEPARATION/ANNULMENT. Except as otherwise provided in
   this Agreement, each party specifically agrees that neither shall make
   any claim for or be entitled to receive any money or property from
   the other as alimony, spousal support, or maintenance in the event
   of separation, annulment, dissolution or any other domestic relations
   proceeding of any kind or nature, and each of the parties waives and
   relinquishes any claim for alimony, spousal support or maintenance,
   including, but not limited to, any claims for services rendered,
   work performed, and labor expended by either of the parties during
   any period of cohabitation prior to the marriage and during the entire
   length of the marriage. The waiver of spousal support shall apply to
   claims both pre and post-judgment.

8. RIGHT TO CONTEST. Nothing contained herein shall limit the right
   of either party to contest any domestic relations suit between the
   parties or to file a countersuit against the other party; However,
   in any hearing on such suit, this Agreement shall be considered
   a full and complete settlement of all property rights between the
   parties. In such case, neither party shall maintain any claim or demand
   whatsoever against the other for property, suit money, attorney fees
   and costs which is either inconsistent with or not provided for in
   this Agreement.

9. INTEGRATION. This Agreement sets forth the entire agreement between
   the parties with regard to the subject matter hereof. All prior
   agreements, covenants, representations, and warranties, expressed or
   implied, oral or written, with respect to the subject matter hereof,
   are contained herein. All prior or contemporaneous conversations,
   negotiations, possible and alleged agreements, representations,
   covenants, and warranties, with respect to the subject matter hereof,
   are waived, merged, and superseded hereby. This is an integrated
   agreement.

10. BINDING ON SUCCESSORS. Each and every provision hereof shall
   inure to the benefit of and shall be binding upon the heirs, assigns,
   personal representatives, and all successors in the interest of
   the parties.

11. ACKNOWLEDGEMENTS. Each party acknowledges that he or she has
   had an adequate opportunity to read and study this Agreement, to
   consider it, to consult with attorneys individually selected by each
   party, without any form of coercion, duress or pressure. Each party
   acknowledges that he or she has examined the Agreement before signing
   it, and has been advised by independent legal counsel concerning the
   rights, liabilities and implications of this document.

12. STATE LAW. It is intended that this Agreement be valid and
   enforceable within the provisions of the State Law, and that Case
   Law that governs its interpretation. State law is considered to be
   that of California, USA.
EOF

# Alice generates a short random key to be used for encrypting the message
openssl rand 16 -out key.plain

# Alice encrypts the message with the short random key
openssl des3 -e -kfile key.plain -in message.plain -out message.encrypted

# Alice creates a message digest of the message to sign
openssl dgst -binary message.plain >message.digest

# Alice signs the digest using her private key
openssl rsautl -sign -in message.digest -out digest.signed -inkey alice.private

# Alice encrypts the random key using Bob's public key
openssl rsautl -encrypt -in key.plain -out key.encrypted -pubin -inkey bob.public

# Alice sends Bob:
# - the encrypted message
# - the encrypted key
# - the signed message digest


# Bob decrypts Alice's encrypted key using his private key
openssl rsautl -decrypt -in key.encrypted -out key.decrypted -inkey bob.private

# Bob decrypts the message using the decrypted key
openssl des3 -d -kfile key.decrypted -in message.encrypted -out message.decrypted

# Bob verifies the digest Alice has signed using her public key
openssl rsautl -verify -in digest.signed -out message.digest1 -pubin -inkey alice.public

# Bob calculates again a message digest of the message
openssl dgst -binary message.plain >message.digest2

# Bob compares the two message digests to verify Alice signed the agreement
# he has examined
diff message.digest1 message.digest2

A Simple Public Key System

  1. Create a graph with a known perfect code
  2. Simple example: fair coin tossing over the phone
  3. Public key encryption and decryption

Bibliography

Software Engineering

Η σημασία του λογισμικού

Το λογισμικό Μέσα αποθήκευσης γνώσης:
  1. DNA
  2. Εγκέφαλος
  3. Υλικό
  4. Βιβλία
  5. Λογισμικό

Προβλήματα στην υλοποίηση συστημάτων που βασίζονται σε λογισμικό

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

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

  1. Η εφαρμογή μιας συστηματικής πειθαρχημένης και ποσοτικοποιούμενης προσέγγισης στην ανάπτυξη, λειτουργία και συντήρηση του λογισμικού. με άλλα λόγια η εφαρμογή των τεχνικών του μηχανικού στο λογισμικό.
  2. Η μελέτη προσεγγίσεων στο παραπάνω πρόβλημα.
Η τεχνολογία λογισμικού περιλαμβάνει τις παρακάτω περιοχές:
  1. Απαιτήσεις
  2. Σχεδιασμός
  3. Υλοποίηση
  4. Έλεγχος
  5. Συντήρηση
  6. Διαχείριση σχηματισμών
  7. Διαχείριση του οργανισμού, της διεργασίας (process) και του έργου
  8. Διεργασίες τεχνολογίας λογισμικού
  9. Εργαλεία και μέθοδοι
  10. Ποιότητα

Κατηγορίες λογισμικού

Χαρακτηριστικά του λογισμικού

Ιδιότητες του λογισμικού

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

Σχεδιασμός με UML

Η ενοποιημένη γλώσσα σχεδιασμού (unified modeling language) (UML) είναι μια γραφική γλώσσα για την οπτική παράσταση, τη διαμόρφωση προδιαγραφών και την τεκμηρίωση συστημάτων που βασίζονται σε λογισμικό. Η UML στοχεύει στο σχεδιασμό αντικειμενοστρεφών συστημάτων. Το σχέδιο είναι μια απλοποιημένη παράσταση της πραγματικότητας.

Σχεδιάζουμε για να μπορέσουμε να καταλάβουμε το σύστημα που αναπτύσσουμε. Έτσι δημιουργώντας ένα σχέδια επιτυγχάνουμε τέσσερεις στόχους:

  1. παριστάνουμε οπτικά το σύστημα που έχουμε ή θέλουμε να κατασκευάσουμε,
  2. προσδιορίζουμε τη δομή και τη συμπεριφορά του συστήματος,
  3. δημιουργούμε ένα πρότυπο για να βασίσουμε την κατασκευή του συστήματος,
  4. τεκμηριώνουμε τις αποφάσεις που λάβαμε.

Σε όλους τους τεχνολογικούς τομείς ο σχεδιασμός βασίζεται σε τέσσερεις βασικές αρχές:

  1. η επιλογή του είδους του σχεδίου έχει επίπτωση στον τρόπο και την μορφή επίλυσης του προβλήματος,
  2. όλα τα σχέδια εκφράζονται σε διαφορετικές βαθμίδες ακρίβειας,
  3. τα καλύτερα σχέδια σχετίζονται με την πραγματικότητα,
  4. ένα είδος σχεδίων δεν είναι ποτέ αρκετό.

Η UML περιλαμβάνει τρία βασικά στοιχεία:

  1. Οντότητες
  2. Σχέσεις
  3. Διαγράμματα
Η UML είναι μια πλήρης και πλούσια γλώσσα με εξαιρετικά ευρύ πεδίο εφαρμογής. Στο μάθημα αυτό θα εξετάσουμε εξαιρετικά συνοπτικά τον τρόπο παράστασης ορισμένων αντικειμενοστρεφών δομών σε UML.

Διαγράμματα της UML

Η UML ορίζει τα παρακάτω διαγράμματα:

Προβλήματα στη διοίκηση έργων λογισμικού

This project is extremely important, but it has no budget ...

Οι σημαντικότεροι κίνδυνοι

This project is extremely important, but it has no budget ...

Στοιχεία της ευέλικτης ανάπτυξης

Η ευέλικτη ανάπτυξη λογισμικού (agile software development) προσδίδει αξία:

Ασυμβίβαστος προγραμματισμός

Ο ασυμβίβαστος προγραμματισμός (ΑΠ) (eXtreme programing (XP)) εδραιώθηκε ως μεθοδολογία ανάπτυξης για μικρές ομάδες ανάπτυξης έργων στα οποία αλλάζουν συχνά οι προδιαγραφές. Βασικά του χαρακτηριστικά είναι: Η μεθοδολογία δεν είναι κατάλληλη για:

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

The Open Source Landscape

History

Basic Concepts

The Open Source Definition

Introduction

Open source doesn't just mean access to the source code. The distribution terms of open-source software must comply with the following criteria:

1. Free Redistribution

The license shall not restrict any party from selling or giving away the software as a component of an aggregate software distribution containing programs from several different sources. The license shall not require a royalty or other fee for such sale.

2. Source Code

The program must include source code, and must allow distribution in source code as well as compiled form. Where some form of a product is not distributed with source code, there must be a well-publicized means of obtaining the source code for no more than a reasonable reproduction cost preferably, downloading via the Internet without charge. The source code must be the preferred form in which a programmer would modify the program. Deliberately obfuscated source code is not allowed. Intermediate forms such as the output of a preprocessor or translator are not allowed.

3. Derived Works

The license must allow modifications and derived works, and must allow them to be distributed under the same terms as the license of the original software.

4. Integrity of The Author's Source Code

The license may restrict source-code from being distributed in modified form only if the license allows the distribution of "patch files" with the source code for the purpose of modifying the program at build time. The license must explicitly permit distribution of software built from modified source code. The license may require derived works to carry a different name or version number from the original software.

5. No Discrimination Against Persons or Groups

The license must not discriminate against any person or group of persons.

6. No Discrimination Against Fields of Endeavor

The license must not restrict anyone from making use of the program in a specific field of endeavor. For example, it may not restrict the program from being used in a business, or from being used for genetic research.

7. Distribution of License

The rights attached to the program must apply to all to whom the program is redistributed without the need for execution of an additional license by those parties.

8. License Must Not Be Specific to a Product

The rights attached to the program must not depend on the program's being part of a particular software distribution. If the program is extracted from that distribution and used or distributed within the terms of the program's license, all parties to whom the program is redistributed should have the same rights as those that are granted in conjunction with the original software distribution.

9. License Must Not Restrict Other Software

The license must not place restrictions on other software that is distributed along with the licensed software. For example, the license must not insist that all other programs distributed on the same medium must be open-source software.

*10. License Must Be Technology-Neutral

No provision of the license may be predicated on any individual technology or style of interface.

Origins: Bruce Perens wrote the first draft of this document as "The Debian Free Software Guidelines", and refined it using the comments of the Debian developers in a month-long e-mail conference in June, 1997. He removed the Debian-specific references from the document to create the "Open Source Definition."

Copyright © 2004 by the Open Source Initiative (http://www.opensource.org)

Software Categories (Sourceforge)

CategoryNumber
Internet 15604
System 12793
Software Development 10607
Communications 9814
Games/Entertainment 9097
Multimedia 7765
Scientific/Engineering 5769
Database 3976
Office/Business 3111
Desktop Environment 2137
Education 2002
Text Editors 1735
Security 1678
Other/Nonlisted Topic 1583
Terminals 393
Printing 281
Sociology 219
Religion 172

Development Status

StatusNumber
1 - Planning 14384
4 - Beta 12036
2 - Pre-Alpha 10308
3 - Alpha 9819
5 - Production/Stable 9664
6 - Mature 904
7 - Inactive 465

Software Categories (FreeBSD Ports)

Top-40 package categories (by population) in the FreeBSD Ports distribution.
CategoryNumber of Packages
Development Tools929
Networking699
www494
Games490
Text Processing445
japanese438
Graphics417
Audio352
Security347
Misc346
Mail322
System Utilities313
Languages240
Editors197
Databases196
X11 toolkits188
Printing188
x11183
Math180
Chinese107
Multimedia103
X11 wm101
Emulators92
Distribution Files83
News81
Java75
ftp75
Archivers72
Korean71
Desk Utilities67
IRC66
Biology62
Astronomy62
Converters59
Communications59
X11 Fonts47
CAD44
X11 Servers42
X11 Clocks39
Palm34
cd /usr/ports
find * -prune -type d |
while read i
do
        echo "$i `ls $i | wc -l`"
done |
sort -rn +1 |
head -40

Operating Environments

EnvironmentNumber
Web Environment 15024
Win32 (MS Windows) 12928
Console (Text Based) 12676
X11 Applications 12571
Other Environment 5659
No Input/Output (Daemon) 4058
Cocoa (MacOS X) 1410
Handhelds/PDA's 743

Operating System

OSNumber
POSIX 30953
OS Independent 19363
Microsoft 19289
MacOS 3275
Other OS 1032
PDA Systems 723
BeOS 426
OS/2 132

Language

LanguageNumber
C++ 12983
C 12971
Java 11470
PHP 8617
Perl 5389
Python 3059
Visual Basic 1771
JavaScript 1641
Delphi/Kylix 1407
Unix Shell 1402
C# 1316
PL/SQL 942
Tcl 788
Objective C 485
ASP 472
Lisp 289
Ruby 287
Pascal 284
Object Pascal 210
Assembly 203
Scheme 173
ML 137
Cold Fusion 119
Fortran 113
Zope 111
Prolog 84
Ada 79
Eiffel 67
Forth 51
Smalltalk 50
XBasic 28
Rexx 28
Erlang 26
PROGRESS 20
Pike 16
Other 17
Logo 15
REBOL 13
APL 12
Euphoria 10
Modula 5

System Software

Operating Systems

Databases

Emulators

Language Processors

Graphics

Applications and Libraries

Environments

Development Tools

Text Processing

Web and Application Servers

Desktop Applications

Open Source Repositories

Influence on Product Development

Advantages

Problems

Development Process Advantages

Development Process Problems

License Distribution (Sourceforge)

LicenseNumber
GNU General Public License (GPL) 35807
GNU Library or Lesser General Public License (LGPL) 5447
BSD License 3587
Artistic License 1119
Apache Software License 905
MIT License 881
Mozilla Public License 1.1 (MPL 1.1) 539
Common Public License 265
Mozilla Public License 1.0 (MPL) 260
zlib/libpng License 245
Qt Public License (QPL) 205
Open Software License 184
Python License (CNRI Python License) 159
Academic Free License (AFL) 131
Python Software Foundation License 80
IBM Public License 70
PHP License 49
Apple Public Source License 44
Sun Industry Standards Source License (SISSL) 43
Sun Public License 38
Jabber Open Source License 36
wxWindows Library Licence 33
University of Illinois/NCSA Open Source License 29
Zope Public License 25
Nethack General Public License 24
W3C License 21
Intel Open Source License 19
Open Group Test Suite License 14
Sleepycat License 13
Apache License V2.0 12
Eiffel Forum License 10
Eiffel Forum License V2.0 10
Attribution Assurance License 9
Reciprocal Public License 7
Ricoh Source Code Public License 6
Historical Permission Notice and Disclaimer 6

Legal Exposure

Web sites

Further Reading