labs

Last update: 06/04/2005

Λύσεις Θεμάτων
1. Τεστ 1
2. Τεστ 2
3. Τεστ 3
4. Τελικό Τεστ
Θέματα και Λύσεις Θεμάτων σε μορφή word
1. Τεστ 1 και Λύσεις για το Τεστ 1
2. Τεστ 2 και Λύσεις για το Τεστ 2
3. Τεστ 3 και Λύσεις για το Τεστ 3
4. Τελικό Τεστ και Λύσεις για το Τελικό Τεστ

Θέματα εξαμηνιαίων τεστ

Τεστ 1

Εισαγωγή στην Επιστήμη των Ηλεκτρονικών Υπολογιστών

Τμήμα (α)

Ενημερωτικό 1^ο Test (ΑΝΑΚΕΦΑΛΑΙΩΤΙΚΟ ΟΚΤΩΒΡΙΟΥ 2003)

1. Να γραφεί ο αριθμός 2009 στο α. Δυαδικό, β. Οκταδικό, γ. Δεκαεξαδικό σύστημα αρίθμησης.

2. Σ’ ένα Η.Υ. MAR (Memory Address Register) έχει μήκος 16 bits. Πόσο είναι το μέγεθος της Μνήμης του Η.Υ.;

3. Τον αριθμό -2003 να τον γράψετε στο σύστημα συμπλήρωμα του 2.

4. Ο αριθμός του συστήματος συμπλήρωμα του 2: 11111111, ποιος είναι;

5. Γράψτε τους 15 πρώτους αριθμούς του δωδεκαδικού συστήματος.

6. Δώστε τη "λογική" συνάρτηση του κρατούμενου του πλήρη αθροιστή και το βέλτιστο κύκλωμα υλοποίησής της. Ποιοι είναι οι χαρακτηριστικοί αριθμοί της συνάρτησης αυτής;

7. Στο ακόλουθο πρόγραμμα:

0	INA A
1	STA A50
2	INA A
3	OUT A
4	SUB A50
5	BPL A3
6	HLT

Διαβάζονται οι αριθμοί: 5 και 337. Γράψτε ποιοι αριθμοί εξάγονται από αυτό;

8. Δείξτε ότι η πύλη NAND είναι οικουμενική (Δηλαδή οι τρεις βασικές πύλες OR, AND και NOT μπορούν να εκφραστούν με τη βοήθεια μόνο της NAND)

9. Ένα κύκλωμα με 4 εισόδους, πόσες γραμμές θα έχει ο πίνακας αληθείας του; Ένας multiplexter με 16 εισόδους πόσες γραμμές ελέγχου θα έχει;

10. Για την ασφαλή μετάδοση των αριθμών χρησιμοποιείται σε κάθε ένα ψηφίο που μεταδίδεται ένα επιπλέον bit, που λέγεται parity bit (ψηφίο ισοτιμίας) και ο ρόλος του είναι να κάνει το πλήθος των bits που είναι 1, του κάθε ψηφίου, είτε περιττού, είτε άρτιου πλήθους (odd or even parity). Για την "φυσική" κωδικοποίηση των 10 ψηφίων του δεκαδικού, στο δυαδικό, κατασκευάσατε τον πίνακα αληθείας της περιττής ισοτιμίας και στη συνέχεια δώσατε το βέλτιστο κύκλωμα που θα δημιουργεί αυτό το bit (της περιττής ισοτιμίας). Τέλος, δώσατε την έκφραση της λογικής συνάρτησης του bit της περιττής ισοτιμίας καθώς και τους χαρακτηριστικούς αριθμούς της συνάρτησης αυτής.

11. Δίδονται δυο φυσικοί αριθμοί Ι και J. Να περιγραφεί, με όποιο τρόπο θέλετε, ο αλγόριθμος που θα προσδιορίζει εάν οι αριθμοί αυτοί είναι πρώτοι αριθμοί. (Δυο φυσικοί αριθμοί είναι πρώτοι, εάν ο μόνος κοινός τους διαιρέτης είναι η μονάδα.)

Τεστ 2

Εισαγωγή στην Επιστήμη των Ηλεκτρονικών Υπολογιστών

Τμήμα (α)

2^ο Test Μηνός – 11.12.2003

1. Έχουμε διαθέσιμο τον MIRACLE και θέλουμε να γράψουμε ένα πρόγραμμα στη συμβολική του γλώσσα, που να διαβάζει τετράδες αριθμών (μεγάλου πλήθους) και να βρίσκει τον μικρότερο και τον μεγαλύτερο της τετράδας, που να τους δίδει στο μέσο εξόδου με την αυτή σειρά.

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

3. Να περιγραφούν τα στάδια από τα οποία διέρχεται η διαδικασία της μεταγλώττισης ενός προγράμματος γραμμένου σε γλώσσα υψηλού επιπέδου. Τέλος να δοθεί ο τρόπος με τον οποίο συνδέεται το πρώτο με το δεύτερο στάδιο.

4. Δίδεται η παρακάτω γραμματική μιας γλώσσας υψηλού επιπέδου

<var> :: = A | B | C

<exp> :: = <var> | - <var> | <exp> + <var> | <exp> * <var>

Εξετάσατε, εάν η παρακάτω ακολουθία συμβόλων είναι μια αποδεκτή ή μη αποδεκτή <exp> και γιατί;

– (Α + Β)(Α + (Α*Β) + C) + A

Τεστ 3

Εισαγωγή στην Επιστήμη των Ηλεκτρονικών Υπολογιστών

Τμήμα (α)

Test Εξαμήνου – 22.1.2004

Θέμα 1. (α) Σ’ ένα καταχωρητή των 2 δύο bytes υπάρχει το περιεχόμενο: 1000100110000111. Προσδιορίσατε τι παριστά ο καταχωρητής στους BCD:

(i) στον Κώδικα Χ-3 και (ii) στον κώδικα Gray.

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

(β) Δείξτε ότι η πύλη NAND είναι οικουμενική (universal) και σχηματίσατε τον πίνακα αληθείας της συνδυαστικής διάταξης:

Λειτουργία

…

Σε τι μπορεί να χρησιμεύσει;

Θέμα 2. (α) Να παρασταθεί σε χάρτη Karnaugh η λογική συνάρτηση

και να δοθεί ο πίνακας αληθείας της, αφού απλοποιηθεί.

(β) Φανταστείτε ότι είσθε μέλος μιας Ομάδας Ερευνών που πρέπει να βρείτε άμεσα όλες τις ρίζες της εξίσωσης:

Η ομάδα διαθέτει υπολογιστή σύγχρονο και ο επικεφαλής αναθέτει σε σας την ευθύνη της δουλειάς, ενώ συγχρόνως ενημερώνει ότι πρόσφατα έχει εγκατασταθεί στον Η.Υ. το Λογισμικό εφαρμογών PRAXIS που έχει την S/R:

S/R EQUAT(N,A,X,E,J)

με τις διευκρινίσεις:

Ν: Βαθμός εξίσωσης

Α: Διάνυσμα συντελεστών complex

X: Διάνυσμα ριζών (complex)

Ε: Ζητούμενη ακρίβεια

J : Το πλήθος των ριζών που βρέθηκαν (JN).

Θέμα 3. (α) Να γραφεί ένα πρόγραμμα σε συμβολική γλώσσα που να διαβάζει 20 αριθμούς και να βρίσκει το άθροισμά τους που να το τυπώνει στο μέσο εξόδου.

(β) Ο Υπουργός Οικονομικών της Χώρας έμαθε για την ποιότητα δουλειάς των φοιτητών του Μαθηματικού Τμήματος, του Πανεπιστημίου Πατρών και τους ανέθεσε την εκπόνηση ενός προγράμματος FORTRAN για τον καθορισμό του φόρου εισοδήματος που θα πληρώσουν οι φορολογούμενοι βάσει των παρακάτω οδηγιών:

ΟΔΗΓΙΕΣ ΥΠΟΥΡΓΕΙΟΥ ΟΙΚΟΝΟΜΙΚΩΝ

ΜΕΡΟΣ ΤΡΙΤΟ

ΠΡΟΣΔΙΟΡΙΣΜΟΣ ΤΟΥ ΦΟΡΟΥ – ΠΑΡΑΡΤΗΜΑΤΑ

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

Το ποσό αυτό μειώνεται, επίσης, ανάλογα με τον αριθμό των τέκνων που βαρύνουν, το φορολογούμενο ή τον άλλο σύζυγο, σύμφωνα με τις διατάξεις του άρθρου 8 του νδ. 3323/1955, ως εξής: α) με ποσοστό 30% του φόρου που αναλογεί και για ποσό μείωσης μέχρι 100.000 δρχ., αν ο φορολογούμενος βαρύνεται με τρία τέκνα, β) με ποσοστό 40% του φόρου που αναλογεί και για ποσό μείωσης μέχρι 200.000 δρχ., αν ο φορολογούμενος βαρύνεται με τέσσερα τέκνα, γ) με ποσοστό 50% του φόρου που αναλογεί και για ποσό μείωσης μέχρι 400.000 δρχ., αν ο φορολογούμενος βαρύνεται με πέντε τέκνα και πάνω.

ΚΛΙΜΑΚΑ ΦΟΡΟΛΟΓΙΑΣ ΕΙΣΟΔΗΜΑΤΟΣ

ΦΥΣΙΚΩΝ ΠΡΟΣΩΠΩΝ ΟΙΚΟΝ. ΕΤΟΥΣ 1992

Κλιμάκιο Εισοδήματος	Φορ/κός συντ/στής (%)	Φόρος κλιμακίου	Σύνολο εισοδ/τος	Σύνολο Φόρου
1.200.000	18	216.000	1.200.000	216.000
1.800.000	30	540.000	3.000.000	756.000
4.500.000	43	1.935.000	7.500.000	2.691.000
Υπερβάλλον	50

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

{Υπόδειξη: Θεωρήσατε ότι έχετε N(input) τον αριθμό φορολογουμένων και ότι για τον καθένα θα σας δίδεται συνολικό εισόδημα (INC), το συνολικό αφορολόγητο ποσό (AFOR), όπως επίσης ο αριθμός των τέκνων (NCHIL), που βαρύνουν το φορολογούμενο. Τέλος λάβατε τις παρακάτω περιπτώσεις φορολογουμένων και εκτυπώσατε το φόρο τους (TAX)}.

INC	AFOR	NCHIL	TAX
900000	45000	1	…
4425000	1020000	2	…
3800000	722000	3	…
6850000	2100000	5	…

Τελικό Τεστ

Εισαγωγή στην Επιστήμη των Ηλεκτρονικών Υπολογιστών

Τμήμα (α)

Τελική Εξέταση – 27.2.2004

Θέμα 1.

(α) Δίδεται ο αριθμός του δεκαεξαδικού συστήματος: FDCB₁₆, και ζητείται να μετατραπεί στο οκταδικό σύστημα αρίθμησης. Όμοια για τον αριθμό 1453.129₁₀ να μετατραπεί στο οκταδικό. Τέλος δώσατε τους πρώτους 20 ακέραιους αριθμούς του οκταδικού συστήματος αρίθμησης.

(β) Γράψατε ένα πρόγραμμα σε όποια γλώσσα επιθυμείται που να διαβάζει και ένα πραγματικό αριθμό με 5 το πολύ ακέραια και ισάριθμα το πολύ δεκαδικά ψηφία και να βρίσκει τον αντίστοιχο αριθμό του δυαδικού συστήματος. Τέλος, επιβεβαιώσατε τον αλγόριθμο του προγράμματός σας στον αριθμό 1453.129₁₀.

Θέμα 2.

(α) Δώσατε τους ορισμούς των: Μικροεντολή, Μκροκώδικας, Ελέγχουσα Μνήμη και Μικροπρογραμματισμός, καθώς επίσης και την δομή της Μικροεντολής.

(β) Στην πρατιθέμενη μονάδα (ALU) Αριθμητικής και Λογικής, πρόκειται να δημιουργηθεί ο μικροκώδικας της εντολής:

"Δεκαπενταπλασιασμός του περιεχομένου του καταγραφέα Α".

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

E, S₁, S₂, Cp₁ και Cp₂

που πρέπει να εκδοθούν.

Θέμα 3.

(α) Πρόκειται να μεταδοθούν αριθμητικά δεδομένα κωδικοποιήμενα σε BCD Κώδικα με τη φυσική κωδικοποίηση (8,4,2,1) και με άρτια ισοτιμία (even parity). Ζητείται να δοθεί ο πίνακας αληθείας του bit της άρτιας ισοτιμίας καθώς και το βέλτιστο κύκλωμα που το δημιουργεί. Τέλος, ποια είναι η λογική συνάρτηση του bit άρτιας ισοτιμίας;

(β) Σε κάποια ομάδα ερευνών που εσείς συμμετέχετε από κάποιο "ατύχημα", καταστρέφεται ένα κομμάτι του λογισμικού με συνέπεια ο Compiler της FORTRAN να μην μπορεί να υπολογίσει την εκθετική συνάρτηση EXP(X) που ως γνωστόν δίδει την τιμή της .

Έτσι, η ομάδα καταφεύγει σε σας, σαν ειδικευμένο Μαθηματικό και σας ζητάει να δημιουργήσετε εσείς μια συνάρτηση με όμοιο όνομα:

EXP(X,N)

και παραμέτρους την τιμή του Χ και το πλήθος Ν των όρων της σειράς που πρέπει να ληφθούν υπόψη για τον υπολογισμό με την ακρίβεια που απαιτείται.

Δώστε τον κώδικα σε FORTRAN της συνάρτησης EXP(X,N) – Χ και Ν δεδομένα – που υπολογίζεται από την

Λύσεις Θεμάτων

Τεστ 1

Εισαγωγή στην Επιστήμη των Ηλεκτρονικών Υπολογιστών

Τμήμα (α)

Ενημερωτικό 1^ο Test (Ανακεφαλαιωτικό Οκτωβρίου)

Απαντήσεις

1. α. Πίνακας μετατροπών (βλέπε σελίδα 81 του Βιβλίου Ε.Ε.Η.Υ.: μετατροπή βάσεως)

0	1	3	7	15	31	62	125	251	502	1004	2009
1	1	1	1	1	0	1	1	0	0	1	<2>

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

γ. Για τη μετατροπή του δυαδικού στο δεκαεξαδικό χωρίζω από δεξιά προς τα αριστερά σε τετραψήφια τμήματα και αντικαθιστώ την τιμή τους (ψηφίο δεκαεξαδικού), οπότε έχουμε: 7D9

0	1	3	7	15	31	62	125	251	502	1004	2009
1	1	1	1	1	0	1	1	0	0	1	<2>

2. Για να βρούμε το μέγεθος της μνήμης του αρκεί να βρούμε το μεγαλύτερο αριθμό που μπορεί να παραστήσει ο MAR κι αυτός είναι όταν όλα τα bits του MAR είναι 1. Δηλαδή,

1111 1111 1111 1111 = 2¹⁶– 1

Άρα το μέγεθος της μνήμης θα είναι 2¹⁶– 1 = 65535

3. Μετατρέπουμε την απόλυτη τιμή του δυαδικού αριθμού στο δυαδικό σύστημα. Οπότε έχουμε:

0	0	1	3	7	15	31	62	125	250	500	1001	2003
0	1	1	1	1	1	0	1	0	0	1	1	<2>

Του προσθέτουμε και το bit του πρόσημου στην αρχή: 0, και μετατρέπουμε τα bits στο σύστημα 2 παίρνοντας τα συμπληρώματά τους, οπότε έχουμε:

Και τέλος προσθέτουμε ένα, οπότε έχουμε

- 2003 = 100000101101

4. Aπό το πρώτο bit, που είναι 1, συμπεραίνουμε ότι ο αριθμός είναι αρνητικός. Στη συνέχεια αντιστρέφουμε τα bits και προσθέτουμε ένα, οπότε παίρνουμε τον αριθμό 00000001.

Άρα ο αριθμός είναι ο -1.

5. Τα ψηφία του δωδεκαδικού συστήματος θα είναι: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, Α, Β. Άρα οι 15 πρώτοι αριθμοί θα είναι:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, Α, Β, 10, 11, 12

6. Φτιάχνουμε πρώτα το πίνακα αληθείας του αθροίσματος

Υ₁+ Υ₂+ Κ

Υ₁	Υ₂	Κ	Σ	Κ_out
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Στη συνέχεια παίρνουμε τις γραμμές του πίνακα όπου το κρατούμενο out έχει τιμή 1 (έγχρωμες γραμμές). Οπότε, δημιουργούμε τη συνάρτηση

Τέλος παριστάνουμε τους όρους του δευτέρου μέλους (ελάχιστοι όροι) στον πίνακα Karnaugh, οπότε έχουμε

		Υ₂
		1₁_ος
Υ₁	1_2ος	1_4ος	1_3ος
	Κ

Το βέλτιστο κύκλωμα δίνεται από το ακόλουθο σχήμα

Τέλος, οι χαρακτηριστικοί αριθμοί της λογικής συνάρτησης Κ_out είναι οι:

και

7. Εξάγονται οι αριθμοί 37, 32, 27, 22, 17, 12, 7, 2.

8. Για να είναι οικουμενική η πύλη NAND θα πρέπει οι πύλες NOT, AND και OR να κατασκευάζονται μόνο από την NAND.

Η πύλη NOT προκύπτει από την πύλη NAND ως εξής:

A	A	AND	NAND
0	0	0	1	1
1	1	1	0	0

Δηλαδή: Α NAND Α =

Η πύλη AND προκύπτει από την πύλη NAND ως εξής:

A	B	NAND		AND
0	0	1	0	0
0	1	1	0	0
1	0	1	0	0
1	1	0	1	1

Δηλαδή:

Η πύλη OR προκύπτει από την πύλη NAND ως εξής:

A	B					OR
0	0	1	1	1	0	0
0	1	1	0	0	1	1
1	0	0	1	0	1	1
1	1	0	0	0	1	1

Δηλαδή:

9. α. Θα έχει 2⁴ γραμμές από το 0000 έως το 1111.

β. Άρα θα έχουμε 4 γραμμές ελέγχου.

10. Ο πίνακας αληθείας της φυσικής κωδικοποίησης είναι ο:

A	B	C	D	P'
0	0	0	0	1
0	0	0	1	0
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	1
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1

Οπότε το parity bit (περιττής ισοτιμίας) θα είναι εκείνο που θα κάνει των δυαδικών μονάδων του κάθε ψηφίου να είναι περιττό. Άρα, θα έχουμε τον παραπάνω πίνακα για το P'. Βάση των γνωστών παίρνουμε τις γραμμές που έχουν για το P' τιμή 1 και δημιουργούμε την αντίστοιχη συνάρτηση

και η παράστασή της στον χάρτη Karnaugh θα είναι

			C
	1^ος		2^ος
		3^ος		4^ος	Β
Α					Β
Α		5^ος
		D

Δεν υπάρχουν διαδοχικές μονάδες, άρα δεν μπορεί να γίνει απλοποίηση στη λογική συνάρτηση P'. Το λογικό κύκλωμα είναι:

11. Τα βήματα του αλγορίθμου είναι τα ακόλουθα

1. Διάβασε τους αριθμούς I και J

2. Αν το Ι = J τότε ο ΜΚΔ = Ι = J, άλλως, βρες τον μεγαλύτερο από τους I και J και θέσε K το μεγαλύτερο και L το μικρότερο.

3. Διαίρεσε το Κ με το L και θέσε το υπόλοιπο ίσο με R

4. Αν R = 0 τότε ο ΜΚΔ=L, αλλιώς θέσε Κ = L και L = R και πήγαινε στο βήμα 3.

Τεστ 2

Εισαγωγή στην Επιστήμη των Ηλεκτρονικών Υπολογιστών

Τμήμα (α)

2^ο Test Μηνός – 11.12.2003

Απαντήσεις

1. Ο παρακάτω κώδικας είναι για μία τετράδα, κι ο αλγόριθμος που μπορεί να αξιοποιηθεί είναι συγκρίνω τους δύο πρώτους, το πιο μεγάλο τον βάζω σε μία 5^η θέση BIG και τον μικρότερο σε μία 6^η θέση SMALL. Στη συνέχεια συγκρίνω κάθε έναν από τους επόμενους αριθμούς με τη θέση BIG και τη θέση SMALL και κάνω αντικαταστάσεις όπου πρέπει.

Παρατήρηση: Το πλήθος των αριθμών μπορεί να είναι οποιοδήποτε κι όχι μόνο τέσσερα.

0	INA A	Εισάγουμε στο συσσωρευτή(Σ) Α το πλήθος των αριθμών (4)
1	STA Α49	Αποθηκεύουμε το περιεχόμενο του Σ Α στην θέση μνήμης 49
2	BZE A7	Αν το περιεχόμενο του Σ A είναι 0, πήγαινε στο 7
3	INA B	Εισάγουμε στο Σ Β έναν αριθμό
4	STA B 49A	Αποθηκεύουμε το περιεχόμενο του Σ Β στην θέση μνήμης 49+Α, όπου Α το περιεχόμενο του Σ Α
5	SUB A#1	Αφαιρούμε από το Σ Α, 1 μονάδα
6	JMP 2	Πήγαινε στο 2
7	LDA A 49	Φόρτωσε το περιεχόμενο της θέσης μνήμης 49 στο Σ Α
8	LDA B 49A	Φόρτωσε το περιεχόμενο της θέσης μνήμης 49+Α στο Σ Β
9	STA B 100	Αποθηκεύουμε το περιεχόμενο του Σ Β στην θέση μνήμης 100 (BIG)
10	SUB A#1	Αφαιρούμε από το Σ Α, 1 μονάδα
11	SUB B 49A	Αφαίρεσε από το Σ Β το περιεχόμενο της θέσης μνήμης 49+Α
12	BMI B16	Αν το περιεχόμενο του Σ Β είναι αρνητικό τότε πήγαινε στο 15
13	LDA B 49A	Φόρτωσε το περιεχόμενο της θέσης μνήμης 49+Α στο Σ Β
14	STA B 200	Αποθηκεύουμε το περιεχόμενο του Σ Β στην θέση μνήμης 200 (SMALL)
15	JMP 20	Πήγαινε στο 20
16	LDA B 100	Φόρτωσε το περιεχόμενο της θέσης μνήμης 100 στο Σ Β
17	STA B 200	Αποθηκεύουμε το περιεχόμενο του Σ Β στην θέση μνήμης 200 (SMALL)
18	LDA B 49A	Φόρτωσε το περιεχόμενο της θέσης μνήμης 49+Α στο Σ Β
19	STA B 100	Αποθηκεύουμε το περιεχόμενο του Σ Β στην θέση μνήμης 200 (BIG)
20	SUB A#1	Αφαιρούμε από το Σ Α, 1 μονάδα
21	BZE A32	Αν το περιεχόμενο του Σ A είναι 0, πήγαινε στο 7
22	LDA B 49A	Φόρτωσε το περιεχόμενο της θέσης μνήμης 49+Α στο Σ Β
23	SUB B 100	Αφαίρεσε από το Σ Β το περιεχόμενο της θέσης μνήμης 49+Α
24	BMI B27	Αν το περιεχόμενο του Σ Β είναι αρνητικό τότε πήγαινε στο 27
25	LDA B 49A	Φόρτωσε το περιεχόμενο της θέσης μνήμης 49+Α στο Σ Β
26	STA B 100	Αποθηκεύουμε το περιεχόμενο του Σ Β στην θέση μνήμης 100 (BIG)
27	LDA B 49A	Φόρτωσε το περιεχόμενο της θέσης μνήμης 49+Α στο Σ Β
27	SUB B 200	Αφαίρεσε από το Σ Β το περιεχόμενο της θέσης μνήμης 200
28	BPL B31	Αν το περιεχόμενο του Σ Β είναι θετικό τότε πήγαινε στο 31
29	LDA B 49A	Φόρτωσε το περιεχόμενο της θέσης μνήμης 49+Α στο Σ Β
30	STA B 200	Αποθηκεύουμε το περιεχόμενο του Σ Β στην θέση μνήμης 200 (SMALL)
31	JMP 20	Πήγαινε στο 20
32	LDA B 100	Φόρτωσε το περιεχόμενο της θέσης μνήμης 100 στο Σ Β
33	OUT B	Δώσε ως έξοδο το περιεχόμενο του Σ Β
34	LDA B 200	Φόρτωσε το περιεχόμενο της θέσης μνήμης 200 στο Σ Β
35	OUT B	Δώσε ως έξοδο το περιεχόμενο του Σ Β
36	HLT

program sorting

dimension k(1000)

read *, (k(i),i=1,1000)

do i = 1, 999

do j = i+1, 1000

if ( k(i) < k(j) ) then

ihelp = k(i)

k(i) = k(j)

k(j) = ihelp

endif

enddo

print *,"Τμήμα Μαθηματικών-Sorting of numbers"

print 10, (k(i),i=1,1000)

10 format (1000(I10,/))

end program sorting

3.Το όλο έργο εκτελείται σε τρεις φάσεις, που είναι:

· H πρώτη φάση είναι η λεκτική ανάλυση (Lexical analysis) κατά την οποία το πρόγραμμα διασπάται σε μια σειρά λέξεων.

· H δεύτερη φάση είναι η συντακτική ανάλυση (Syntactical analysis) στην οποία ελέγχεται η γραμματική του προγράμματος.

· Τέλος, η τρίτη φάση είναι η δημιουργία του κώδικα της γλώσσας μηχανής (Code generαtion) ο οποίος θα εκτελεστεί, τελικά, από τον H. Y.

Η σύνδεση της συντακτικής ανάλυσης με την λεκτική ανάλυση γίνεται με την μεταφορά των τριών πινάκων:

· Του πίνακα των αριθμών (number table),

· Του πίνακα των διαφόρων ακολουθιών χαρακτήρων (string table),

· Και του πίνακα λογικών μονάδων (token table).

4. Δεν είναι αποδεκτή διότι ανάμεσα στις παρενθέσεις δεν υπάρχει τελεστής

– (Α + Β)(Α + (Α*Β) + C) + A

Τεστ 3

Εισαγωγή στην Επιστήμη των Ηλεκτρονικών Υπολογιστών

Τμήμα (α)

Test Εξαμήνου – 22.1.2004

Απαντήσεις

Θέμα 1. (α).

(i) Κώδικας Χ-3

1000100110000111

Χωρίζουμε το δυαδικό αριθμό: 1000-1001-1000-0111

Μορφή Χ-3	Δυαδική μορφή	Δεκαδική μορφή
1000	0101	5
1001	0110	6
1000	0101	5
0111	0100	4

Άρα, παριστά τον αριθμό 5654

(i) Κώδικας Gray

Ο κανόνας που διέπει την μετατροπή ενός 4-ψήφιου δυαδικού αριθμού από κωδικοποίηση Gray σε φυσική κωδικοποίηση (8,4,2,1) και αντίστροφα είναι ο ακόλουθος: Άφησε το πιο σημαντικό ψηφίο του αριθμού το ίδιο. Για κάθε επόμενο ψηφίο, έλεγξε το πλήθος των δυαδικών μονάδων στα αριστερά του που υπάρχουν στον κώδικα Gray: εάν είναι άρτιο άφησε το υπάρχον ψηφίο, άλλως πάρε το συμπλήρωμά του. Παράδειγμα:

Από Δυαδικό σε Gray		Από Gray σε δυαδικό
Δ =>	G	G =>	Δ
1001	----	1001	----
	1		1
	11		11
	110		111
	1101		1110

1000100110000111

Χωρίζουμε το δυαδικό αριθμό: 1000-1001-1000-0111

Μορφή Gray	Δυαδική μορφή
1000	Αφήνουμε το πρώτο ψηφίο ως έχει	1_ _ _	1111
	Το επόμενο ψηφίο 1000 έχει περιττό πλήθος μονάδων αριστερά του. Άρα γίνεται 1.	11_ _
	Το επόμενο ψηφίο 1000 έχει περιττό πλήθος μονάδων αριστερά του. Άρα γίνεται 1.	111_
	Το επόμενο ψηφίο 1000 έχει περιττό πλήθος μονάδων αριστερά του. Άρα γίνεται 1.	1111

Μορφή Gray	Δυαδική μορφή
1001	Αφήνουμε το πρώτο ψηφίο ως έχει	1_ _ _	1110
	Το επόμενο ψηφίο 1001 έχει περιττό πλήθος μονάδων αριστερά του. Άρα γίνεται 1.	11_ _
	Το επόμενο ψηφίο 1001 έχει περιττό πλήθος μονάδων αριστερά του. Άρα γίνεται 1.	111_
	Το επόμενο ψηφίο 1001 έχει περιττό πλήθος μονάδων αριστερά του. Άρα γίνεται 0.	1110

Μορφή Gray	Δυαδική μορφή
0111	Αφήνουμε το πρώτο ψηφίο ως έχει	0_ _ _	0101
	Το επόμενο ψηφίο 0111 έχει άρτιο πλήθος μονάδων αριστερά του. Άρα μένει 1	01_ _
	Το επόμενο ψηφίο 0111 έχει περιττό πλήθος μονάδων αριστερά του. Άρα γίνεται 0.	010 _
	Το επόμενο ψηφίο 0111 έχει άρτιο πλήθος μονάδων αριστερά του. Άρα μένει 1.	0101

Μορφή Gray	Δυαδική μορφή	Δεκαδική μορφή
1000	1111	15
1001	1110	14
1000	1111	15
0111	0101	5

Άρα, παριστά τον αριθμό 1514155

Ο αριθμός είναι αρνητικός λόγω της μονάδας που βρίσκεται στην αρχή του αριθμού. Βρίσκουμε το συμπλήρωμα του αριθμού 1000100110000111 και προσθέτουμε μια δυαδική μονάδα:

που είναι ο αριθμός 30329.

(β). Για να είναι οικουμενική η πύλη NAND θα πρέπει οι πύλες NOT, AND και OR να κατασκευάζονται μόνο από την NAND.

Η πύλη NOT προκύπτει από την πύλη NAND ως εξής:

A	A	AND	NAND
0	0	0	1	1
1	1	1	0	0

Δηλαδή: Α NAND Α =

Η πύλη AND προκύπτει από την πύλη NAND ως εξής:

A	B	NAND		AND
0	0	1	0	0
0	1	1	0	0
1	0	1	0	0
1	1	0	1	1

Δηλαδή:

Η πύλη OR προκύπτει από την πύλη NAND ως εξής:

A	B					OR
0	0	1	1	1	0	0
0	1	1	0	0	1	1
1	0	0	1	0	1	1
1	1	0	0	0	1	1

Δηλαδή:

Για την ακόλουθη συνδυαστική διάταξη:

Προκύπτει ο παρακάτω πίνακας αληθείας:

A	B	C	D
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Θέμα 2. Ο χάρτης Karnaugh της λογικής συνάρτησης

θα είναι ο ακόλουθος:

			C
			10^ος	11^ος
	12^ος	9^ος	5^ος	8^ος	Β
Α	6^ος	3^ος	1^ος	2^ος	Β
Α			4^ος	7^ος
		D

Η απλοποίηση των όρων 1, 2, 3, 5, 6, 8, 9, και 12 μας δίνει Β και η απλοποίηση των όρων 1, 2, 4, 5, 7, 8, 10 και 11 μας δίνει C. Συνεπώς:

Ο αντίστοιχος πίνακας αληθείας θα είναι ο:

Α	Β	F
0	0	0
0	1	1
1	0	1
1	1	1

(β)

program application_of_praxis

complex :: A(0:100), X(100)

read *, n,e

read *, (A(i),i=0,n)

call equat(n,A,X,e,j)

print *, (X(i),i=1,j)

end program application_of_praxis

Θέμα 3. (α). Το πρόγραμμα θα είναι το εξής:

0 ΙΝΑ Α

1 STA A 200

2 STA 100#0

3 BZE Α 9

4 INA B

5 ADD B 100

6 STA B 100

7 SUB A #1

8 JMP 3

9 OUT B

10 HLT

Εισάγουμε στο συσσωρευτή(Σ) Α το πλήθος των αριθμών

Αποθηκεύουμε το περιεχόμενο του Σ Α στην θέση μνήμης 200

Αποθηκεύουμε το 0 στη θέση μνήμης 100

Αν το περιεχόμενο του Σ Α είναι 0 πήγαινε στο 9

Εισάγουμε στο Σ Β ένα αριθμό

Προσθέτουμε στο Σ το περιεχόμενο της μνήμης 100

Αποθηκεύουμε το περιεχόμενο του Σ Α στην θέση μνήμης 100

Αφαιρούμε από το Σ Α μία μονάδα

Πήγαινε στο 3

Εκτύπωσε στο μέσο εξόδου το περιεχόμενο του Σ Β

Τέλος

(β)

program forologia

integer :: klim(3)

real :: tax(2)

write(*,5);read *, n

do j = 1, n

read *, inc, afor, nchill

klim(1) = 216000;klim(2) = 540000;klim(3) = 1935000

do i = 1, 2

if (inc < 1200000) then

tax(i) = inc*0.18

else if (inc < 3000000) then

tax(i) = klim(1) + (inc - 1200000)*0.3

else if (inc < 7500000) then

tax(i)=klim(1)+klim(2)+(inc-3000000)*0.43

else

tax(i)=klim(1)+klim(2)+klim(3)+(inc-7500000)*0.5

endif

inc = afor

enddo

finaltax = tax(1) - tax(2)

posomeiosis = 0

if (nchil == 3) then

posomeiosis = finaltax*0.3

if (posomeiosis > 100000) posomeiosis = 100000

else if (nchil == 4) then

posomeiosis = finaltax*0.4

if (posomeiosis > 200000) posomeiosis = 200000

else if (nchil >= 5) then

posomeiosis = finaltax*0.5

if (posomeiosis > 400000) posomeiosis = 400000

endif

finaltax = finaltax - posomeiosis

write(*,40), j, finaltax

enddo

40 format (2/,"O sunolikos foros poy kaleitai na plirosei &

o",i2,"os forologoumenos einai:",2/,30x,F12.2," drx.",5/)

end program forologia

Τελικό Τεστ

Εισαγωγή στην Επιστήμη των Ηλεκτρονικών Υπολογιστών

Τμήμα (α)

Τελική Εξέταση – 27.2.2004

Θέμα 1.

(α).

Ο αριθμός από το δεκαεξαδικό μετατρέπεται πρώτα στο δυαδικό και μετά στο οκταδικό

FDCB₁₆= 1111 1101 1100 1011₂ = 1111110111001011₂ = 176713₈

Ο αριθμός από το δεκαδικό μετατρέπεται στο οκταδικό:

Το ακέραιο μέρος το βρίσκουμε κάνοντας διαδοχικές διαιρέσεις με το 8 και το δεκαδικό κάνοντας διαδοχικούς πολλαπλασιασμούς με το 8.

0	2	22	181	1453
2	6	5	5	<8>

0,129	0,0320	0,2560	0,0480	0,3840	0,0720	0,5760	0,6080	0,8640	0,9120	0,2959	0,3672	0,9375	0,5000	0,0000
<8>	1	0	2	0	3	0	4	4	6	7	2	2	7	4

1453.129₁₀ = 2265,10203044672274

Οι 20 πρώτοι αριθμοί του οκταδικού συστήματος είναι:

0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22, 23

(β)

program dectobin

dimension :: ibinary(1000)

read *, dec

if (dec>99999 .or. dec<0) stop 'The number has more than 5 digits .or. it is not an integer'

adec = int(dec)

k=0

do while(adec/=0)

b=mod(adec,2.0)

k=k+1

adec=int(adec/2.0)

ibinary(k)=b

enddo

do i = k, 1, -1

print 10, ibinary(i)

enddo

print 25

k=0

bdec = dec - int(dec)

do while(bdec/=int(bdec))

b=bdec*2.0

k=k+1

bdec=b - int(b)

ibinary(k)=int(b)

enddo

do i = 1, k

print 10, ibinary(i)

enddo

print 20

10 format (i1,\)

25 format (",",\)

20 format (5/)

end program dectobi

Θέμα 2.

(α) Για τους ορισμούς βλέπε φυλλάδιο 6^ης εβδομάδας (5.11.03) όπου υπάρχει αναλυτική παρουσίαση των ερωτημάτων του θέματος

(β) Ο πίνακας των απαιτούμενων μεταφορών για την υλοποίηση της εντολής "Δεκαπενταπλασιασμός του περιεχομένου του καταγραφέα Α" είναι

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

Μεταφορά	Ε	S₁	S₂	Cp₁	Cp₂
	–	0	1	0	1
	0	1	0	1	0
	0	1	0	1	0
	1	1	0	1	0
	0	1	0	0	1
	1	1	0	1	0

Θέμα 3.

(α) Ο πίνακας αληθείας της φυσικής κωδικοποίησης είναι ο:

A	B	C	D	P
0	0	0	0	0
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	1
0	1	0	1	0
0	1	1	0	0
0	1	1	1	1
1	0	0	0	1
1	0	0	1	0

Οπότε το parity bit (περιττής ισοτιμίας) θα είναι εκείνο που θα κάνει το πλήθος των δυαδικών μονάδων του κάθε ψηφίου να είναι άρτιο. Άρα, θα έχουμε τον παραπάνω πίνακα για το P. Βάση των γνωστών παίρνουμε τις γραμμές που έχουν για το P τιμή 1 και δημιουργούμε την αντίστοιχη συνάρτηση

και η παράστασή της στον χάρτη Karnaugh θα είναι

			C
		1^ος		2^ος
	3^ος		4^ος		Β
Α					Β
Α	5^ος
		D

Δεν υπάρχουν διαδοχικές μονάδες, άρα δεν μπορεί να γίνει απλοποίηση στη λογική συνάρτηση P. Το λογικό κύκλωμα είναι:

(β)

program exponent

external expn

print *, exp(2.0),expn(2.0,25)

end program exponent

function expn(x,n)

external par

expn = 0.0

do k = 0, n

expn = expn + x**k/par(k)

enddo

end function expn

function par(k)

par = 1

if (k==0) return

do i = 1, k

par = par*i

enddo

end function par