Εξέταση Επίστημης Υπολογιστών (Σεπτέμβριος 2008)

Διδάσκοντες: Γ. Γραββάνης, Επ. Καθηγητής

Εξέταση Επίστημης Υπολογιστών (Σεπτέμβριος 2008)

Δημοσίευσηαπό kavourdilis » 15 Σεπ 2008, 10:15

μπορει να μας πει καποιος ποια κεφαλαια ή/κ παραγραφους να προσεξουμε απο το βιβλιο? ???
Τελευταία επεξεργασία από megatron και 18 Ιούλ 2009, 14:50, έχει επεξεργασθεί 1 φορά/ες συνολικά
Αιτία: Επεξερ
kavourdilis
Newbie
 
Δημοσιεύσεις: 21
Εγγραφή: 09 Μάιος 2008, 15:06
Φοιτητής ΗΜΜΥ: Ναι

Re: εξεταση 9/2008

Δημοσίευσηαπό Stokos » 15 Σεπ 2008, 11:38

Θέμα 1 (Θεωρία)

1) Τι είναι αλγόριθμος;
2) Τι είναι πρόγραμμα;
3) Μορφές Αλγορίθμων
3) Τι κάνει ο αλγόριθμος επανάληψης
4) Τι είναι αναδρομή
5) Βιβλιοθήκη, έννοια αποθήκευσες
7) Δομές δεδομένων (stack, queue, list, tree)
8) Τι είναι υπολογισιμότητα
9) Τι είναι πολυπλοκότητα
10) Τι είναι ημιαγωγός τύπου p & n
11) Τι είναι πύλες (Είδη, σχήμα & τι κάνουν)
12) Τρανζίστορ, πυρίτιο (ιδιότητες), αθροιστές (σχήμα & τι κάνουν),  μνήμες, chip
13) Flip-flop (σχήμα & τι κάνει)
14) Είδη διαδρομών
15) Λειτουργικό Σύστημα
16) Σελλιδοποίηση

Θέμα 2 (Δυαδικό Σύστημα)
1) Να μετατρέψετε αριθμούς από δεκαδικό στο δυαδικό και αντίστροφα
2) Να εκτελέσετε πράξεις (πρόσθεση/αφαίρεση) με αριθμούς στο δυαδικό σύστημα
3) Να βρείτε την έξοδο ενός πλήρη αθροιστή (ή παρόμοιου κυκλώματος) με είσοδο ένα δοσμένο δυαδικό αριθμό

Θέμα 3 (Γλώσσα Μηχανής)
Τι κάνει το πρόγραμμα που δίνεται? / Τι βρίσκεται στη τάδε θέση μνήμης μετά την εκτέλεση του προγράμματος?

Θέμα 4 (Προγράμματα σε Ψευδοκώδικα)
1) Να συμπληρώσετε τα κενά στα προγράμματα του ψευδοκώδικα.
(Συμβουλή: Ξεκίνα από την έξοδο του προγράμματος, π.χ. αν έχει έξοδο 1,3,5,7,... στην επανάληψη θα βάλεις να ξεκινά από το 1 και να έχει βήμα 2)

2) Να γραφεί ένα πρόγραμμα σε ψευδοκώδικα που να κάνει το εξής: (...) και να έχει Χ υπολογιστικά βήματα.
Συμβουλές:
α) Αν ξεπεράσεις τον αριθμό των υπολογιστικών βημάτων που θέλει σου το κόβει όλο.
β) Αν δεν αφήνεις κενά μέσα στα IF και Repeat blocks σου τα κόβει όλα.
π.χ.
(ΣΩΣΤΟ)
IF (συνθήκη)
.....εντολές που υπάγονται στο if
.....repeat N times
..........εντολές που υπάγονται στο if και στο repeat
.....end repeat
.....εντολές που υπάγονται στο if
end if

(ΛΑΘΟΣ)
IF (συνθήκη)
εντολές που υπάγονται στο if
repeat N times
εντολές που υπάγονται στο if και στο repeat
end repeat
εντολές που υπάγονται στο if
end if

(Το if πρέπει να είναι στην ίδια κάθετο με το endif που το κλείνει κτλ)

γ) Διάβασε το Κεφ. 2 του βιβλίου του Καράκου στη Fortran, μερικές πέφτουν παρόμοια θέματα από εκεί.
Τελευταία επεξεργασία από Stokos και 15 Σεπ 2008, 11:45, έχει επεξεργασθεί 1 φορά/ες συνολικά
Stokos
 

Re: εξεταση 9/2008

Δημοσίευσηαπό Pagouras » 15 Σεπ 2008, 12:01

Stokos έγραψε: και να έχει [b]Χ υπολογιστικά βήματα.


Οταν λες χ υπολογιστικα βηματα, εννοεις χ γραμμες κωδικα  ??? ???
Vorsprung durch Technik
                                    
                                 
Άβαταρ μέλους
Pagouras
Sr. Member
 
Δημοσιεύσεις: 340
Εγγραφή: 04 Απρ 2008, 11:18

Re: εξεταση 9/2008

Δημοσίευσηαπό Stokos » 15 Σεπ 2008, 13:21

και ναι και όχι... υπολογιστικό βήμα είναι κάθε πράξη που εκτελείται από τον υπολογιστή και έχει ως συνέπεια δέσμευση κάποιας θέσης μνήμης ή αλλαγή περιεχομένου της θέσης μνήμης ή εκτέλεση κάποιας πράξης. Η σειρά π.χ. a:=b+c μπορεί να θεωρηθεί ως ένα υπολογιστικό βήμα, ενώ η σειρά end if δεν είναι υπολογιστικό βήμα.

Παράδειγμα

Υπολογιστικά βήματα είναι τα:
a := 5; (δέσμευση)
i = i+1; (αλλαγή περιεχομένου)
if (a > b) (η σύγκριση είναι πράξη που δίνει true/false)
a := b + c; (εκτέλεση πράξης και αποθήκευση αποτελέσματος)
κτλ

Υπολογιστικά βήματα δεν είναι τα:
end if;
repeat N times (το περιεχόμενό του υπολογίζεται ξεχωριστά) (**)
end repeat;
do; (Μιλάω για το do...while) (**)
end do; (Εννοώ το end do που κλείνει το do_while) (**)
print (a); (*)
κτλ.

(*) Προσοχή:
Το print (a+b) (ή οποιαδήποτε άλλη παράσταση) είναι υπολογιστικό βήμα αφού πρέπει να υπολογίσει πρώτα το a+b, να το αποθηκεύσει (προσωρινά) κάπου και στη συνέχεια να το τυπώσει.

(**) Το do...while και το do_while τα αναλύω παρακάτω:

Ειδική Περίπτωση I

sum := 0;
do while(sum >= 2)
.....sum := sum+1
end do


Αριθμός βημάτων:
1. sum := 0; (sum = 0)
2. Έλεγχος sum >= 2; (Λάθος)
3. sum := sum+1; (sum = 1)
4. Έλεγχος sum >=2; (Λάθος)
5. sum := sum+1; (sum = 2)
6. Έλεγχος sum >= 2; (Σωστό)

Τέλος: 6 Βήματα

Ειδική Περίπτωση IΙ

sum := 0;
do
.....sum := sum+1
while (sum >= 2);


Αριθμός βημάτων:
1. sum := 0; (sum = 0)
2. sum := sum+1; (sum = 1)
3. Έλεγχος sum >=2; (Λάθος)
4. sum := sum+1; (sum = 2)
5. Έλεγχος sum >= 2; (Σωστό)

Τέλος: 5 Βήματα

Ειδική Περίπτωση III

sum := 0
.....repeat 2 times
sum := sum +1;
end repeat


Αριθμός βημάτων:
1. sum := 0; (sum = 0)
2. sum := sum+1; (sum = 1)
3. sum := sum+1; (sum = 2)

Τέλος: 3 Βήματα

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

---

Με αυτό το παράδειγμα ελπίζω να καταλάβατε 2 πράγματα:

1. Το πως υπολογίζουμε τα υπολογιστικά βήματα στις 3 περιπτώσεις βρόγχου (αν και δε νομίζω να σας χρειαστεί στο πρόγραμμα που θα πρέπει να γράψετε, εκτός ίσως από το III)

2. Τη διαφορά της do_while (Ι) με τη do...while (ΙΙ). Η dο...while θα εκτελέσει τουλάχιστον μια επανάληψη ενώ η do_while όχι απαραίτητα (αν π.χ. δώσουμε στην αρχή sum := 2) δε θα μπει ποτέ στο βρόγχο της do_while ενώ θα μπει στο βρόγχο της do...while και θα εκτελέσει μόνο μια φορά μια επανάληψη.

Γενικά σε ένα πολύπλοκο πρόγραμμα είναι αδύνατον να υπολογίσουμε τα υπολογιστικά του βήματα με συγκεκριμένο αριθμό, χρησιμοποιούμε συναρτήσεις [Συνήθως της μορφής: πολυωνύμου ή εκθετικές* ή nLogn (λογάριθμος του 2)] για να περιγράψουμε τη πολυπλοκότητα του προγράμματος. Οπότε αυτό που θα σας ζητηθεί θα είναι μάλλον κάτι εξαιρετικά απλό εφόσον ζητάει συγκεκριμένο αριθμό βημάτων, μην αγχώνεστε  ;)

(*): Ένα πρόγραμμα με εκθετική συνάρτηση πολυπλοκότητας δεν είναι εφικτό από τους σημερινούς υπολογιστές.  :P


---

Μια και αναφέρθηκα σε πράξεις να υπενθυμίσω ότι για ψευδοκώδικα (και για τις περισσότερες γλώσσες προγραμματισμού) ισχύει το εξης:

ακέραιος / ακέραιος = ακέραιος

Παραδείγματα:
6/5 = 1
5/8 = 0
10/6 = 1

(Ακόμα και αν το αποτέλεσμα της διαίρεσης είναι 1,99999... θα έχουμε έξοδο 1 αφού χάνεται το δεκαδικό μέρος για να μετατραπεί σε ακέραιο)

ακέραιος / πραγματικός = πραγματικός
πραγματικός / ακέραιος = πραγματικός
πραγματικός / πραγματικός = πραγματικός

Παραδείγματα:
9,2/4,5 = 2,044
5/2,5 = 2,0
9/2,0 = 4,5 (*)

(*) Προσοχή: Το 2,0 θεωρείται πραγματικός (float ή real) και το 2 ακέραιος (integer)

~~~

Αυτά τα πρόχειρα προς το παρόν, ελπίζω να σας καλύψω με το e-book που ετοιμάζω με τη νέα χρονιά  ;)

Επειδή δε μπορώ να κάνω edit μια μικρή συμπλήρωση:

Είπα πως το a := b+c; μπορεί να θεωρηθεί ως ένα υπολογιστικό βήμα (το οποίο αποτελείται από ουσιαστικά από 2 στοιχειώδεις πράξεις: πρόσθεση b+c και αποθήκευση στο a).

Κατ' επέκταση μπορούμε να θεωρήσουμε τμήματα παρόμοιου κώδικα ως ένα υπολογιστικό βήμα

Το ποιο χαρακτηριστικό παράδειγμα είναι το εξής:

repeat N times
.....Κ εντολές;
end repeat;


N υπολογιστικά βήματα τα οποία αποτελούνται από Κ εντολές οι οποίες μπορούν να αναλυθούν σε Ζ στοιχειώδεις πράξεις.

Επίσης

if συνθήκη then
.....Χ εντολές
else
.....Υ εντολές
end if


μπορεί όλο αυτό το τμήμα να θεωρηθεί ως ένα υπολογιστικό βήμα το οποίο αποτελείται από Χ εντολές αν η συνθήκη είναι true ή Υ εντολές αν η συνθήκη είναι false.

Επομένως μπορούμε να ομαδοποιήσουμε τον έλεγχο στις εντολές Do_while και do...while μαζί με τις εντολές του βρόγχου σε 1 υπολογιστικό βήμα. Επομένως με αυτή τη λογική:

sum := 0;
do while(sum >= 2)
.....sum := sum+1
end do


sum := 0;
do
.....sum := sum+1
while (sum >= 2);


3 βήματα και τα δύο.

Start Program Paradeigma
a := a/b;
a := a/c;
a := a + c*b;
print(a)
End Program Paradeigma


Αυτές οι πράξεις δεν έχουν καμιά σχέση μεταξύ τους, δεν υπάγονται σε κανένα κοινό block εντολών κάποιου if/do_while/repeat κτλ. επομένως είναι 3 υπολογιστικά βήματα (το print(a) δεν υπολογίζεται ως βήμα όπως έχουμε πει).

Τέλος ένα γενικό παράδειγμα:

Start Program
integer a,b;
a := 1;
b := 3;
if((a+b)>5)
.....a := 10
.....repeat 2 times
..........print(a);
.....end repeat;
else
.....repeat 3 times
..........b := b+1;
..........b := b-a;
.....end repeat;
end if
End Program


a := 1; (1o)
b := 3; (2o)
if((a+b)>5) (3o)
Αν είναι true τότε: a := 10 (+1 υπολογιστικό βήμα)
Αν είναι false τότε: repeat 3 times (+3 υπολογιστικά βήματα που αποτελούνται από 2 επιμέρους εντολές)

Άρα μπορούμε να έχουμε από 4 έως 7 υπολογιστικά βήματα.

Συνήθως τη παραπάνω λογική ακολουθεί ο Γραββάνης όταν λέει υπολογιστικό βήμα και όχι την αναλυτική που έκανα εγώ στο προηγούμενο post. Απλά το έκανα τόσο αναλυτικά για να καταλάβετε τη διαφορά μεταξύ do_while και do...while
Τελευταία επεξεργασία από Stokos και 15 Σεπ 2008, 15:27, έχει επεξεργασθεί 1 φορά/ες συνολικά
Stokos
 

Re: εξεταση 9/2008

Δημοσίευσηαπό lamgramm » 16 Σεπ 2008, 18:58

Ξερει κανεις αν αφηνει κομπιουτερακι ο Γραβανης στην εξεταση και αν θελει να φαινονται οι πραξεις στο 2ο θεμα με τις μετατροπες???
Άβαταρ μέλους
lamgramm
Full Member
 
Δημοσιεύσεις: 113
Εγγραφή: 10 Ιουν 2008, 15:44

Re: εξεταση 9/2008

Δημοσίευσηαπό patirgerasimos » 16 Σεπ 2008, 23:09

οχι δεν αφηνει. κ κατι αλλο η εντολη spa που λεει  παρελειψε επομενη εντολη αν AC θετικο.. πως καταλαβαινω αν αυτο που εχω ειναι θετικο??? δλδ οι αριθμοι αυτοι ειναι προσημασμενοι??? α και τα θεματα ειναι ισοδυναμα?
Τελευταία επεξεργασία από patirgerasimos και 16 Σεπ 2008, 23:28, έχει επεξεργασθεί 1 φορά/ες συνολικά
Άβαταρ μέλους
patirgerasimos
Hero Member
 
Δημοσιεύσεις: 1158
Εγγραφή: 09 Απρ 2008, 20:02
Τοποθεσία: Μονή Εσφιγμένου

Re: εξεταση 9/2008

Δημοσίευσηαπό danai » 17 Σεπ 2008, 01:16

Μπορεί κάποιος να μου πει πως λύνεται το ερώτημα:
Εκφράστε την ακόλουθη σειρά εντολών σε δυαδική μορφή
LDA 0B3
SPA
ADD 0AD
STA 0B3

Και κάτι ακόμα γνωρίζουμε αν υπάρχει πρόβλημα να γραφεί ο ψευδοκώδικας με εντολές στα ελληνικά ;
danai
Newbie
 
Δημοσιεύσεις: 33
Εγγραφή: 15 Ιαν 2008, 14:38

Re: εξεταση 9/2008

Δημοσίευσηαπό Pagouras » 17 Σεπ 2008, 09:52

danai έγραψε:Και κάτι ακόμα γνωρίζουμε αν υπάρχει πρόβλημα να γραφεί ο ψευδοκώδικας με εντολές στα ελληνικά ;


Αν θυμαμαι καλα μας ειχε πει οτι δεν εχει προβλημα με τον ψευδοκωδικα ειτε ειναι στα αγγλικα ειτε στα ελληνικα. Ακομα ειχε πει πως αμα θελουμε, μπορουμε αντι για ψευδογλωσσα να χρησιμοποιησουμε οποιαδηποτε γλωσσα προγραμματισμου θελουμε (c,fortran,...)  ;) ;)
Vorsprung durch Technik
                                    
                                 
Άβαταρ μέλους
Pagouras
Sr. Member
 
Δημοσιεύσεις: 340
Εγγραφή: 04 Απρ 2008, 11:18

Re: εξεταση 9/2008

Δημοσίευσηαπό asterianos » 17 Σεπ 2008, 10:28

Pagouras έγραψε:Ακομα ειχε πει πως αμα θελουμε, μπορουμε αντι για ψευδογλωσσα να χρησιμοποιησουμε οποιαδηποτε γλωσσα προγραμματισμου θελουμε (c,fortran,...)  ;) ;)


Για καλό και για κακό ρωτήστε το αυτό την ώρα που θα σας δίνει τα θέματα. Γιατί το Φεβρουάριο τα ίδια μας έλεγε στο μάθημα και όταν τον ρώτησα την ώρα της εξέτασης, μου είπε ότι θέλει ψευδογλώσσα, αλλιώς αν το έγραφα σε fortran και π.χ. ήταν τέλειο, θα έχανα κάποιες μονάδες. Καλύτερα να το διευκρινίσετε πριν γράψετε τον κώδικα.
Ηλεκτρο...λόγοι ενός Ηλεκτρολόγου
Άβαταρ μέλους
asterianos
Full Member
 
Δημοσιεύσεις: 112
Εγγραφή: 04 Απρ 2008, 11:30

Re: εξεταση 9/2008

Δημοσίευσηαπό patirgerasimos » 17 Σεπ 2008, 10:42

ειπε οτι δεν θα τις δωσει ολες θα κοψει κατι λιγο αλλα δεν υπαρχει προβλημα...
Άβαταρ μέλους
patirgerasimos
Hero Member
 
Δημοσιεύσεις: 1158
Εγγραφή: 09 Απρ 2008, 20:02
Τοποθεσία: Μονή Εσφιγμένου

Re: εξεταση 9/2008

Δημοσίευσηαπό paul21 » 17 Σεπ 2008, 12:27

Παιδιά η εντολή AND πώς λειτουργεί???
Δε θέλω τζάκι , Δε θέλω σόμπα.... θέλω μονάχα της Original τη μπόμπα.
Άβαταρ μέλους
paul21
Full Member
 
Δημοσιεύσεις: 193
Εγγραφή: 09 Απρ 2008, 21:11

Re: εξεταση 9/2008

Δημοσίευσηαπό Stokos » 17 Σεπ 2008, 13:10

Εκτελεί τη πράξη AND μεταξύ των δύο αριθμών/λέξεων (σε δυαδική μορφή)

Πράξη AND

Δίνει 1 όταν και τα 2 bit είναι 1, δηλαδή:

0 και 1 = 0
1 και 0 = 0
0 και 0 = 0
1 και 1 = 1

Παράδειγμα εφαρμογής της AND σε αριθμούς δυαδικής μορφής:

1001100011
1011011011
&----------
1001000011
Stokos
 

Re: εξεταση 9/2008

Δημοσίευσηαπό patirgerasimos » 17 Σεπ 2008, 13:21

και η εντολη spa πως δουλευει???
Άβαταρ μέλους
patirgerasimos
Hero Member
 
Δημοσιεύσεις: 1158
Εγγραφή: 09 Απρ 2008, 20:02
Τοποθεσία: Μονή Εσφιγμένου

Re: εξεταση 9/2008

Δημοσίευσηαπό Stokos » 17 Σεπ 2008, 13:51

Είναι ένα "if" ουσιαστικά το οποίο παραλείπει την επόμενη εντολή αν ο αριθμός/λέξη που βρίσκεται στον Accumulator είναι θετικός. Για να καταλάβεις πως δουλεύει το Accumulator διάβασε σελ. 191 του βιβλίου (Χρησιμοποιεί την ονομασία JUMPMSB αντί για SPA εκεί).
Stokos
 

Re: εξεταση 9/2008

Δημοσίευσηαπό patirgerasimos » 17 Σεπ 2008, 14:11

δλδ αν το ποιο σημαντιψο bit στon AC ειναι 0 τοτε η εντολη παρακαμπτεται.. σωστα το πα?? :-\ τα χω φτυσει
Άβαταρ μέλους
patirgerasimos
Hero Member
 
Δημοσιεύσεις: 1158
Εγγραφή: 09 Απρ 2008, 20:02
Τοποθεσία: Μονή Εσφιγμένου

Επόμενο

Μέλη σε σύνδεση

Μέλη σε αυτή την Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες