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

theoni

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

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2321
Κάθε συγκριτικός ή λογικός τελεστής θεωρείται πράξη
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

theoni

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

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Η δυαδική στη χειρότερη περίπτωση είναι ασύγκριτα ταχύτερη από τη σειριακή στη μέση περίπτωση. Συγκρίνεις το ν/2 με το log2ν

GB

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

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

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 838
Καλημέρα σε όλους

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

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

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

καμιά ιδέα ??

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

Diotima

  • Επισκέπτης
Καλημέρα σε όλους

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

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

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

καμιά ιδέα ??

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

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

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

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

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

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

Diotima

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

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

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

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

Diotima

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

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

ολγα

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

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

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

ολγα

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

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

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

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

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

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

lsourtzo

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



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


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