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

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

Για οποιοδήποτε πρόβλημα με register/login, στείλτε email στο contact@thmmy.gr.

[dim]

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

[Ariel]

Έχει λύσει κανείς το θέμα 3 του Φεβρουαρίου 2008?

[vasso]

Ta themata fetos itan teleia

agapame Ntelo!

[lpool]

Ta themata fetos itan teleia

agapame Ntelo!

Από ποια άποψη τέλεια? Εύκολα?

[vasso]

Ta themata fetos itan teleia

agapame Ntelo!

Από ποια άποψη τέλεια? Εύκολα?

Ναι, έτσι μου φάνηκαν. 3 μονάδες για ένα ΑΠΑ... 3 μονάδες για μία μηχανή τούρινγκ... 1 μονάδα για να πεις με λόγια στο 1β ότι δεν υπάρχει λέξη από αα που να παράγεται από τη γλώσσα ή την παράθεση με τον εαυτό της... 1 μονάδα αν θυμάμαι καλά στο 1α για να γράψεις την ίδια γλώσσα με S'->SS τον μόνο νέο κανόνα...


Δεν ήταν εύκολα; (δεν ειρωνεύομαι, ρωτάω)

[Sage]

Πιάνοντας τα πρώτα μου θέματα(Σεπτέμβρη 2003).. μου δημιουργήθηκαν κάποιες απορίες.

Α)Το α* αφορά τις συμβολοσειρές που δημιουργούνται απο e και πλήθος α. 1)Μπορεί να ξεκινάει από e; 2)Μπορεί να είναι μόνο e;

Β)Μπορεί να λύσει και κάποιος άλλος τα Σ-Λ;

Γ)Στο 3ο θέμα, α ερώτημα, μετά από κάποια βήματα δημιουργούμε σαν τελικό σύμβολο το κενό. Αυτό το διαγράφουμε στο αμέσως επόμενο βήμα που αλλάζει το τρέχον; Ή στην τελευταία μετάβαση;

[aggalitsas]

Πιάνοντας τα πρώτα μου θέματα(Σεπτέμβρη 2003).. μου δημιουργήθηκαν κάποιες απορίες.

Α)Το α* αφορά τις συμβολοσειρές που δημιουργούνται απο e και πλήθος α. 1)Μπορεί να ξεκινάει από e; 2)Μπορεί να είναι μόνο e;

Β)Μπορεί να λύσει και κάποιος άλλος τα Σ-Λ;

Γ)Στο 3ο θέμα, α ερώτημα, μετά από κάποια βήματα δημιουργούμε σαν τελικό σύμβολο το κενό. Αυτό το διαγράφουμε στο αμέσως επόμενο βήμα που αλλάζει το τρέχον; Ή στην τελευταία μετάβαση;

A) a*={{e},{a},{aa},{aaa}{aaa...}etc}  επομένως ναι και ναι.

Β)
1_Λ
2_ θα έλεγα σωστό αλλα δεν καταλαβάινω τη σημάνει τομή πολυπλοκότητας
3_Λ (δεν υπάρχει λέξη που να ξεκινάει με 2 ββα
4_Σ (στη καύτερη να είναι εα ΤΟΜΗ εα
5_Σ σελ7  σημειώσεις μέρος 2
6 no clue

Γ)δεν ειμαι σιγουρος τι ρωτας, αμα η δ δεν σου λεει τι  να κανεις για το κενο γιατι να το πειράξεις?

[Sage]

Πιάνοντας τα πρώτα μου θέματα(Σεπτέμβρη 2003).. μου δημιουργήθηκαν κάποιες απορίες.

Α)Το α* αφορά τις συμβολοσειρές που δημιουργούνται απο e και πλήθος α. 1)Μπορεί να ξεκινάει από e; 2)Μπορεί να είναι μόνο e;

Β)Μπορεί να λύσει και κάποιος άλλος τα Σ-Λ;

Γ)Στο 3ο θέμα, α ερώτημα, μετά από κάποια βήματα δημιουργούμε σαν τελικό σύμβολο το κενό. Αυτό το διαγράφουμε στο αμέσως επόμενο βήμα που αλλάζει το τρέχον; Ή στην τελευταία μετάβαση;

A) a*={{e},{a},{aa},{aaa}{aaa...}etc}  επομένως ναι και ναι.

Β)
1_Λ
2_ θα έλεγα σωστό αλλα δεν καταλαβάινω τη σημάνει τομή πολυπλοκότητας
3_Λ (δεν υπάρχει λέξη που να ξεκινάει με 2 ββα
4_Σ (στη καύτερη να είναι εα ΤΟΜΗ εα
5_Σ σελ7  σημειώσεις μέρος 2
6 no clue

Γ)δεν ειμαι σιγουρος τι ρωτας, αμα η δ δεν σου λεει τι  να κανεις για το κενο γιατι να το πειράξεις?

Thanks!! 
Όσο για το Γ, επισημαίνεται μέσα στις διαφάνειες οτι σε μια ολική κατάσταση στις ΜΤ το τελευταίο στοιχείο δεν μπορεί να είναι το "κενο", εκτός αν είναι τρέχον. Και στο συγκεκριμενο παράδειγμα σε κάποια φάση, δημιουργείται(αναγκαστικά) ένα κενό επειδή ο "κερσορας" μεταβαίνει δεξιότερα απο το τελευταίο σύμβολο που είναι καταγεγραμένο. Anyway.. αυτο δεν νομίζω οτι είναι κ μεγάλο πρόβλημα. Οπότε και να μην διευκρινιστεί δεν υπάρχει θέμα.

[aggalitsas]

μπορέι κάποιος να λύσει το  θεμα 2α ΦΕΒ 2008 ΚΜC? δεν καταλαβαίνω πως εξαλείφουμε τους κοντούς κανόνες.

έχω
S -> XSX | X | e
X -> ab | e

εξαλείφω μακριούς κανόνες
S -> XS1 | X | e
S1-> SX
X-> ab |e

προς το κενό
S-> XS1 | X
S1-> SX|S
X-> ab|e

S->XS1 | X | S1
S1-> SX | S
X-> ab

και μετα το χάνω!

[nikos912000]

Στο θέμα 3 Ιανουάριος 2002 υπάρχει απλός τρόπος για το β (ΜΑΠΑ->ΑΠΑ); Γιατί ο αλγόριθμος γενικά θέλει δουλειά!

[soso]

-Ιανουάριος 2003 Θέμα 1ο είναι Λ,Σ,Σ,Λ,Σ,Σ?

-Σεπτέμβριος 2003 Θέμα 2ο (vi)?

-Σεπτέμβριος 2002 Θέμα 3ο όταν φτάνει σε τελική κατάσταση αλλά το επόμενο στοιχείο της συμβολοσειράς δεν έχει δρόμο, θεωρείται αποδεκτή η συμβολοσειρά ή όχι? π.χ. (iv)

-Φεβρουάριος 2008 Θέμα 3ο,α) εννοεί ότι με το που ξεκινάει η ΜΤ γράφει στη πρώτη θέση το α?

-Ιανουάριος 2012 Θέμα 2ο, Α->Αα|αΒ|αα, τα | σημαίνουν  Α->Aα, Α->αΒ, Α->αα?

-Φεβρουάριος 2009, Θέμα 3ο, (δ) τί εννοεί αν είναι σαφής?

[nikos912000]

Γ)Στο 3ο θέμα, α ερώτημα, μετά από κάποια βήματα δημιουργούμε σαν τελικό σύμβολο το κενό. Αυτό το διαγράφουμε στο αμέσως επόμενο βήμα που αλλάζει το τρέχον; Ή στην τελευταία μετάβαση;

Το κενό δεν το δημιουργείς... Σκέψου απλά ότι μετά το τέλος της συμβολοσειράς σου υπάρχουν "σκουπίδια" ή αλλιώς κενά!

[Sage]

Στο θέμα 3 Ιανουάριος 2002 υπάρχει απλός τρόπος για το β (ΜΑΠΑ->ΑΠΑ); Γιατί ο αλγόριθμος γενικά θέλει δουλειά!

Έχω στο συνημμένο την λύση(πιστεύω οτι είναι σωστή)..

-Ιανουάριος 2003 Θέμα 1ο είναι Λ,Σ,Σ,Λ,Σ,Σ?

Λ,Σ,Σ,Λ,Λ,Λ Τα έβαλα, χωρίς να είμαι απόλυτος.
Πάντως αν ίσχυε το v) τότε δε θα καθόταν να αποδείξει στο βιβλίο σε τόσες σελίδες πως η έκφραση aⁿbⁿ δεν είναι κανονική.

-Σεπτέμβριος 2003 Θέμα 2ο (vi)?

Και γω το χω απορία..

-Σεπτέμβριος 2002 Θέμα 3ο όταν φτάνει σε τελική κατάσταση αλλά το επόμενο στοιχείο της συμβολοσειράς δεν έχει δρόμο, θεωρείται αποδεκτή η συμβολοσειρά ή όχι? π.χ. (iv)

Επίσης το χω απορία, γέρνω στο οτι δεν θεωρείται αποδεκτή.

-Φεβρουάριος 2008 Θέμα 3ο,α) εννοεί ότι με το που ξεκινάει η ΜΤ γράφει στη πρώτη θέση το α?

-Ιανουάριος 2012 Θέμα 2ο, Α->Αα|αΒ|αα, τα | σημαίνουν  Α->Aα, Α->αΒ, Α->αα?

-Φεβρουάριος 2009, Θέμα 3ο, (δ) τί εννοεί αν είναι σαφής?

Δεν ασχολήθηκα ακόμα με τα καινούρια θέματα, μόνο με του 11(τα παλούκια).
Αύριο πρωί με τα υπόλοιπα..

[Sage]

μπορέι κάποιος να λύσει το  θεμα 2α ΦΕΒ 2008 ΚΜC? δεν καταλαβαίνω πως εξαλείφουμε τους κοντούς κανόνες.

έχω
S -> XSX | X | e
X -> ab | e

εξαλείφω μακριούς κανόνες
S -> XS1 | X | e
S1-> SX
X-> ab |e

προς το κενό
S-> XS1 | X
S1-> SX|S
X-> ab|e

S->XS1 | X | S1
S1-> SX | S
X-> ab

και μετα το χάνω!

Ως προς το κενό νομίζω ξέχασες το S1->X..
ανεβάζω πάλι ενδεικτικά την λύση μου.

Το πρώτο θέμα το έχεις λύσει; Πως λύνεται;

[τσαι-borg]

Μια ερώτηση μιας και το έγραψες, αφού S->e και X->e, S1->SX δεν είναι προς το κενό?