[Συστήματα Υπολογιστών]Θέματα Εξετάσεων

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[12:00-13:30]

Η γραμματεία είναι ανοιχτή καθημερινά 12:00-13:30

[Silvershot]

αν γίνεται να εξηγησει καποιος τι παιζει με τις διευθυνσεις της ram γενικα θα ημουν ευγνωμων..πιο δυσκολο κομματι δε παιζει να υπαρχει σε ολο το βιβλιο

Σωστα τo εθεσες  

[Godhatesusall]

Εχετε δικιο παιδια εκανα λαθος για τη γ αλλα συμφωνα με αυτη τη λογικη δεν ειναι και η δ υλοποιησιμη αλλα με μεγαλη σπαταλη;

Γι'αυτο εγραψα και "gimme a fuckin' break".Γιατι σπαταλας 1014 διευθυνσεις...

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

Πρωτου εξαμηνου μαθημα ειναι.Νταξ' τι να ζητησει πια?Αναλυση αλγοριθμων ειναι θαρρω μαθημα των ηλεκτρονικαριων,μεγαλο εξαμηνο.Μαθε ο,τι εχει στο φυλλαδιο του(οσα απ αυτα καταλαβαινονται δλδ γιατι κι εγω σαν καλος ενεργειακος το προβλημα "εχω ρεστα" δε το πιασα και πολυ)

To προβλημα εχω ρεστα παλευεται..Αυτο που δε παλευεται ειναι η ταξη μεγεθους Aν το καταλαβε καποιος ας γραψει, μπας και το πιασουμε κ μεις !

EDIT: Οταν μας το ειχε πει με τα ρεστα το ειχα καταλαβει αλλα τωρα που το ξαναδιαβαζω δε καταλαβαινω χριστο

Λοιπόν,έχουμε και λέμε

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

Βλέποντας όλα τα for, τα if, τους πολλαπλασιασμούς κτλ μπορούμε να βρούμε πόσο χρονοβόρος είναι ένας αλγόριθμος. Συνήθως το μέτρο της σύγκρισης είναι ο αριθμός (n) των εισόδων (πίνακας με 128 στοιχεία n=128 κοκ)

Άρα ένας απλός αλγόριθμος όπως ο εξής(σε matlab)

for  ι=0:1:n
    Χ= Χ+1;

προσθέτει σε κάθε επανάληψη την μονάδα στο Χ. Προς το παρών, ας θεωρήσουμε την πράξη Χ=Χ+1 σαν μία πράξη(ότι δηλαδή εκτελείται σε έναν κύκλο μηχανής και δεν έχω καθυστέρηση μέχρι να φέρω τον αριθμό αυτό από την μνήμη, να τον επεξεργαστώ και μετά να τον γράψω)

Σε κάθε επανάληψη του for, ο αλγόριθμος κάνει 1 μόνο πράξη. Επειδή υπάρχουν n επαναλήψεις (επαναλαμβάνω, όπου n= ο αριθμός των εισόδων. Στο πρόβλημα μας το n θα μπορούσε πχ να είναι ο αριθμός των εφημερίδων που τυπώνονται καθημερινά) τότε ο συνολικός αριθμός των πράξεων είναι n.

Προφανώς, σε περισσότερο σύνθετα προβλήματα μπορείς να δεις ότι οι πράξεις είναι συνολικά   2*n^3+ 2*n^2 + 3n +12. Στις περιπτώσεις αυτές μας νοιάζει ΜΟΝΟ η απόκριση του αλγορίθμου σε ΠΟΛΥ μεγάλες εισόδους. Προφανώς αν n=10^5 προφανώς ο όρος που επηρεάζει περισσότερο το αποτέλεσμα είναι ο n^3 και όχι οι υπόλοιπο. Άρα λέμε ότι ο αλγόριθμος είναι της τάξης του O(n^3) , πράγμα που στις σημειώσεις σας μπορεί και να το λέει ως Θ(n^3).

Τέλος, αξίζει να σημειωθεί ότι η πολυπλοκότητα του αλγορίθμου συνηθίζεται να υπολογίζεται στην χειρότερη δυνατή περίπτωση.

Αν δεν καταλάβατε τπτ, ρωτήστε.

[Godhatesusall]

αν γίνεται να εξηγησει καποιος τι παιζει με τις διευθυνσεις της ram γενικα θα ημουν ευγνωμων..πιο δυσκολο κομματι δε παιζει να υπαρχει σε ολο το βιβλιο

Η μνήμη αποτελείται από έναν αριθμό κελιών, τα οποία αποτελούνται από κάποια bits.

Για παράδειγμα, αν μια μνήμη έχει 10 κελιά των 8 bits το καθένα, η συνολική χωρητικότητα της μνήμης είναι 10*8=80 bits.

Όμως, πρέπει να υπάρχει ένας τρόπος να μπορέσει να καταλάβει η μνήμη ποιο από τα κελιά ζητά ο χρήστης κάθε φορά. Τον ρόλο αυτόν τον έχει ο adress bus που λέει στην μνήμη ποιο ακριβώς κελί θέλει ο χρήστης. Ο adress bus πρακτικά είναι ένας αριθμός από καλώδια, το καθένα από τα οποία μπορεί να έχει τιμή 0(απουσία τάσης) ή 1(παρουσία τάσης).

Έτσι λοιπόν έχουμε ένα πρόβλημα με δυαδικούς αριθμούς. Πόσα bits(=καλώδια στην περίπτωση μας) χρειάζεται μια μνήμη k κελιών στον adress bus?

Έστω μια μνήμη 500 κελιών. Επειδή όπως ξέρετε, η μνήμη μεταφέρει ένα-ένα τα κελιά (δηλαδή δεν μεταφέρει ποτέ ξεχωριστά bits που υπάρχουν μέσα στα κελιά), ο αριθμός των bits των κελιών δεν μας νοιάζει. Όμως, όπως έχετε δει μέχρι τώρα, ένας δυαδικός αριθμός n bits καλύπτει το εύρος [0, (2^n)-1]. Άρα τώρα ψάχνω πότε 2^n>500. Για n=8, 2^n= 256 και άρα δεν έχουμε αρκετά καλώδια ώστε να προσπελάσουμε όλη την μνήμη. Όμως, για n=9, 2^9=512 και άρα έχουμε αρκετά καλώδια για να προσπελάσουμε όλη την μνήμη ,και μας μένουν και μερικές θέσεις αχρησιμοποίητες.

[Silvershot]

Εχετε δικιο παιδια εκανα λαθος για τη γ αλλα συμφωνα με αυτη τη λογικη δεν ειναι και η δ υλοποιησιμη αλλα με μεγαλη σπαταλη;

Γι'αυτο εγραψα και "gimme a fuckin' break".Γιατι σπαταλας 1014 διευθυνσεις...

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

Πρωτου εξαμηνου μαθημα ειναι.Νταξ' τι να ζητησει πια?Αναλυση αλγοριθμων ειναι θαρρω μαθημα των ηλεκτρονικαριων,μεγαλο εξαμηνο.Μαθε ο,τι εχει στο φυλλαδιο του(οσα απ αυτα καταλαβαινονται δλδ γιατι κι εγω σαν καλος ενεργειακος το προβλημα "εχω ρεστα" δε το πιασα και πολυ)

To προβλημα εχω ρεστα παλευεται..Αυτο που δε παλευεται ειναι η ταξη μεγεθους Aν το καταλαβε καποιος ας γραψει, μπας και το πιασουμε κ μεις !

EDIT: Οταν μας το ειχε πει με τα ρεστα το ειχα καταλαβει αλλα τωρα που το ξαναδιαβαζω δε καταλαβαινω χριστο

Λοιπόν,έχουμε και λέμε

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

Βλέποντας όλα τα for, τα if, τους πολλαπλασιασμούς κτλ μπορούμε να βρούμε πόσο χρονοβόρος είναι ένας αλγόριθμος. Συνήθως το μέτρο της σύγκρισης είναι ο αριθμός (n) των εισόδων (πίνακας με 128 στοιχεία n=128 κοκ)

Άρα ένας απλός αλγόριθμος όπως ο εξής(σε matlab)

for  ι=0:1:n
    Χ= Χ+1;

προσθέτει σε κάθε επανάληψη την μονάδα στο Χ. Προς το παρών, ας θεωρήσουμε την πράξη Χ=Χ+1 σαν μία πράξη(ότι δηλαδή εκτελείται σε έναν κύκλο μηχανής και δεν έχω καθυστέρηση μέχρι να φέρω τον αριθμό αυτό από την μνήμη, να τον επεξεργαστώ και μετά να τον γράψω)

Σε κάθε επανάληψη του for, ο αλγόριθμος κάνει 1 μόνο πράξη. Επειδή υπάρχουν n επαναλήψεις (επαναλαμβάνω, όπου n= ο αριθμός των εισόδων. Στο πρόβλημα μας το n θα μπορούσε πχ να είναι ο αριθμός των εφημερίδων που τυπώνονται καθημερινά) τότε ο συνολικός αριθμός των πράξεων είναι n.

Προφανώς, σε περισσότερο σύνθετα προβλήματα μπορείς να δεις ότι οι πράξεις είναι συνολικά   2*n^3+ 2*n^2 + 3n +12. Στις περιπτώσεις αυτές μας νοιάζει ΜΟΝΟ η απόκριση του αλγορίθμου σε ΠΟΛΥ μεγάλες εισόδους. Προφανώς αν n=10^5 προφανώς ο όρος που επηρεάζει περισσότερο το αποτέλεσμα είναι ο n^3 και όχι οι υπόλοιπο. Άρα λέμε ότι ο αλγόριθμος είναι της τάξης του O(n^3) , πράγμα που στις σημειώσεις σας μπορεί και να το λέει ως Θ(n^3).

Τέλος, αξίζει να σημειωθεί ότι η πολυπλοκότητα του αλγορίθμου συνηθίζεται να υπολογίζεται στην χειρότερη δυνατή περίπτωση.

Αν δεν καταλάβατε τπτ, ρωτήστε.

Θα μπορουσαμε να πουμε οτι βρισκοντας τη πολυπλοκοτητα, βρισκουμε ουσιαστικα τη ταξη μεγεθους σε γενικη περιπτωση? Δηλαδη, στο παραδειγμα με την ταξινομηση, η πολυπλοκοτητα που ισουται με 3n^2 - 3n/2 μας δινει και τη ταξη μεγεθους που ειναι n^2 ?

[SPS]

ρε παιδιά αυτά με τις μνήμες και τα κελια που είναι στις διαφάνειες ή στο βιβλίο του Forouzan γιατί δεν τα είδα πουθενα...

[Silvershot]

Ουσιαστικα ο αριθμος των κελιων ισουται με το συνολο των διαφορετικων συνδυασμων που φτιαχνουν τα n bit. Δηλαδη θελουμε το 2^n να ειναι >= του αριθμου των κελιων. Και προφανως αν ισχυει αυτη η σχεση τοτε χριαζομαστε n καλωδια για τη μεταφορα των  συνδυασμων(κελιων) απο τη μνημη στη ΚΜΕ. Επισης η μεταφορα των bit του κελιου γινεται ταυτοχρονα μεσω των n καλωδιων.

Αν εχω λαθος πειτε!

[Godhatesusall]

Θα μπορουσαμε να πουμε οτι βρισκοντας τη πολυπλοκοτητα, βρισκουμε ουσιαστικα τη ταξη μεγεθους σε γενικη περιπτωση? Δηλαδη, στο παραδειγμα με την ταξινομηση, η πολυπλοκοτητα που ισουται με 3n^2 - 3n/2 μας δινει και τη ταξη μεγεθους που ειναι n^2 ?

Ναι, αν η πολυπλοκότητα είναι 3n^2 - 3n/2 τότε η τάξη μεγέθους είναι Ο(n^2)

[ultraviolet]

Στα λειτουργικα συστηματα απο τις διαλεξεις μερος 2 ειδα το παραδειγμα:
Ποια ειναι ηφυσικη διευθυνση που αντιστοιχει σε καθε μια απο τις εικονικες διευθυνσεις: 20,8200?

απαντηση
0Κ<20<4Κ -> 8Κ<χ<12Κ,αρα:
φυσικη διευθυνση:
8Κ+(20-0)=8*1024+20=8212
8Κ<8200<12Κ -> 24Κ<χ<28Κ,αρα:
φυσικη διευθυνση:
24Κ+(8200-8Κ)=24*1024+(8200-8*1024)=24584

Μηπως θ μπορουσε ν το εξηγησει καποιος
Εχει μπει ποτε κατι τετοιο?

[Silvershot]

Παιδια αν εχω γραψει σωστα την html,το θεμα με αλγοριθμο χωρις την ερωτηση με τις ιντσες( την οποια σκατωσα ), το δυαδικο και λιγο απο τις ερωτησεις θεωριας, περναω?

[athen]

Παιδια αν εχω γραψει σωστα την html,το θεμα με αλγοριθμο χωρις την ερωτηση με τις ιντσες( την οποια σκατωσα ), το δυαδικο και λιγο απο τις ερωτησεις θεωριας, περναω?

για να περασεις πρεπει να εχεις απο 45 και πανω. υπολογισε ποσο περιπου εχεις πιασει και θα δεις!
παντως αν εχεις σωστα την html, τον αλγοριθμο και το δυαδικο (και κατι απο ερωτησεις οπως λες) μαλλον περνας (λεω μαλλον γιατι δεν ξερω ποσο ακριβως επιανε το καθενα)! 

[Silvershot]

Παιδια αν εχω γραψει σωστα την html,το θεμα με αλγοριθμο χωρις την ερωτηση με τις ιντσες( την οποια σκατωσα ), το δυαδικο και λιγο απο τις ερωτησεις θεωριας, περναω?

για να περασεις πρεπει να εχεις απο 45 και πανω. υπολογισε ποσο περιπου εχεις πιασει και θα δεις!
παντως αν εχεις σωστα την html, τον αλγοριθμο και το δυαδικο (και κατι απο ερωτησεις οπως λες) μαλλον περνας (λεω μαλλον γιατι δεν ξερω ποσο ακριβως επιανε το καθενα)!  

5 επιανε η καθε μια απο τις 5 ερωτησεις θεωριας. 1 εγραψα και τις αλλες πασαλειμματα απο οτι μου κατεβαινε.

[SPS]

για να περασεις πρεπει να εχεις απο 45 και πανω.

όχι 50?

[lmassoud]

eisai sigouros panw apo 45??
kai yai thn erwthsh me thn eikona kai pixels ..pws thn kanate??

[ΚΗΜΜΥ]

45 ναι, στρογγυλοποιειται

[Silvershot]

45 ναι, στρογγυλοποιειται

Αυτο ισχυει σε ολα τα μαθηματα?