THMMY.gr

Topic που αφορά γενικές απορίες και ανακοινώσεις/επικαιρότητα σχετικά με το μάθημα. Stay on topic!


μπορεί να ναεβάσει κάποιος τις διαφάνειες να τις εκτυπώσουμε;

Τις ανεβάζει όλες στο ethmmy, εκτός αν τις θέλεις τώρα δηλαδή.

λέω να τις έχω για την Τετάρτη που έχουμε μάθημα :P εκτός και αν τις ανεβάσει μέχρι τότε

:-*

ευχαριστώ !!! :* :*

καλημέρα :)

παιδια τι φαση το μάθημα?? το προτεινετε να το παρω για επιλογης??

Πάρτο.

Tl;dr: Εύκολο το μάθημα, όχι πολύ διάβασμα, ειδικά αν παρακολοθείς. Δίνεις με ανοιχτά βιβλία.

Βέβαια Σεπτέμβρη μας άφησε 1 ώρα για τα όλα τα θέματα χωρίς παράταση, οπότε καλά είναι να τα ξέρεις καλά μην ξαναγίνει κάτι τέτοιο.

Ευχαριστω!! ;)

Μπορεί να πει κάποιος μέχρι πού έχει φτάσει από τις σημειώσεις του?

Την προηγούμενη φορά μπήκε στο τρίτο σετ διαφανειών...νομίζω έκανε καμια 10αριά διαφάνειες περίπου..
.ίσως και λίγο παραπάνω γιατί έφυγα μετά...

Oκ, ευχαριστώ!

Το ψήνει κανείς να αλλάξει μέρα το μάθημα;

Είμαστε πολύ από 5ο έτος που το έχουμε πάρει σαν  επιλογή για το 9ο και πέφτει μαζί με VLSI οπότε δικαιολογημένα θεωρώ πρέπει να αλλάξει

Νομίζω λογικότερο θα ήταν να αλλάξουν τα vlsi

+1 γιατί λογικά περισσότεροι είμαστε εδώ παρά στα vlsi...

+1 για αλλαγη εχω γραψει και στο τοπικ των VLSI

Αναβολή παραδόσεων Δευτέρας 11 και Τετάρτης 13 Ιανουαρίου 2016
9 Ιαν 2016 4:06 μμ
Ντελόπουλος

Λόγω προγραμματισμένης απουσίας μου στο εξωτερικό, οι παραδόσεις των ημερών Δευτέρα 11/1/16 και Τετάρτη 13/1/16 δεν θα πραγματοποιηθούν. Οι τελευταίες παραδόσεις του μαθήματος θα είναι στις 18/1/16 και 20/1/16 και θα περιλαμβάνουν ασκήσεις.

Στην εξέταση μπορούμε να έχουμε και το βιβλίο και τις σημειώσεις του;

Ό,τι θες αφήνει στις εξετάσεις

Αύριο τελικά θα κάνουμε;

Απο ότι είπαμε στο μάθημα κατάλαβα πως θα γίνει.

Υπάρχει περιπτωση να ανεβασει κανεις σημειωσεις απο τα δυο τελευταια μαθηματα?

οι διαφανειες αντιστοιχουν σε ολο το βιβλιο;;

Από το lewis-παπαδημητρίου η ύλη είναι τα πρώτα 4 κεφάλαια μόνο (γλώσσες, πεπερασμένα αυτόματα, αυτόματα στοίβας, μηχανές turing) και από αυτά όχι όλες οι παράγραφοι. Αν πας με σημειώσεις θα δεις ακριβώς τι είναι εκτός (επίσης αν δεν κάνω λάθος θα βγάλει ανακοίνωση για την ακριβή ύλη, πέρσι νομίζω έβγαλε)

Παιδιά, κάποιος/α ξέρει ακριβώς τη φετινή ύλη από Lewis γιατί βλέπω ότι είναι μέσα και κλάσεις Ρ και ΝΡ ?

Για να εχουμε ΑΠΑ, εστω οτι Σ={α,β}, πρέπει απο μία κατάσταση να οδηγούμαστε κάπου (δλδ σε μια απο τις καταστασεις που ανηκουν στο ΑΠΑ) και με το α και με το β ετσι?
Αν πχ δ(q1,α)=q2 και δεν υπαρχει το δ(q1,β) ουτε σαν να οδηγει στο κενο τοτε δεν εχουμε απα σωστα?
και αν τελικα βαλουμε το κενο πρεπει να βαλουμε και σε αυτο καταστασεις δ(κενο,α)=δ(κενο,β)=κενο?

Το ΑΠΑ δεν μπορεί να έχει εν κενώ μεταβάσεις, και πρέπει απο καθε κατασταση να φευγω και με α και με β προς τα κάπου

Στο κενο συνολο δεν θεωρειται μεταβαση?
Αυτο οταν σχηματιζουμε απο ΜΑΠΑ->ΑΠΑ
Αν δηλαδη εχω ενα κενο συνολο και μου ζητειται να χαρακτηρισω αν ειναι ΑΠΑ?

Κενο σύνολο είναι το όνομα της κατάστασης. Για να είναι ΑΠΑ οι προυποθεσεις ειναι απλές.
Από κάθε κατασταση φεύγω και με α και με β ακριβώς μια φορά. Δεν υπάρχουν μεταβάσεις εν κενώ.

cool
θενξ! :)

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

+1

 :-X
Κανενας παιχτης πλζ δωστε υλικο στους παλιους

Παίδες, να ρωτήσω κάτι ...

Έστω 2 γλώσσες L1 και L2

Η ένωση αυτών των δύο είναι το ίδιο με την παράθεση τους ?
Γενικά πιστεύω πως όχι...
Ξέρω πως η παράθεση είναι μια σ.σ απο την πρώτη γλώσσα σε σειρά με μια σ.σ απο την δεύτερη...

Αλλά μεσα στις σημειώσεις του σε κάποια φάση (εκεί με τις Κ.Ε) κάπως το υποννοεί...

εγω εχω καταλάβει ότι η ένωση είναι κάτι σαν και αυτό: 

έστω έχεις L[a U ab] τότε στο βιβλίο κάπου λέει αυτό:
"πάρε ένα α ή ένα αb", άρα λογικά είναι διαφορετικό απτην παράθεση που θα ήταν aab αυστηρά

Να ρωτήσω εγώ κάτι άλλο: Υπάρχει περίπτωση κάποιο αυτόματο να αποδέχεται μια κανονική έκφραση L[R] αλλά ταυτόχρονα να αποδέχεται και συμβολοσειρές οι οποίες δεν ανήκουν στν L[R]?

ΓΙα παράδειγμα για την L[R] = (ab*)* (που έχει πέσει και παλιότερα), εύκολα κανείς σχεδιάζει αυτόματο που αποδέχεται την (ab*)  αλλά την (ab*)* ?? δλδ να αποδεχεται τo string abbabb (που ανήκει στην L[R]) αλλά όχι το abbabbb (που δεν ανήκει στην L[R] ;;   

Πώς μπορεί να γίνει αυτό; Δλδ ουσιαστικά να μετράς τα β για να έχεις πλήρη συμμετρία; 
Μπορώ να σκεφτώ μόνο κάτι το οποίο αποδέχεται γενικά συμβολοσειρές (αβ*)* που τελειώνουν σε β αλλά έτσι θα αποδέχεται και συμβολοσειρές εκτός της L[R].

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

Τώρα για κάθε κανονική έκφραση υπάρχει αυτόματο που τη δέχεται αποκλειστικά και ο ντελό γενικά αυτό θέλει. Το παράδειγμα σου είναι τετριμμένο: σχεδιάζεις το (ab*) όπως λες και βάζεις μη ντετερμινιστικό βήμα στο τέλος να ξαναπηγαίνει στην αρχική του κατάσταση.

Σε ευχαριστώ για την απάντηση.
Κάτι τέτοιο ας πούμε;
->

(http://i68.tinypic.com/2yuzw4p.jpg)

Looking good!

Ty!

Οι περσινές ασκήσεις που ειναι στα Downloads αρκούν για να είμαστε καλυμμένοι για όλες τις περιπτώσεις θεμάτων?

Ανέβασα κάτι λυμένα θέματα απο το 2012 μέχρι και 2015. Οι λύσεις είναι ενδεικτικές, οπότε οποιαδήποτε διόρθωση ή υπόδειξη είναι ευπρόσδεκτη! Ειδικά σε μηχανές Turing και ελαχιστοποίση ΑΠΑ δεν είμαι και 100% σίγουρος για το αν ειναι σωστά αυτά που έγραψα. Θα ανέβαζα και σημειώσεις απο τα 2 τελευταία μαθήματα αλλά μου κάνει κατι κόλπα το adobe (Error: The file is damaged and could not repair).Επίσης, ελπίζω να βγαίνει άκρη με τα γράμματα που κάνω, είναι λίγο Γραμμική Β'.

Παιδια μια ερωτηση. Στις διαφάνειες και στο βιβλίο λέει ότι για να βρούμε το kleene star ενός αυτόματου, προσθέτουμε μία καινούρια κατάσταση η οποία είναι αρχική και τελική του καινούριου αυτόματου, οι τελικές καταστάσεις του παλιού αυτόματου παραμένουν τελικές και του καινούριου αυτόματου και από την νέα αρχική-τελική κατάσταση και τις τελικές καταστάσεις του παλιού αυτόματου καταλήγουμε στην παλιά αρχική κατάσταση με την e. Σε σημειώσεις από ασκήσεις του μαθήματος που βρήκα εδω αλλά και σε κάποιες άλλες που έχω, βλέπω την εξής διαφορά: ότι οι τελικές καταστάσεις του παλιού αυτόματου δεν είναι τελικές στο καινούριο αυτόματο και ότι από αυτές καταλήγουμε με την e στην καινούρια αρχική-τελική κατάσταση που προσθέσαμε.

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

Ωραίος , θα μπορούσες όμως να εξηγήσεις την διαδικασία με την οποία γεμίζεις τον πίνακα στον δυναμικό προγραμματισμό ; στο Θέμα 3ο του 2012 γιατι μπερδεύομαι απίστευτα

Νομίζω ότι για το kleene star απλά απο τις τελικές καταστάσεις πας με "e" στην αρχική, την οποία όμως αρχική την έχεις κάνει και τελική.

Θες για παράδειγμα να δεις τι θα μπει στο κελί [1,4]. Πηγαίνεις και τσεκάρεις το κελί [1,1] με το κελί [2,4], αυτα τα 2 θα σου δώσουν "α κενό". οπότε εσυ πας μετα και βλέπεις τους κανόνες της γραμματικής σου και ρωτάς υπάρχει καποιος κανόνας που μου δίνει "α κενό"? δεν υπάρχει. Οπότε συνεχίζεις με το [1,2] και τ�1,3] και [4,4] που σου δινουν "S b" και για αυτο υπάρχει κανόνας Χ->Sb. Οπότε πας και γράφεις Χ στο κελί [1,4]. Μετά συνεχίζεις και κανεις την ίδια διαδικασία με το κελί [2,5].Δηλαδή ξεκινάς απο τέρμα αριστερά και πας προς τα μέσα και απο κάτω προς τα πάνω, για να βρεις τα ζευγάρια που πρεπει να ελέγξεις για το εκάστοτε κελί.

https://www.youtube.com/watch?v=C_Nv0n6BRO0&index=1&list=PLLMmbOLFy25Gir_BIQbCgg1fMl3bauWgM

τσεκάρετε τα βιντεάκια από αυτό το κανάλι..Συγκεκριμένα τα  ΠΛΗ30 ΜΑΘΗΜΑ 3,4,5 και όλες τις ενότητες του καθενός καλύπτουν πιστεύω όλη την ύλη! Είναι πολύ βοηθητικά για κατανόηση!

γινεται μηπως να στειλεις τα 2 αλλα μαθηματα (3,4) σε πλειλιστ?? γιατι χαθηκα στο καναλι του τυπου εχει τα παντα μεσα


Επισης μια υποδειξη για το 1γ του Φλεβαρη '15, νομιζω πως ισχυει η ισοδυναμια, αφου αν παρεις ως συμβολοσειρα z την aa θα πρεπει να  ισχυει οτι η abbaa και η bbaaa ανηκουν στην L που το εδειξες στο πρωτο ερωτημα.
Αρα ισχυει και η ισοδυναμια.



Για το 2ο θεμα αν μπορει καποιος να εξηγησει το 2α θα εχει αιωνια ευγνωμοσυνη

ENOTHTA 3
https://www.youtube.com/watch?v=0Ile2JC4e5w&list=PLLMmbOLFy25G4w9Tycd4RVuVT5mLl2p70
https://www.youtube.com/watch?v=ev2lnoFfwxg&list=PLLMmbOLFy25F8mitptTWdIPr1hFnvAvSC
https://www.youtube.com/watch?v=eIA0nzm4CVQ&list=PLLMmbOLFy25ENod52DAj5o-zC6JFoC5UK
https://www.youtube.com/watch?v=3bubrvAxXJM&list=PLLMmbOLFy25FOR9VjHD6poG7V42Qfvt2k
https://www.youtube.com/watch?v=da3CHQyQMUo&list=PLLMmbOLFy25FJ8EsYzj_vJQbNPtb877ac
ΕΝΟΤΗΤΑ 4
https://www.youtube.com/watch?v=c1elpL4LVxU&list=PLLMmbOLFy25EYeXXBURCGd_oVpEjsV9ov
https://www.youtube.com/watch?v=mJe1LiEK6Co&list=PLLMmbOLFy25GnMo8toaSIypsUcAFZoXFY
https://www.youtube.com/watch?v=cGq7He-0cHw&list=PLLMmbOLFy25EjsQXcgDVurxuwkUnBmN-q
https://www.youtube.com/watch?v=K3wV7Am_pHI&list=PLLMmbOLFy25FH4dyBpu6MZDcwkPTsAb8P
https://www.youtube.com/watch?v=HvEESSEgBVo&list=PLLMmbOLFy25GnQ0ZpsIigjatnNL8CuP5L
ΕΝΟΤΗΤΑ 5
https://www.youtube.com/watch?v=C_Nv0n6BRO0&list=PLLMmbOLFy25Gir_BIQbCgg1fMl3bauWgM

Παιζει να εισαι και θεουλης  ^peace^ ^peace^

Ωραίος φίλε μου αλλά έχω μια απορία!

Είναι απο τα θέματα Ιούνη 2013  Θέμα 1 πρώτο:

Αν αληθεύει ότι abbab ∈ L[ ( (ab) U b )* ] 
γιατί είναι σωστό;

Όταν έχουμε αστεράκι και μέσα μια ένωση, τότε τι επιλογές έχουμε;
Λέμε : "πάρε ένα ab* ή ένα b* " και μετά μπορείς να ξαναπάρεις κάποιο απτα ab* b* και να το κάνεις concat με το πρώτο; 

Η ένωση είναι ένα καινούργιο σύνολο εδώ {αβ,β} άρα το * είναι όλες οι συμβολοσειρές που μπορούν να παραχθούν απ τα αβ και β (όπου τα αβ και β τα χρησιμοποιείς όσες φορές και με όποια σειρά θες).

τα θεματα σεπτεμβρη του '15 ειναι σωστα στα downloads?

θυμαται κανεις τις διορθωσεις?

εδιτ: επισης αν μπορει καποιος να πει τη διαδικασια μετατροπης απο ΜΑΠΑ σε ΑΠΑ (λιγο αναλυτικα αν γινεται)

Ναι όντως μια εξήγηση για το 2ο θεμα το 2α θα ηταν άξια ευγνωμοσύνης! Και νομίζω ότι έχεις δίκιο για την ισοδυναμία, δεν το πηρα χαμπάρι ότι απο πάνω είχε "έτοιμα" τα abbaa και bbaaa.

Μπορεί κανείς να εξηγήσει πως εξαλείφω τους κοντούς κανόνες για να έχω ΚΜC;

Ισχύει με το aa, αλλά αν δώσεις μόνο a στο bba (=bbaa) τότε αυτή η λέξη ανήκει στη γλώσσα, όμως δεν ισχύει το ίδιο για την abba. Άρα δεν ισχύει για κάθε z που ανήκει στο Σ*. Άρα δεν είναι ισοδύναμες.

το παραδειγμα αυτο το ειχε κανει στο μαθημα και ειχε πει οτι δεν ισχυει ισοδυναμια..

και νομιζω βγαινει απο την σελιδα 15 μερος 2 στις διαφανειες του..(νομιζω)

ΔΕΝ είναι ισοδύναμες διότι πρέπει να ισχύει για κάθε z, όχι μονο για ενα συγκεκριμένο, λες οτι οι Σ.Σ.  αββ και ββα οδηγούν σε μη-ισοδύναμες καταστάσεις οπότε δεν ισχύει για κάθε ζ.... --> δεν είναι ισοδύναμες

Δικιο εχετε παιδες μετα ειδα το "για καθε"

Αρα χρειαζεται να ξερω τις κλασεις ισοδυναμιας και αν ειναι ιδιες κομπλε αλλιως πουλο..

Πιστεύω το ίδιο φαίνεται και από τη στιγμή που έχεις κατασκευάσει το ελάχιστο ΑΠΑ. Αν ήταν ισοδύναμες οι bba και abb, τότε και οι καταστάσεις στις οποίες καταλήγουν θα ήταν ισοδύναμες, και έτσι το ελάχιστο θα έπρεπε να έχει μόνο δύο καταστάσεις, αντί για τρεις.

υπαρχει περιπτωση να εχετε βρει κανα video, παραδειγμα που να τα εξηγει?? γιατι δε βγαζω ακρη...

το κριτηριο αντλησης τι ειναι?

Μπορούμε να έχουμε και δικές μας σημειώσεις μαζί πχ λυμένα θέματα?

Ναι οτι θες

Στο 2ο θέμα τι βγάλατε για τη συμβολοσειρά? Ανήκει ή δεν ανήκει?

δεν ανήκει

thx man

6 μερούλες φουλ φτάνουν;

Χαλαρουιτα

 :-*

Αλλαγή ημερομηνίας εξέτασης ΘΥΑ

9 Σεπ 2016 12:15 μμ
Ντελόπουλος

Η επαναληπτική εξέταση του μαθήματος ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΩΝ ΚΑΙ ΑΛΓΟΡΙΘΜΩΝ θα πραγματοποιηθεί τη Δευτέρα 3/10/16 και ώρα 19:00 αντί της Τρίτης 20/9/16 που είχε προγραμματιστεί. Ζητώ την κατανόησή σας για την αλλαγή αυτή.

επειδη δυσκολευομαι διαβασε κανεις απο αλλου για το ελαχιστο απα και τις κλασεις ισοδυναμιας να μου πει μηπως και νιωσω πως τις βρισκω ?

+1

παιδες, δεν εχω δηλωμένο το μάθημα, αλλά θέλω να το δώσω.. Γνωρίζει κανείς αν ο Ντελόπουλος κρατάει βαθμούς?? έστειλα μαιλ αλλά δεν έχει απαντήσει

Λογικα δεν θα στο κρατησει :(
Ο Niobe το περασε αλλα δεν το ειχε δηλωσει κ τον εβαλε να ξαναδωσει το μαθημα :/

ποπα .!.

εχει λυσει μηπως κανεις τα θεματα του Ιουνιου 16 και μπορει να τ ανεβασει??

https://www.thmmy.gr/smf/index.php?topic=1894.msg1152129;topicseen#new (https://www.thmmy.gr/smf/index.php?topic=1894.msg1152129;topicseen#new)

thx

γλυκούλης  <3 <3

https://www.youtube.com/watch?v=1GZOzTJOBuM

τί μπορούμε να έχουμε μαζί αύριο;

Ότι μη ηλεκτρονικό θες. Προσοχή στη 1,5 ώρα μονο που ειναι λίγη

έχει λύσει κάποιος/α 1ο θέμα Φεβρουαρίου 2016?

είσαι μεγάλος παικταράς!

Μπορει να εξηγησει καποιος πως εξαλειφουμε κοντους κανονες για να παμε σε κανονικη μορφη Chomsky? Δε μπορω να το καταλαβω με τιποτα

- Αρχικά βρίσκουμε για κάθε σύμβολο A που ανήκει στο V το D(A)={BανήκειV : A->* B}, δηλαδή στο D(A) ανήκουν όλα τα σύμβολα Β στα οποία μπορείς να φτάσεις ξεκινώντας από το Α, μετά από έναν αριθμό βημάτων. Το D(A) περιέχει πάντοτε το Α.
- Έπειτα διαγράφουμε τους κοντούς κανόνες.
- Μετά αντικαθιστούμε τους κανόνες της μορφής A->BC με όλους τους δυνατούς συνδυασμούς Α->B'C' με B' ανήκει D(B) και C' ανήκει D(C).
 Για παράδειγμα αν έχουμε τον κανόνα S->S1 X και D(S1)={S1,S} D(X)={X,S1,S} τότε οι νέοι κανόνες θα είναι : S->S1 X, S->S1S1 S->S1S, S->SX, S->SS1,  S->SS
- Tέλος βρίσκουμε το D(S)-{S} και ,αν αυτό δεν είναι το κενό σύνολο, για κάθε Α που ανήκει στο D(S)-{S} με Α->ΒC προσθέτουμε τον κανόνα S->BC

μπράβο θεάρα!

Δηλαδη αν π.χ. S-> bA|aB|a|b τότε D(S) = {S,a,b} ή S->{S,A,B,a,b} (ή κάτι άλλο) ?

Το πρωτο