Εργασια Sudoku

Όταν ανεβάζουμε φωτογραφίες στις Ανακοινώσεις και Έκτακτα νέα, βάζουμε τη μεγαλύτερη πλευρά 400 (width=400 ή height=400 ). π.χ. [img height=400 (κλείνει η αγκύλη)

THMMY.gr > Forum > Μαθήματα Βασικού Κύκλου > 3ο Εξάμηνο > Δομές Δεδομένων (Moderators: chatzikys, Tasos Bot, tzortzis) > Εργασια Sudoku

0 Members and 1 Guest are viewing this topic.

Pages: 1 [2] 3

Author

Topic: Εργασια Sudoku (Read 6568 times)

golden

Θαμώνας

Gender:

Posts: 392

Απ: Εργασια Sudoku

« Reply #15 on: December 02, 2005, 16:00:38 pm »

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


	Logged

dim

Honoured Member
Μόνιμος κάτοικος ΤΗΜΜΥ.gr

Gender:

Posts: 1564

finding emo

Απ: Εργασια Sudoku

« Reply #16 on: December 02, 2005, 16:07:42 pm »

Sorry!!!

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


	Logged

chggr005

Αbsolute ΤΗΜΜΥ.gr

Gender:

Posts: 2566

Free ...as a bird (Beatles)

Re: Εργασια Sudoku

« Reply #17 on: December 04, 2005, 03:52:34 am »

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


	Logged

Goodbye to you, my trusted friend.
We've known each other since we were nine or ten.
Together we 've climbed hills or trees.
Learned of love and ABC's,
skinned our hearts and skinned our knees.

Goodbye my friend, it's hard to die,
when all the birds are singing in the sky,
Now that the spring is in the air.
Ο λογαριασμός έχει παραβιαστεί, μην ανοίξετε το link. are everywhere.
When you see them I'll be there.

We had joy, we had fun, we had seasons in the sun.
But the hills that we climbed
were just seasons out of time.

Terry Jacks - Seasons In The Sun

Οι πρωτοετείς φοιτητές μπορούν να ενημερωθούν για τον Σύλλογο Φοιτητών Ηλεκτρολόγων Μηχανολόγων Μηχανικών από εδώ: Σύλλογος Φοιτητών

golden

Θαμώνας

Gender:

Posts: 392

Απ: Εργασια Sudoku

« Reply #18 on: December 04, 2005, 05:40:03 am »

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


	Logged

chggr005

Αbsolute ΤΗΜΜΥ.gr

Gender:

Posts: 2566

Free ...as a bird (Beatles)

Re: Εργασια Sudoku

« Reply #19 on: December 05, 2005, 13:43:14 pm »

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


	Logged

Terry Jacks - Seasons In The Sun

JAs0n-X

Αbsolute ΤΗΜΜΥ.gr

Gender:

Posts: 2861

Rhodes [Sattelite image]

Απ: Εργασια Sudoku

« Reply #20 on: December 05, 2005, 17:51:00 pm »

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


	Logged

J=X
--------------------------------------------
Ο Χριστος πεθανε
Ο Μαρξ πεθανε...
και εγω τελευταια δεν αισθανομαι καλα !

BOBoMASTORAS

Veteran
Καταστραμμένος

Posts: 6082

It just doesn't get any easier! It gets worse...

Απ: Εργασια Sudoku

« Reply #21 on: December 05, 2005, 20:05:58 pm »

Quote from: golden on December 04, 2005, 05:40:03 am

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

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


	Logged

Της γενιάς μου βασιλιά,
μην κατέβεις τα σκαλιά.
Πιες αθάνατο νερό
να νικήσεις τον καιρό.

http://tools.ietf.org/html/rfc1149
The only reason we invent robots

gfloros

Guest

Απ: Εργασια Sudoku

« Reply #22 on: December 05, 2005, 22:00:40 pm »

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

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

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


	Logged

BOBoMASTORAS

Veteran
Καταστραμμένος

Posts: 6082

It just doesn't get any easier! It gets worse...

Απ: Εργασια Sudoku

« Reply #23 on: December 05, 2005, 22:39:52 pm »

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


	Logged

chggr005

Αbsolute ΤΗΜΜΥ.gr

Gender:

Posts: 2566

Free ...as a bird (Beatles)

Re: Εργασια Sudoku

« Reply #24 on: December 06, 2005, 07:26:34 am »

Quote from: BOBoMASTORAS on December 05, 2005, 20:05:58 pm

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

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


	Logged

Terry Jacks - Seasons In The Sun

BOBoMASTORAS

Veteran
Καταστραμμένος

Posts: 6082

It just doesn't get any easier! It gets worse...

Απ: Εργασια Sudoku

« Reply #25 on: December 07, 2005, 00:48:16 am »

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


	Logged

chggr005

Αbsolute ΤΗΜΜΥ.gr

Gender:

Posts: 2566

Free ...as a bird (Beatles)

Re: Εργασια Sudoku

« Reply #26 on: December 07, 2005, 01:39:10 am »

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


	Logged

Terry Jacks - Seasons In The Sun

dim

Honoured Member
Μόνιμος κάτοικος ΤΗΜΜΥ.gr

Gender:

Posts: 1564

finding emo

Απ: Εργασια Sudoku

« Reply #27 on: December 07, 2005, 13:16:28 pm »

Quote from: dim

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

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

Quote from: chggr005 on December 07, 2005, 01:39:10 am

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

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

)

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


	Logged

lars

Θαμώνας

Gender:

Posts: 419

Απ: Εργασια Sudoku

« Reply #28 on: December 07, 2005, 19:57:50 pm »

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


	Logged

abc

Καταξιωμένος/Καταξιωμένη

Gender:

Posts: 209

Go get a life

Re: Απ: Εργασια Sudoku

« Reply #29 on: December 07, 2005, 21:43:57 pm »

Quote from: lars on December 07, 2005, 19:57:50 pm

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

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

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

Με πιάνετε; Kiss


	Logged

Στράααατόοοο...

Pages: 1 [2] 3

Jump to: