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

[theoni]

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

[petrosp13]

Κάθε συγκριτικός ή λογικός τελεστής θεωρείται πράξη

[theoni]

Εννοώ πως θα γίνει η σύγκριση μετάξυ δυαδικής και σειριακής ;;;;θα υπολογίσουμε πόσες πράξεις εκτελεί η σειριακή για ν=5 ας πουμε  θα υπολογίσουμε και τις πραξείς της δυαδικής και θα δούμε ποιά απο τις δυο εκτελεί περισσότερες πράξεις;;;

[gpapargi]

Η δυαδική στη χειρότερη περίπτωση είναι ασύγκριτα ταχύτερη από τη σειριακή στη μέση περίπτωση. Συγκρίνεις το ν/2 με το log₂ν

[GB]

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

[Λαμπράκης Μανώλης]

Καλημέρα σε όλους

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

Αν χ>0 τότε, και όχι Αν χ>=0 τότε .... άραγε ο τελεστής >= πόσες πράξεις είναι ??

1) μία πράξη ??
2) δύο πράξεις  (μία κάθε συγκριτικός τελεστής) ??
3) τρεις πράξεις (μία κάθε συγκριτικός τελεστής και μία το Η που γίνεται), όπως παρατήρησε κάποιος μαθητής μου (εύστοχη παρατήρηση)

καμιά ιδέα ??

ευχαριστώ
κάποια ιδέα

[Diotima]

Καλημέρα σε όλους

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

Αν χ>0 τότε, και όχι Αν χ>=0 τότε .... άραγε ο τελεστής >= πόσες πράξεις είναι ??

1) μία πράξη ??
2) δύο πράξεις  (μία κάθε συγκριτικός τελεστής) ??
3) τρεις πράξεις (μία κάθε συγκριτικός τελεστής και μία το Η που γίνεται), όπως παρατήρησε κάποιος μαθητής μου (εύστοχη παρατήρηση)

καμιά ιδέα ??

ευχαριστώ
κάποια ιδέα

Εγώ θα θεωρήσω ότι γίνεται μία σύγκριση μεταξύ της τιμής μιας μεταβλητής και μιας σταθεράς και θα το υπολογίσω ως μία πράξη. Όταν λένε οι οδηγίες "σύγκριση 2 μεταβλητών" χωρίς άλλη διευκρίνηση, καταλαβαίνω ότι ισχύει για οποιοδήποτε συγκριτικό τελεστή.Τώρα το πώς μεταγλωττίζεται το >= δε μας ενδιαφέρει.

Για παράδειγμα, ακόμα κι αν γίνεται η σύγκριση χ > ψ, που φανερά θα τη θεωρήσουμε μία πράξη, μπορεί ο μεταγλωττιστής να βρίσκει τη διαφορά χ-ψ και να τη συγκρίνει με το 0 για να ελέγξει αν είναι >0. Οπότε κάνει και μία αφαίρεση, στην πραγματικότητα 2 πράξεις. Μπορεί αυτό να ισχύει και για τη συνθήκη χ>=ψ. Αυτό δεν το ξέρουμε.

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

[Λαμπράκης Μανώλης]

Και πάλι όμως πρέπει να υποθέσουμε, αυτό είναι που δεν μου αρέσει σε όλο τι κεφάλιάιο 5... αν δεν βάλουν κάτι ακριβώς μέσα από το βιβλίο τότε θα έχουμε μεγάλο θέμα...αν κάτι δεν οριζεται σαφώς στο βιβλίο τότε δεν μπορούμε να το αποδείξουμε...ας ελπίσουμε να πάνε όλα καλά με αυτό το θέμα

[Diotima]

Και πάλι όμως πρέπει να υποθέσουμε, αυτό είναι που δεν μου αρέσει σε όλο τι κεφάλιάιο 5... αν δεν βάλουν κάτι ακριβώς μέσα από το βιβλίο τότε θα έχουμε μεγάλο θέμα...αν κάτι δεν οριζεται σαφώς στο βιβλίο τότε δεν μπορούμε να το αποδείξουμε...ας ελπίσουμε να πάνε όλα καλά με αυτό το θέμα

Δε χρειάζεται να υποθέσουμε τίποτα. Βλέπουμε μία σύγκριση, άρα είναι μία πράξη.
Όπως όταν δούμε την πράξη χ*ψ θα πούμε ότι είναι μία πράξη, άσχετα αν διδάσκουμε ότι εκτελείται ο αλγόριθμος του Πολλαπλασιασμού αλά Ρωσικά στο low level.
Πρέπει να ξεφύγουμε από το επίπεδο της assembly.

[Λαμπράκης Μανώλης]

Συνάδελφε επέτρεψέ μου να διαφωνίσω λίγο στο γεγονός ότι αυτό το κεφάλαιο εξ άναγκης υποθέτουμε πράγματα ..
αν ήταν έτσι θα γνωρίζαμε σαφώς πόσες πράξεις θεωρείται η εντολή κ<--κ+1 και η πόσες εντολή κ<--λ+α .. εγώ επιμένω, μακάρι να μην πέσει κάτι περίεργο από το κεφάλαιο αυτό, γιατί τότε δεν θα ξέρουμε τι να λέμε πάλι ...

[Diotima]

Συνάδελφε επέτρεψέ μου να διαφωνίσω λίγο στο γεγονός ότι αυτό το κεφάλαιο εξ άναγκης υποθέτουμε πράγματα ..
αν ήταν έτσι θα γνωρίζαμε σαφώς πόσες πράξεις θεωρείται η εντολή κ<--κ+1 και η πόσες εντολή κ<--λ+α .. εγώ επιμένω, μακάρι να μην πέσει κάτι περίεργο από το κεφάλαιο αυτό, γιατί τότε δεν θα ξέρουμε τι να λέμε πάλι ...

Νομίζω Μανώλη ότι έχεις παρακολουθήσει τις συζητήσεις όπως εξελίχθηκαν σε αυτό το νήμα και μάλλον θα έχεις διαβάσει όσα έγραψαν όσοι συμμετείχαν και τα σεντόνια που έχω γράψει εγώ στην προσπάθεια μου να ξεδιαλύνω όσο μπορώ αυτό το κεφάλαιο.
Υποστήριξα εξ' αρχής ότι υπάρχουν κενά, ασάφειες και ελλείψεις ορισμών.
Και δε γράφω κι όλα όσα θέλω... Κανονικά δεν πρέπει να πέσει τίποτα, το έχω ξαναπεί...
Πρότεινα να χρησιμοποιηθεί απόσπασμα απ' το πρώτο κεφάλαιο γι αυτά που λες και να δοθούν οι ορισμοί που λείπουν.
Το πράγμα κατέληξε σε κάποιες οδηγίες από τον κ. Κανίδη, που όσο και ανεπίσημες κι αν είναι δίνουν ένα μπούσουλα πλέον.
Προς τιμήν του τις ανάρτησε ο Παναγιώτης Τσιωτάκης. Εγώ θα τις ακολουθήσω στο θέμα που ρωτάς. Νομίζω θα ήταν καλό να τις ακολουθήσουμε για να υπάρξει μια κοινή αντιμετώπιση, τι άλλο μπορεί να γίνει; Είμαστε λιγότερο από 2 μήνες πριν τις Πανελλαδικές. Με βάση αυτά σου απάντησα.

[ολγα]

Σύμφωνα με τις οδηγίες του κ. Κανίδη:
"Συνεπώς η αύξηση (ή μείωση) της τιμής οποιασδήποτε μεταβλητής (π.χ  x <-- x+1) υπολογίζεται ως μια πράξη ενώ αν εμπλέκονται και άλλες μεταβλητές (x <-- y+1), υπολογίζεται ως δύο."

Ερώτηση:
Το παρακάτω υπολογίζεται ως μία πράξη. Σωστά;
i<--i+5

Άρα και η αύξηση του i στην παρακάτω "Για" επίσης  υπολογίζεται ως μία πράξη;
Για i από 5 μέχρι 100 με_βήμα 5

[ολγα]

Μήπως θα μπορούσε να απαντήσει κάποιος στην ερώτησή μου;

[Λαμπράκης Μανώλης]

Σύμφωνα με τις οδηγίες του κ. Κανίδη:
"Συνεπώς η αύξηση (ή μείωση) της τιμής οποιασδήποτε μεταβλητής (π.χ  x <-- x+1) υπολογίζεται ως μια πράξη ενώ αν εμπλέκονται και άλλες μεταβλητές (x <-- y+1), υπολογίζεται ως δύο."

Ερώτηση:
Το παρακάτω υπολογίζεται ως μία πράξη. Σωστά;
i<--i+5

Άρα και η αύξηση του i στην παρακάτω "Για" επίσης  υπολογίζεται ως μία πράξη;
Για i από 5 μέχρι 100 με_βήμα 5

Καλησπέρα...έχω την εντύπωση είναι σωστές και οι δύο ερωτήσεις σου...μία πράξη και τα δύο

[lsourtzo]

Καλησπέρα.
Θα ήθελα να ρωτήσω ποια είναι η σωστή απάντηση στην ερώτηση: Ποια είναι η πολυπλοκότητα του τμήματος αλγορίθμου
Για i από 1 μέχρι n
   Για j από 1 μέχρι m
       διάβασε Α[i,j]
   Τέλος_επανάληψης
Τέλος_επανάληψης

Μα αφού στις οδηγίες λένε ότι οι μαθητές ΔΕΝ πρέπει να ασχοληθούν με τον υπολογισμό της Πολυπλοκότητας Ο
Γιατί να το ρωτήσουν αυτό ?   

τελικά θα απαντήσει κανείς σε αυτό