[Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες

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

[Δείτε περισσότερα εδώ...]

Συμβουλές καλής χρήσης του φόρουμ: Youtube embed code and links, Shoutbox, Notify, ...

Δείτε περισσότερα εδώ...

[Niobe]

Ποσο περηφανος θα ηταν ο Turing για σας ρε μαγκες... 

[Andromedas]

Η λογική μου φαίνεται σωστή. Αρκεί όμως για όλο το σύνολο των αναδρομικά απαριθμησιμων γλωσσών; Η εννοεί για τις αναδ απαρ από το συγκεκριμένο Σ;
Αν γίνεται να ανεβάσεις τις ΜΤ που χρησιμοποιριε για κάθε μια ενωση, παραθεση, Kleene  συγκεκριμένα θα βοηθούσε.

2 Ερώτημα έχουμε βρει κάνα τρόπο με να ελέγχουμε εάν μια ΓΧΣ είναι σαφής;

[Κηπουρίδης]

Η λογική μου φαίνεται σωστή. Αρκεί όμως για όλο το σύνολο των αναδρομικά απαριθμησιμων γλωσσών; Η εννοεί για τις αναδ απαρ από το συγκεκριμένο Σ;
Αν γίνεται να ανεβάσεις τις ΜΤ που χρησιμοποιριε για κάθε μια ενωση, παραθεση, Kleene  συγκεκριμένα θα βοηθούσε.

2 Ερώτημα έχουμε βρει κάνα τρόπο με να ελέγχουμε εάν μια ΓΧΣ είναι σαφής;

Για ολες, δε χρησιμοποιησα κατι σχετικο με το Σ για την αποδειξη  .

Γενικα το προβλημα που αναφερεις ειναι undecidable (με αναγωγη απ το PCP αν σε ενδιαφερει περα απ τους σκοπους της εξετασης).
Αυτο δεν ειναι κατι τρομακτικο βεβαια. Σημαινει απλως οτι δεν υπαρχει συστηματικος τροπος να το βρουμε για οποιαδηποτε ΓΧΣ.
Μπορουμε ομως για την συγκεκριμενη ΓΧΣ που θα δωσει να βγαλουμε συμπερασματα, μονο που δεν υπαρχει μεθοδολογια (και δε μπορει να υπαρξει μαλιστα, σε τετοιες αποδειξεις ειναι η ομορφια ολου του μαθηματος). Προσπαθεις να το αποδειξεις μονος σου. ΠΧ μπορει να δεις οτι μονο ενα συγκεκριμενο non-terminal symbol μπορει να παραξει καποιο γραμμα, και να πατησεις σε αυτο το γεγονος για να χτισεις την αποδειξη σου. Αν στειλεις συγκεκριμενο θεμα μπορω να σου απαντησω, αλλα οπως ξαναειπα μπορει αυτο να μη βοηθησει καθολου αφου δεν μπορει να υπαρξει συστηματικος τροπος.

Υ.Γ.: Δεν καταλαβα τι ειπες με τις διαφανειες, δε νομιζω να εχει ανεβασμενο κατι σχετικο ο Ντελο.

[SolidSNK]

Ρίξτε και μια ματιά και σε παλαιότερη απόπειρα μου.

απο φεβ. 14 το 3ο θεμα πως λυνεται;   

Για το α) και το β) υπάρχουν αρκετοί τρόποι. Εξαρτάται τι ακριβώς θέλει από σένα. Μπορείς να πεις από τη θεωρία πως γνωρίζουμε πως κάθε κανονική γλώσσα είναι αναδρομική, αλλά δε νομίζω να ζητάει αυτό. So, θα σου πρότεινα τόσο το α) όσο και το β) να το πας κατασκευαστικά. Το μεν α) σχεδιάζοντας μια TM από το εκφυλισμένο FSA που αποφασίζει τη γλώσσα, ενώ για το μεν β) νομίζω έχω ήδη ποστάρει παλαιότερα τη λύση σε τέτοια θέματα: υπέθεσε πως έχεις 2 TM που αποφασίζουν τις L1 και L2, με την L3 να δέχεται την έξοδο τους και να εκτελεί OR, συνάρτηση που προφανώς είναι αναδρομική.

Για το γ) είμαι σίγουρος πως θέλει κάτι αυστηρό. So be it. Αρχικά, υπέθεσε ένα αλφάβητο και πες ότι η τετριμμένη γλώσσα που αποτελείται από ένα μόνο γράμμα του αλφαβήτου (π.χ. La={a}) είναι αναδρομική. Δε νομίζω να χρειάζεται εξήγηση αυτό, άμα θες να είσαι τέρμα αυστηρός φτιάξε τη χαζή TM που αναγνωρίζει το γράμμα. Εφόσον δίνεται πως το σύνολο των ανδρομικών γλωσσών είναι κλειστό προς αυτές τις πράξεις, τότε η κλειστότητα των τετριμμέννων {a}, {b}, {c}... γλωσσών με τις συγκεκριμένες πράξεις θα είναι επίσης αναδρομικές γλώσσες. Όμως σύμφωνα με τον ορισμό (δες κεφάλαιο "Πεπερασμένη αναπαράσταση των γλωσσών" από το βιβλίο), αυτή η κλειστότητα είναι το σύνολο των κανονικών γλωσσών ως προς το συγκεκριμένο αλφάβητο. Άρα κάθε κανονική γλώσσα είναι αναδρομική.

Εχει λαθος αυτο που εγραψες στο (β). Κι αυτο επειδη λεγοντας να παρεις το OR δυο πραγματων χωρις να πεις τον τροπο με τον οποιο θα το παρεις μπορει να πεσεις σε infinite loop (προυποθετεις εσωτερικα χωρις να το εχεις πει οτι τα TM θα τερματισουν, χωρις αυτο απαραιτητα να ισχυει ομως). Πρεπει οπωσδηποτε να γινει η (σειριακη) παραλληλοποιηση ωστε ακομα κι αν ενα σπασιμο w1w2 ειναι αποτυχημενο, να μην επηρεασει τα υπολοιπα σπασιματα που μπορει να τερματισουν.

Όχι, δεν προυποθέτω ότι τα ΤΜ θα τερματίσουν.

Η διαδικασία που περιέγραψες είναι το dovetailing. Όπως θα ξέρεις, χρησιμοποιείται για να αποδείξει την αναδρομική απαριθμησιμότητα ενός άλλου, πολύ σημαντικού, συνόλου (νομίζω το αναφέρει το βιβλίο του παπαδημητρίου στο 5 (?)). Δεν είναι απαραίτητη εδώ όμως. Αν το επιθυμείς, I can elaborate more.

[Andromedas]

πχ   2014 φεβρουαριος θεμα 2 διαισθάνομαι ότι είναι σαφής αλλά δεν μπορώ να το πω με κάποια διατύπωση

Υ.Γ.: Δεν καταλαβα τι ειπες με τις διαφανειες, δε νομιζω να εχει ανεβασμενο κατι σχετικο ο Ντελο.

είπα για διαφάνειες κάτι;

[Κηπουρίδης]

Όχι, δεν προυποθέτω ότι τα ΤΜ θα τερματίσουν.

Η διαδικασία που περιέγραψες είναι το dovetailing. Όπως θα ξέρεις, χρησιμοποιείται για να αποδείξει την αναδρομική απαριθμησιμότητα ενός άλλου, πολύ σημαντικού, συνόλου (νομίζω το αναφέρει το βιβλίο του παπαδημητρίου στο 5 (?)). Δεν είναι απαραίτητη εδώ όμως. Αν το επιθυμείς, I can elaborate more.

Εννοειται ρε, αν υπαρχει πιο απλος τροπος πες το, εγω δε μπορεσα να σκεφτω κατι.
Αυτο που ειπα ειναι οτι η πραξη OR πρεπει να διευκρινισουμε πως θα εφαρμοστει. Αν πχ παρουμε (στην ενωση) και προσομοιωσουμε με την TM1 μεχρι να παρουμε απαντηση, κι αν παρουμε απαντηση YES (αφου εχουμε or) ενω αν δεν παρουμε συνεχιζουμε να το προσομοιωνουμε, τοτε αν το TM2 αποδεχεται ενω το TM1 μπαινει σε infinite loop δε θα παρουμε ποτε απαντηση, ενω υπαρχει.
Εν ολιγοις συμφωνω με το OR, το θεμα μου ειναι οτι πρεπει να εφαρμοστει με τροπο που να μην κολλαει σε μια αποτυχημενη προσπαθεια (στο παραδειγμα πανω προσομοιωση με TM1).

Andromedas:
Ο,τι να ναι καταλαβα, Turing Machine μαλλον εννοουσες με το MT; Ειναι παρα πολυ παιδεμα να το ορισουμε πληρως και δεν υπαρχει λογος, αφου γνωριζουμε οτι ειναι πληρως ισοδυναμα με καθε γλωσσα προγραμματισμου. + οτι ο Ντελοπουλος ειναι μορφη, αν δει οτι καταλαβες δεν υπαρχει περιπτωση να κοψει επειδη δεν ηταν αυστηρη η αποδειξη.

[SolidSNK]

Όχι, δεν προυποθέτω ότι τα ΤΜ θα τερματίσουν.

Η διαδικασία που περιέγραψες είναι το dovetailing. Όπως θα ξέρεις, χρησιμοποιείται για να αποδείξει την αναδρομική απαριθμησιμότητα ενός άλλου, πολύ σημαντικού, συνόλου (νομίζω το αναφέρει το βιβλίο του παπαδημητρίου στο 5 (?)). Δεν είναι απαραίτητη εδώ όμως. Αν το επιθυμείς, I can elaborate more.

Εννοειται ρε, αν υπαρχει πιο απλος τροπος πες το, εγω δε μπορεσα να σκεφτω κατι.
Αυτο που ειπα ειναι οτι η πραξη OR πρεπει να διευκρινισουμε πως θα εφαρμοστει. Αν πχ παρουμε (στην ενωση) και προσομοιωσουμε με την TM1 μεχρι να παρουμε απαντηση, κι αν παρουμε απαντηση YES (αφου εχουμε or) ενω αν δεν παρουμε συνεχιζουμε να το προσομοιωνουμε, τοτε αν το TM2 αποδεχεται ενω το TM1 μπαινει σε infinite loop δε θα παρουμε ποτε απαντηση, ενω υπαρχει.
Εν ολιγοις συμφωνω με το OR, το θεμα μου ειναι οτι πρεπει να εφαρμοστει με τροπο που να μην κολλαει σε μια αποτυχημενη προσπαθεια (στο παραδειγμα πανω προσομοιωση με TM1).

Andromedas:
Ο,τι να ναι καταλαβα, Turing Machine μαλλον εννοουσες με το MT; Ειναι παρα πολυ παιδεμα να το ορισουμε πληρως και δεν υπαρχει λογος, αφου γνωριζουμε οτι ειναι πληρως ισοδυναμα με καθε γλωσσα προγραμματισμου. + οτι ο Ντελοπουλος ειναι μορφη, αν δει οτι καταλαβες δεν υπαρχει περιπτωση να κοψει επειδη δεν ηταν αυστηρη η αποδειξη.

Ναι η αλήθεια είναι δεν έμπλεξα με αυστηρούς μηχανικούς όρους και το άφησα έτσι μετέωρο. Ουσιαστικά μίλησα για 3 μηχανές που τρέχουν παράλληλα. Από πλευράς υπολογισιμότητας δεν αλλάζει απολύτως τίποτα έτσι, αλλά άμα ήταν να το ορίσω αυστηρά τότε... dovetailing it is hoohoo.

[Κηπουρίδης]

πχ   2014 φεβρουαριος θεμα 2 διαισθάνομαι ότι είναι σαφής αλλά δεν μπορώ να το πω με κάποια διατύπωση

Υ.Γ.: Δεν καταλαβα τι ειπες με τις διαφανειες, δε νομιζω να εχει ανεβασμενο κατι σχετικο ο Ντελο.

είπα για διαφάνειες κάτι;

Απλως παιρνουμε το κειμενο που θελουμε να ελεγξουμε αν ανηκει στη γραμματικη, βλεπουμε το πρωτο γραμμα του, και αντικαθιστουμε το S με τη μοναδικη παραγωγη που γενναει σαν πρωτο γραμμα αυτο που θελουμε (ευκολη η αποδειξη οτι μονο αυτη η επιλογη στεκει). Συνεχιζουμε με αυτο τον τροπο και αποδεχομαστε μονο εαν τελειωσουμε το κειμενο ΚΑΙ τελειωσουμε και τα S ταυτοχρονα.

Αφου σε καθε βημα ειχαμε μονο μια επιλογη, η γραμματικη ειναι σαφης.

[Andromedas]

Θεμα 3 φλεβαρης 13
Τσεκάρετε άμα ισχύει η λύση μου ,ο τύπος για τις κλάσεις κανονικών γλωσσών είναι στην σελ 83 παπα
Πλσ ποστ για διορθώσεις. Ευχαριστώ!

[Niobe]

Το θεμα 2β του Φλεβαρη '14 ειναι ιδιο με το 2β του Σεπτεμβρη '15

Εχει κανεις καμια ιδεα για το πως λυνονται?? Γενικα πως εξεταζω οτι μια γραμματικη ειναι ασαφης

[Andromedas]

Το θεμα 2β του Φλεβαρη '14 ειναι ιδιο με το 2β του Σεπτεμβρη '15

Εχει κανεις καμια ιδεα για το πως λυνονται?? Γενικα πως εξεταζω οτι μια γραμματικη ειναι ασαφης

Φλεβαρη '14 ειναι ιδιο με το 2β του Σεπτεμβρη '15 ειναι το ιδιο
Απαντήθηκε παραπάνω.

[Niobe]

Το θεμα 2β του Φλεβαρη '14 ειναι ιδιο με το 2β του Σεπτεμβρη '15

Εχει κανεις καμια ιδεα για το πως λυνονται?? Γενικα πως εξεταζω οτι μια γραμματικη ειναι ασαφης

Φλεβαρη '14 ειναι ιδιο με το 2β του Σεπτεμβρη '15 ειναι το ιδιο
Απαντήθηκε παραπάνω.

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

Παιζει να ειναι και δυσκολο να πεσει αφου μπηκε το σεπτεμβρη

[Andromedas]

Απαντήθηκε, δεν υπάρχει απόδειξη...  Άρα περιγραφικά.

[Niobe]

Απαντήθηκε, δεν υπάρχει απόδειξη...  Άρα περιγραφικά.

GG

Δεν ειχα δει την απαντηση..

[MrsHofstadter]

Παιδιά, στο θέμα 2/Φεβρουάριος 2013, όταν ζητάει να σχεδιάσουμε αυτόματο στοίβας που αποδέχεται τη γλώσσα L και μας έχει δώσει και το ΜΑΠΑ για την L, πώς βρίσκουμε το αυτόματο στοίβας; Υπάρχει κάπου συγκεκριμένα στη θεωρία ο τρόπος;