Εργασια Sudoku

[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 με προσοχή στα ονόματα των αρχείων!

[Admins]

Για αλλαγή του public name σας, επικοινωνήστε με έναν από τους Admins.

[golden]

Στο παράδειγμα που έδωσα γιατι Ο(n^2) κι όχι O(n^4)? Συγνώμη αν γίνομαι κουραστικός αλλά είναι το μόνο που μου έχει μείνει για να αφιερωθώ επιτέλους στα σήματα!!

[dim]

Sorry!!!

Λάθος βιασύνης!
Ο(n^4)

[chggr005]

Παιδιά, είστε σίγουροι ότι η πολυπλοκότητα είναι Ο(n^4)? Εγώ διαφωνώ εν μέρει με αυτό.

[golden]

Η πολυπλοκότητα σίγουρα θα προκύψει διαφορετική αν έχεις ακολουθήσει διαφορετικό αλγόριθμο για την εξέταση του sudoku! Πόσο την υπολογίζεις εσυ?(περιέργεια!)

[chggr005]

Ναι, τελικά μετά από λίγη σκέψη, χαρτί και μολύβι, προέκυψε ότι βγαίνει n τετράγωνο. Πάντως νομίζω ότι όλοι οι φοιτητές χρησιμοποίησαν πάνω κάτω τον ίδιο αλγόριθμο.

[JAs0n-X]

ο οποιος ειναι?
εγω ξερω οτι αλλοι χρησιμοποιησαν αθροισματογινομενα...
αλλοι ενα boolean πινακακι μονοδιαστατο με 9 κουτια...(οπως εγω)...
εσεις τι χρησιμοποιησατε τελικα..
εμενα ο κωδικας της checkSudokuMatrix βγηκε 50 γραμμες που νομιζω ειναι αρκετα ικανοποιητικο (γεια σου τρικουπη με το συμαζεμα σου! )...
εκανε κανεις καμμια τρελη πατεντα να μας την πει να τον θαυμασουμε?

[BOBoMASTORAS]

Η πολυπλοκότητα σίγουρα θα προκύψει διαφορετική αν έχεις ακολουθήσει διαφορετικό αλγόριθμο για την εξέταση του sudoku! Πόσο την υπολογίζεις εσυ?(περιέργεια!)

Εγώ θα διατυπώσω λίγο διαφορετικά την ερώτηση.

Τι συμβολίζει το n???

[gfloros]

Μπορεί κανένα παλικάρι να ανεβάσει την εκφώνηση της εργασίας;

Χαιρετίσματα από τα ελληνικά στρατά...
Να κοιμάστε ήσυχοι!

Ο στρατιώτης Flo

[BOBoMASTORAS]

ορίστε
εργασία μέρος Α

[chggr005]

Τι συμβολίζει το n???

To n λογικά συμβολίζει την διάσταση του πίνακα (δεδομένου ότι είναι τετραγωνικός)

[BOBoMASTORAS]

Δηλαδή μπορούμε να πούμε ότι ένας πίνακας Sudokou με 10 γραμμές θέλει περίπου 10^2=100 πραξεις για να επαληθευτεί. Έτσι δεν είναι???

[chggr005]

Όχι! Απλά η τάξη ενός αλγορίθμου (Ο) σου δίνει ένα μέτρο σύγκρισης μεταξύ δύο αλγορίθμων και δεν μπορείς να βγάλεις συμπεράσματα αυτού του είδους.
Για παράδειγμα ένας αλγόριθμος τάξης n^4 θα είναι χειρότερος (θέλει περισσότερο χρόνο εκτέλεσης) από έναν τάξης n^2.
Ο αριθμός των εντολών που χρειάζεται δεν είναι 100. Για να τον βρεις θα πρέπει να κάνεις πράξεις, οι οποίες θα καταλήγουν σε μία μορφή πχ 45n^2 + 10n +2345. Στην παράσταση αυτή εάν βάλεις n=10 θα βρεις τον αριθμό των εντολών που χρειάζονται για να επαληθευτεί ο πίνακας.

[dim]

Απʼ ότι φαίνεται στην επόμενη σελίδα, τα βήματα που απαιτούνται είναι
15N²+N+4  βήματα
Άρα έχουμε Ο( Ν2 ) πολυπλοκότητα.

To παραπάνω είναι από την εργασία..
Ο πραγματικός αριθμός των βημάτων δεν είναι Ν².
Η πολυπλοκότητα είναι απλά ο βαθμός του πολυωνύμου που δίνει τον αριθμό των βημάτων.
Και μάλιστα το πολυώνυμο που βγάλαμε σε αυτή την εργασία για τον αριθμό των βημάτων είναι πολύ.."στο περίπου"

Όχι! Απλά η τάξη ενός αλγορίθμου (Ο) σου δίνει ένα μέτρο σύγκρισης μεταξύ δύο αλγορίθμων και δεν μπορείς να βγάλεις συμπεράσματα αυτού του είδους.
Για παράδειγμα ένας αλγόριθμος τάξης n^4 θα είναι χειρότερος (θέλει περισσότερο χρόνο εκτέλεσης) από έναν τάξης n^2.

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

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

Αν κάποιος έχει διαφορετική άποψη θα ήταν ενδιαφέρον να την έλεγε..

[lars]

Η μελέτη της πολυπλοκότητας αναφέρεται στη γενικότερη περίπτωση όπου τότε το Ν->οο 
Για να δεις ποιος αλγόριθμος είναι καλύτερος για συγκεκριμένο αριθμό,αρκεί να συγκρίνεις τις γραφικές παραστάσεις των πολυπλοκοτήτων των 2 αλγορίθμων.Και πάλι τα πράγματα όμως είναι σχετικά για την περιπτωση των Ο() πολυπλοκοτήτων μιας που αυτές δίνουν το άνω όριο για τον χρόνο εκτέλεσης των αλγορίθμων(στην περίπτωση δλδ που θα εκτελεστούν όλες οι εντολές).Για να συγκρίνεις 2 αλγόριθμους με συγκεκριμένο μέγεθος εισόδου,πρέπει να κάνεις μελέτη μέσης περίπτωσης και ακόμα καλύτερα να υπολογίζεις το χρόνο εκτέλεσης για διάφορες εισόδους.

[abc]

Η μελέτη της πολυπλοκότητας αναφέρεται στη γενικότερη περίπτωση όπου τότε το Ν->οο 
Για να δεις ποιος αλγόριθμος είναι καλύτερος για συγκεκριμένο αριθμό,αρκεί να συγκρίνεις τις γραφικές παραστάσεις των πολυπλοκοτήτων των 2 αλγορίθμων.Και πάλι τα πράγματα όμως είναι σχετικά για την περιπτωση των Ο() πολυπλοκοτήτων μιας που αυτές δίνουν το άνω όριο για τον χρόνο εκτέλεσης των αλγορίθμων(στην περίπτωση δλδ που θα εκτελεστούν όλες οι εντολές).Για να συγκρίνεις 2 αλγόριθμους με συγκεκριμένο μέγεθος εισόδου,πρέπει να κάνεις μελέτη μέσης περίπτωσης και ακόμα καλύτερα να υπολογίζεις το χρόνο εκτέλεσης για διάφορες εισόδους.

Πολύ ωραία η παρατήρηση

Και γω να προσθέσω το εξής παράδειγμα:

Αν ένα πρόγραμμα ελέγχει τυχαίους πίνακες nxn για το αν είναι sudoku ή όχι τότε η αντιμετώπιση της πολυπλοκότητας θα είναι εντελώς διαφορετική στην περίπτωση που ήλεγχε πίνακες οι οποίοι συμπληρώθηκαν από μία ομάδα φοιτητών του ΤΗΜΜΥ.

Με πιάνετε;