ΣΕ μοντέρνα τεχνολογίασυσκευές ελέγχου και υπολογισμού μια σημαντική θέση καταλαμβάνουν διακριτοί μετατροπείς, δηλαδή συσκευές που έχουν ορισμένο αριθμό εισόδων και εξόδων. Τα σύνολα σημάτων που φτάνουν στις εισόδους και εμφανίζονται στις εξόδους ανήκουν σε γνωστά πεπερασμένα σύνολα.
Μοιραστείτε εργασία στα κοινωνικά δίκτυα
Εάν αυτό το έργο δεν σας ταιριάζει, υπάρχει μια λίστα με παρόμοια έργα στο κάτω μέρος της σελίδας. Μπορείτε επίσης να χρησιμοποιήσετε το κουμπί αναζήτησης
Aranov Viktor Pavlovich Διακριτά Μαθηματικά. Ενότητα 5. DNF και σχήματα από FE.
Διάλεξη 28 Προβλήματα ανάλυσης και σύνθεσης
Διάλεξη 28 ΣΧΗΜΑΤΑ ΑΠΟ ΛΕΙΤΟΥΡΓΙΚΑ ΣΤΟΙΧΕΙΑ.
ΠΡΟΒΛΗΜΑΤΑ ΑΝΑΛΥΣΗΣ ΚΑΙ ΣΥΝΘΕΣΗΣ
Σχέδιο διάλεξης:
1. Η έννοια ενός κυκλώματος λειτουργικών στοιχείων(ΦΕ).
2. Προβλήματα ανάλυσης και σύνθεσης κυκλωμάτων από FE.
- Η έννοια ενός κυκλώματος από FE
Στη σύγχρονη τεχνολογία των συσκευών ελέγχου και υπολογιστών, σημαντική θέση κατέχειδιακριτούς μετατροπείς, δηλαδή συσκευές που έχουν ορισμένο αριθμό εισόδων και εξόδων. Τα σύνολα σημάτων που φτάνουν στις εισόδους και εμφανίζονται στις εξόδους ανήκουν σε γνωστά πεπερασμένα σύνολα. Οι συσκευές μετατρέπουν σετ σημάτων εισόδου σε εξόδου. Το μαθηματικό μοντέλο τέτοιων συσκευών είναι τα λεγόμενακυκλώματα από λειτουργικά στοιχεία(SFE).
Ως παράδειγμα, εξετάστε το ηλεκτρικό κύκλωμα τριών διόδων και την αντίσταση που φαίνεται στο Σχ. 1.
Ρύζι. 1. Διάγραμμα καλωδίωσης και αυτό σύμβολο
Στα σημεία του κυκλώματος που απεικονίζονται από έναν κύκλο, σε διαφορετικές χρονικές στιγμές, μπορεί να εμφανιστεί είτε ένα υψηλό επίπεδο, περίπου ίσο με 5 V, είτε ένα χαμηλό επίπεδο, περίπου ίσο με το μηδέν. Στο σημείο του κυκλώματος που σημειώνεται με παύλα, διατηρείται μια σταθερά χαμηλή στάθμη τάσης.
Τα σημειωμένα σημεία θα ερμηνεύονται ως είσοδοι και το σημείο ως έξοδο. Η λειτουργία του κυκλώματος μπορεί να περιγραφεί ως εξής: εάν το επίπεδο τάσης είναι χαμηλό σε όλες τις εισόδους, τότε η έξοδος είναι επίσης χαμηλή, εάν τουλάχιστον μία από τις εισόδους έχει υψηλό επίπεδο τάσης, τότε η έξοδος είναι υψηλή. Αν ορίσουμε ένα κράτος με υψηλό επίπεδοτάση κατά ένα και με χαμηλό μηδέν, τότε η εξάρτηση της εξόδου από τις εισόδους μπορεί να ρυθμιστεί χρησιμοποιώντας μια συνάρτηση Boolean.
Με βάση αυτό, το παραπάνω κύκλωμα ονομάζεται λογικό στοιχείο "OR".
Παρόμοια κυκλώματα μπορούν να κατασκευαστούν από σωλήνες κενού, ηλεκτρομηχανικούς διακόπτες, πνευματικά στοιχεία κ.λπ. Η εξάρτηση της εξόδου από τις εισόδους μπορεί να περιγραφεί όχι μόνο ως διαχωρισμός, αλλά και με τη βοήθεια σύνδεσης, άρνησης και πιο περίπλοκων συναρτήσεων Boole.
Θα εξετάσουμε λογικά στοιχεία με διαφορετική εξάρτηση της εξόδου από τις εισόδους. Αυτά τα στοιχεία μπορούν να συνδεθούν μεταξύ τους τροφοδοτώντας τις εξόδους ορισμένων στοιχείων στις εισόδους άλλων. Ως αποτέλεσμα, παίρνουμε SFE.
Ο ορισμός της έννοιας του SFE μπορεί να χωριστεί σε δύο στάδια. Στο πρώτο στάδιο, αποκαλύπτεται το δομικό μέρος αυτής της έννοιας, στο δεύτερο - το λειτουργικό.
Εγώ στάδιο. Ας χωρίσουμε αυτό το βήμα σε διάφορα βήματα.
1 . Υπάρχει ένα πεπερασμένο σύνολο αντικειμένων () που ονομάζεταιλογικά στοιχεία.Κάθε στοιχείο έχει εισόδους και μία έξοδο. Το στοιχείο απεικονίζεται γραφικά όπως φαίνεται στο Σχ. 2.
2 . Με την επαγωγή ορίζουμε την έννοιαλογικό δίκτυο ως αντικείμενο που έχει ορισμένο αριθμό εισόδων και συγκεκριμένο αριθμό εξόδων (Εικ. 3).
α) Βάση επαγωγής. Μια απομονωμένη κορυφή ονομάζεται τετριμμένο λογικό δίκτυο. Εξ ορισμού, είναι και είσοδος και έξοδος (Εικόνα 4).
… …
…
Ρύζι. 2 Εικ. 3 Εικ. 4
β) Επαγωγική μετάβαση. Αυτό το μέρος βασίζεται στη χρήση τριών λειτουργιών.
I . Η λειτουργία συνδυασμού ασυνεχών δικτύων. Έστω και είναι δύο μη τεμνόμενα δίκτυα (χωρίς κοινά στοιχεία, εισόδους και εξόδους) που έχουν και εισόδους και εξόδους, αντίστοιχα. Η ένωση δικτύων θεωρητικής συνόλων είναι ένα λογικό δίκτυο που έχει εισόδους και εξόδους.
II . Η λειτουργία της προσάρτησης ενός στοιχείου. Αφήστε το δίκτυο και το στοιχείο να είναι τέτοια ώστε και σε διαφορετικές εξόδους με αριθμούς επιλέγονται. Τότε το σχήμα ονομάζεται λογικό δίκτυο, το οποίο είναι το αποτέλεσμα της σύνδεσης ενός στοιχείου σε ένα δίκτυο. Οι είσοδοι είναι όλες οι είσοδοι, οι έξοδοι είναι όλες οι έξοδοι του δικτύου, εκτός από τις εξόδους με αριθμούς, καθώς και την έξοδο του στοιχείου. Το δίκτυο έχει εισόδους και εξόδους (Εικ. 5).
… …
Ρύζι. 6.
Ρύζι. 5
III . Η λειτουργία του διαχωρισμού της εξόδου. Αφήστε μια έξοδο με αριθμό να επιλεγεί στο δίκτυο. Τότε το σχήμα ονομάζεται λογικό δίκτυο που λαμβάνεται με διαίρεση της εξόδου. Οι είσοδοι είναι όλες οι είσοδοι, οι έξοδοι είναι όλες οι έξοδοι του δικτύου με αριθμούς 1, ..., ..., και δύο ακόμη έξοδοι που προκύπτουν από την έξοδο με τον αριθμό δικτύου (Εικ. 6). Επομένως, έχει εισόδους και εξόδους.
3 . Αφήστε τα αλφάβητα και δοθούν.
Διάγραμμα λειτουργικών στοιχείωνονομάζεται λογικό δίκτυο με εισόδους από το αλφάβητο και εξόδους από το αλφάβητο, το οποίο συμβολίζεται
. (1)
Δίνουμε παραδείγματα σχημάτων.
1. Έστω ότι το σύνολο αποτελείται από τρία στοιχεία AND (συνδετήρας), OR (διαζευκτήρας) και NOT (inverter).
Τότε το σχήμα (Εικ. 6) θα είναι ένα διάγραμμα, αφού μπορεί να κατασκευαστεί χρησιμοποιώντας τις πράξεις I III .
Ρύζι. 6 Εικ. 7
2. Το σχήμα που φαίνεται στο σχ. 7, είναι επίσης ένα διάγραμμα.
II στάδιο. Προσδιορισμός της λειτουργίας του κυκλώματος.
4 . Ας συγκρίνουμε το SFE (1) με το σύστημα συναρτήσεων της άλγεβρας της λογικής
(2)
επίσης λέγεταιαγωγιμότητα αυτού του κυκλώματος.
Παράδειγμα. α) Για το κύκλωμα, έχουμε ένα σύστημα που αποτελείται από μία εξίσωση
Ή.
β) Για το σχήμα, λαμβάνουμε ομοίως
- Υλοποίηση Boolean συναρτήσεων από κυκλώματα FE. Προβλήματα ανάλυσης και σύνθεσης
σχέδια από ΦΒ
Εργασία ανάλυσης: για ένα δεδομένο SFE (1) να ληφθεί ένα σύστημα εξισώσεων Boole (2).
Αλγόριθμος επίλυσης του προβλήματος: παρακολούθηση των πράξεων κατασκευής δικτύου I III , υπολογίζουμε διαδοχικά τις συναρτήσεις στις εξόδους των στοιχείων δικτύου.
Εργασία σύνθεσης: για μια δεδομένη βάση λειτουργικών στοιχείων και ένα αυθαίρετο σύστημα εξισώσεων Boole (2), κατασκευάστε ένα κύκλωμα (1) από δεδομένα FE που εφαρμόζει αυτό το σύστημα εξισώσεων.
Η ύπαρξη λύσης στο πρόβλημα σύνθεσης καθορίζεται από το θεώρημα Post, σύμφωνα με το οποίο το σύστημα συναρτήσεων που υλοποιούν το βασικό FE πρέπει να είναι πλήρες. Οι συναρτήσεις μπορούν να αναπαρασταθούν ως υπέρθεση συναρτήσεων και κάθε βήμα της υπέρθεσης αντιστοιχεί σε έναν ορισμένο συνδυασμό στοιχείων.
Παράδειγμα. Για λειτουργία
(3)
Το σχήμα που αντιστοιχεί στην υπέρθεση στη δεξιά πλευρά του τύπου (3) φαίνεται στο σχ. 8.
Ρύζι. 8
Το πρόβλημα σύνθεσης έγκειται στο γεγονός ότι για ένα δεδομένο σύστημα εξισώσεων Boole είναι δυνατό να κατασκευαστούν πολλά κυκλώματα από FE που εφαρμόζουν αυτό το σύστημα. Από αυτή την άποψη, προκύπτει το πρόβλημα της βέλτιστης σύνθεσης: από όλα τα πιθανά σχήματα που υλοποιούνται αυτή τη λειτουργία, επιλέξτε το καλύτερο ένα προς ένα χαρακτηριστικό ή το άλλο, για παράδειγμα, με τον μικρότερο αριθμό στοιχείων. Τέτοια σχήματα θα κληθούνελάχιστη.
Ο παρακάτω ισχυρισμός είναι αληθής.
Θεώρημα. Υπάρχει ένας αλγόριθμος που για κάθε σύστημα Boolean συναρτήσεων δημιουργεί ένα ελάχιστο κύκλωμα.
Αυτός ο αλγόριθμοςΗ κατασκευή ελάχιστων κυκλωμάτων ανήκει στην κατηγορία των αλγορίθμων του τύπου "brute force", καθώς βασίζεται στην προβολή όλων των κυκλωμάτων μέχρι μια ορισμένη πολυπλοκότητα. Οι αλγόριθμοι ωμής δύναμης, κατά κανόνα, είναι πολύ επίπονοι και ακατάλληλοι για πρακτικούς σκοπούς. Επομένως, εξετάζουμε περαιτέρω ένα απλούστερο πρόβλημα για το οποίο το αρχικό σύστημα εξισώσεων περιέχει μία εξίσωση
και, επομένως, το επιθυμητό κύκλωμα έχει μία έξοδο.
Να συμβολίσετε την πολυπλοκότητα του ελάχιστου κυκλώματος με . Θα εξετάσουμε το πρόβλημα σύνθεσης όχι για μια μεμονωμένη συνάρτηση, αλλά για ολόκληρη την κατηγορία συναρτήσεων των μεταβλητών. Η ποιότητα των αλγορίθμων σύνθεσης συγκρίνεται συγκρίνοντας τις λεγόμενες συναρτήσεις Shannon. Αφήνω
την ελάχιστη πολυπλοκότητα των κυκλωμάτων που υλοποιούν, τα οποία λαμβάνονται με τη χρήση του αλγόριθμου.
Οι συναρτήσεις ονομάζονται συναρτήσεις Shannon, και είναι προφανές ότι
Το καθήκον της σύνθεσης είναι να βρεθεί ένας αλγόριθμος στον οποίο θα ήταν δυνατό να είναι πιο κοντά και έτσι ώστε η πολυπλοκότητα του αλγορίθμου να είναι σημαντικά μικρότερη από την πολυπλοκότητα του εξαντλητικού αλγορίθμου αναζήτησης. Με μια τέτοια διατύπωση του προβλήματος, δεν απαιτείται ο αλγόριθμος για κάθε συνάρτηση να βρίσκει το ελάχιστο κύκλωμα, είναι απαραίτητο μόνο να το απλούστερο κύκλωμα, που ελήφθη με τη βοήθεια, είχε μια πολυπλοκότητα που δεν υπερέβαινε πολύ.
Άλλες σχετικές εργασίες που μπορεί να σας ενδιαφέρουν.vshm> |
|||
| 9013. | ΜΕΘΟΔΟΙ ΣΥΝΘΕΤΗΣΗΣ ΣΧΗΜΑΤΩΝ ΑΠΟ FE. ΣΧΗΜΑΤΑ ΑΠΟΚΩΔΙΚΟΠΟΙΗΤΗ ΚΑΙ ΔΥΑΔΙΚΟΥ ΠΡΟΣΘΗΚΗ | 153,07 KB | |
| Η γενική θεωρία της σύνθεσης SFE οδηγεί στο συμπέρασμα ότι οι περισσότερες από τις συναρτήσεις Boolean για μεγάλες τιμές έχουν πολύπλοκα ελάχιστα σχήματα. Αυτό σημαίνει ότι μια πολύ στενή κατηγορία Boolean συναρτήσεων έχει πρακτική αξία από την άποψη της σύνθεσης. | |||
| 5321. | Τύποι και τιμές των αυτόματων παραμέτρων προστασίας για διάφορα στοιχεία ενός δεδομένου σχεδίου σχεδίου | 526,7 KB | |
| Για την παροχή κανονική λειτουργίατου συστήματος ηλεκτρικής ενέργειας και των καταναλωτών ηλεκτρικής ενέργειας, είναι απαραίτητο να εντοπιστεί και να διαχωριστεί το συντομότερο δυνατό ο τόπος της ζημιάς από το μη κατεστραμμένο δίκτυο, αποκαθιστώντας τις κανονικές συνθήκες λειτουργίας του συστήματος ηλεκτρικής ενέργειας και των καταναλωτών. | |||
| 5384. | Ανάπτυξη ηλεκτρικού κυκλώματος βάσης για την ανάλυση της λειτουργίας ενός χρονισμένου αποκωδικοποιητή για 4 εισόδους και 16 εξόδους | 626,63 KB | |
| Για τη βελτίωση της λειτουργίας του τροχαίου υλικού ATP, έχει αναπτυχθεί η οργανωτική δομή του συστήματος συντήρησης και επισκευής του τροχαίου υλικού ATP, καθώς και ένα σύνολο εξοπλισμού για τη διάγνωση και Συντήρηση. Ο κύριος στόχος της λειτουργίας των εγκαταστάσεων επισκευής της επιχείρησης είναι η διασφάλιση της αδιάλειπτης λειτουργίας του εξοπλισμού. Περιλαμβάνει: βάση επισκευής και αποκατάστασης της επιχείρησης, αποθήκες, συνεργεία και γενικά τμήματα εγκαταστάσεων επισκευαστικών εγκαταστάσεων, τεχνολογικό εξοπλισμό, αποστολέα. Οργάνωση... | |||
| 1886. | Στάδια ανάλυσης συστήματος, κύριοι στόχοι, καθήκοντα | 27,44KB | |
| Η θεωρία των βέλτιστων συστημάτων μας επιτρέπει να εκτιμήσουμε το όριο που μπορεί να επιτευχθεί σε ένα βέλτιστο σύστημα, να το συγκρίνουμε με τους δείκτες ενός υπάρχοντος μη βέλτιστου συστήματος και να ανακαλύψουμε εάν είναι σκόπιμο στην υπό εξέταση περίπτωση να αναπτυχθεί ένα βέλτιστο σύστημα. Για μια αυτόματα ελεγχόμενη διαδικασία ενός αυτόματα ελεγχόμενου συστήματος, διακρίνονται δύο στάδια βελτιστοποίησης: στατικό και δυναμικό. Η στατική βελτιστοποίηση επιλύει τα ζητήματα δημιουργίας και εφαρμογής ενός βέλτιστου μοντέλου διαδικασίας, ενώ δυναμική... | |||
| 5123. | Ανάπτυξη λειτουργικών στρατηγικών | 35,44 KB | |
| Στρατηγική διαχείρισης προσωπικού. Λειτουργίες και δομή διαχείρισης. Οι λειτουργίες διαχείρισης και ο ρόλος τους στη διαμόρφωση των δομών διαχείρισης. Ιεραρχικός τύπος δομής ελέγχου. | |||
| 20368. | Η επίδραση της σύνθεσης συνταγογραφούμενων συστατικών και τεχνολογιών στις καταναλωτικές ιδιότητες λειτουργικών προϊόντων | 742,05 KB | |
| Η σύγχρονη ιατρική επιστήμη έχει υιοθετήσει την έννοια της βέλτιστης διατροφής. Αυτό σημαίνει ότι έχει γίνει μια μετάβαση από την έννοια της επαρκής διατροφής, όταν τα μακροθρεπτικά συστατικά ήταν κυρίως ρυθμισμένα και κανονικοποιημένα - πηγές λίπους, πηγές ενέργειας, πλαστικό υλικό (λιπίδια, πρωτεΐνες, λίπη), στην έννοια της βέλτιστης διατροφής, όταν Η γκάμα των θρεπτικών ουσιών και άλλων θρεπτικών συστατικών που είναι απαραίτητα για τη ζωή των δευτερευόντων συστατικών του σώματος, στα οποία δεν δόθηκε προηγουμένως προσοχή, διευρύνεται σημαντικά. | |||
| 4706. | Μέθοδοι για τη σύνθεση καρβοξυλικών Me | 9,26 MB | |
| Η ουσία της μεθόδου είναι η διάλυση του οξειδίου, υδροξειδίου ή ανθρακικού μετάλλου σε ένα υδατικό διάλυμα του αντίστοιχου οξέος. Το προϊόν απομονώνεται με εξάτμιση του διαλύματος πριν από την έναρξη της κρυστάλλωσης ή με διήθηση του ιζήματος εάν το καρβοξυλικό είναι αδιάλυτο ή ελάχιστα διαλυτό στο νερό. | |||
| 15923. | Βασικές μέθοδοι σύνθεσης πυραζαλοδιαζεπινών | 263,39 KB | |
| Νέες μέθοδοι για τη σύνθεση παραγώγων πυραζολοδιαζεπίνης. Η ανάπτυξη νέων στρατηγικών σύνθεσης παρουσιάζει σημαντικό ενδιαφέρον. Δεν έχουν διεξαχθεί συστηματικές και γενικευτικές μελέτες για τη σύνθεση παραγώγων πυραζολοδιαζεπίνης· ορισμένα ζητήματα παραμένουν ανέγγιχτα, αμφιλεγόμενα ή δεν έχουν επιλυθεί πλήρως. | |||
| 11978. | Εγκαταστάσεις ενεργειακής τεχνολογίας με βάση την υδροθερμική οξείδωση του αλουμινίου για την παραγωγή ηλεκτρικής ενέργειας, θερμότητας, υδρογόνου και λειτουργικών νανοϋλικών | 49,89KB | |
| Η ανάπτυξη βασίζεται στην αντίδραση υδροθερμικής οξείδωσης του αλουμινίου κατά την οποία απελευθερώνεται μεγάλη ποσότητα θερμικής ενέργειας και σχηματίζονται οξείδια αλουμινίου και υδρογόνο: l2H2O→lOOH boehmite15H2415. Ως αρχικά αντιδραστήρια χρησιμοποιούνται απεσταγμένο νερό και σκόνες αλουμινίου micron. Εγκατάσταση KEU10 Εγκατάσταση ETK100 ΠροδιαγραφέςΜονάδες ETK100: Τιμή παραμέτρου Κατανάλωση αλουμινίου kg h 101 Κατανάλωση νερού στην είσοδο στη συσκευή επεξεργασίας νερού kg h 484 Χωρητικότητα υδρογόνου nm3 110 Θερμική ισχύς ... | |||
| 6605. | Εξειδικευμένα συστήματα. Σχεδιασμός TP με μέθοδο σύνθεσης | 11,67 KB | |
| Η αναπαράσταση της συσσώρευσης γνώσης και η διατήρησή της ενημερωμένη είναι μια πολύπλοκη εργασία που διερευνάται στο τμήμα της επιστήμης των υπολογιστών που ονομάζεται μηχανική γνώσης. Ο μηχανικός γνώσης εμπλέκεται στην ανάπτυξη της γνωσιακής βάσης του πυρήνα των συστημάτων που ονομάζονται ευφυή. Τις περισσότερες φορές, τα έξυπνα συστήματα χρησιμοποιούνται για την επίλυση πολύπλοκων προβλημάτων όπου η κύρια πολυπλοκότητα της λύσης ... | |||
Η αναπαράσταση των Boolean συναρτήσεων με τύπους μπορεί να αποδοθεί με την ακόλουθη έννοια "μηχανική-κατασκευαστική". Θα θεωρήσουμε έναν τύπο πάνω από κάποιο αυθαίρετα καθορισμένο σύνολο ως "μαύρο κουτί", ένα είδος συσκευής, στην είσοδο του οποίου τροφοδοτούνται όλα τα πιθανά σύνολα μεταβλητών τιμών και οι τιμές της συνάρτησης που αντιπροσωπεύονται από τον τύπο που αντιστοιχεί σε αυτά τα σύνολα εμφανίζονται στην έξοδο (Εικ. 6.22).
Για να κατανοήσουμε πώς λειτουργεί το «μαύρο κουτί», πρέπει να αναλύσουμε τη διαδικασία κατασκευής ενός τύπου από υποτύπους. Φτάνοντας στους «βασικούς» υποτύπους, δηλ. στοιχεία του συνόλου , φτάνουμε στα «τούβλα», τα δομικά στοιχεία από τα οποία συναρμολογείται το «μαύρο κουτί», το οποίο υπολογίζει τη συνάρτηση . Κάθε συνάρτηση της «βάσης» υπολογίζεται από τον αντίστοιχο «κόμβο», που θεωρείται ως η μικρότερη δομική μονάδα του «μαύρου κουτιού» μας και η εσωτερική του δομή δεν αναλύεται πλέον.
Παράδειγμα 6.22.Ας επιλέξουμε την τυπική βάση ως σύνολο. Στη συνέχεια, ένας τύπος σε μια τυπική βάση που αντιπροσωπεύει μια συνάρτηση (ισοδυναμία) κατασκευάζεται ως εξής:
Ο υπολογισμός με αυτόν τον τύπο (και η διαδικασία κατασκευής του από τα στοιχεία της τυπικής βάσης) μπορεί να απεικονιστεί σχηματικά όπως φαίνεται στο Σχ. 6.23.
Μια μεταβλητή (ακριβέστερα, η τιμή αυτής της μεταβλητής) τροφοδοτείται στην είσοδο ενός δομικού στοιχείου που ονομάζεται μετατροπέας (Εικ. 6.24, α) και υπολογίζει την άρνηση. Η άρνηση αφαιρέθηκε από την έξοδο του μετατροπέα, δηλ. συνάρτηση , τροφοδοτείται σε μία από τις εισόδους του συνδέσμου (Εικ. 6.24.5), η δεύτερη είσοδος του οποίου παρέχεται με μια μεταβλητή . Η συνάρτηση εμφανίζεται στην έξοδο του συνδέσμου. Ο υπολογισμός της συνάρτησης παρακολουθείται με παρόμοιο τρόπο. Και οι δύο αυτές συναρτήσεις τροφοδοτούνται στις εισόδους του διαχωριστή (Εικ. 6.24, c), από την έξοδο του οποίου αφαιρείται η συνάρτηση (αυτό δεν είναι τίποτα άλλο από το άθροισμα του αθροίσματος 2:). Και τέλος, αυτή η συνάρτηση τροφοδοτείται στην είσοδο του μετατροπέα, στην έξοδο του οποίου λαμβάνεται ήδη η συνάρτηση (ισοδυναμία).
Έτσι, φτάνουμε στην ιδέα ενός "κυκλώματος" - ενός μαθηματικού μοντέλου μιας αριθμομηχανής συνάρτησης Boole, που αντιπροσωπεύεται από κάποιον τύπο, συναρμολογημένο από δομικά στοιχεία, καθένα από τα οποία υπολογίζει μία από τις "βασικές" συναρτήσεις Boolean. Στη γενική περίπτωση, το "κύκλωμα" υπολογίζει έναν Boolean τελεστή και κάθε συντεταγμένη συνάρτηση αυτού του τελεστή λαμβάνεται από μία από τις εξόδους του κυκλώματος.
Μαθηματικά, ένα "κύκλωμα" ορίζεται ως ένα ειδικό είδος κατευθυνόμενου γραφήματος στο οποίο τόσο οι κορυφές όσο και τα τόξα παρέχονται με ορισμένες ετικέτες.
Ας εισαγάγουμε τη σημείωση: εάν είναι κάποιο σύνολο συναρτήσεων Boole, τότε συμβολίζουμε με το υποσύνολο που αποτελείται από όλες τις συναρτήσεις των μεταβλητών.
Ορισμός 6.14. Αφήστε τα σύνολα: (συναρτήσεις Boolean) και (Boolean μεταβλητές) να είναι σταθερά.
Ένα κύκλωμα λειτουργικών στοιχείων πάνω από μια βάση (CFE), ή απλά ένα κύκλωμα πάνω από μια βάση, επίσης ένα κύκλωμα (F,X), είναι ένα κατευθυνόμενο γράφημα χωρίς περίγραμμα (δηλαδή ένα δίκτυο), κάθε κορυφή του οποίου επισημαίνεται με ένα από τα στοιχεία του συνόλου ώστε να ισχύουν τα ακόλουθα: απαιτήσεις:
1) κάθε είσοδος του δικτύου επισημαίνεται είτε με κάποια μεταβλητή από , είτε με κάποια σταθερά από ?
2) εάν η κορυφή v του δικτύου χαρακτηρίζεται από μια συνάρτηση μεταβλητών (δηλαδή), τότε ο ημιβαθμός εισόδου της είναι ίσος με και στο σύνολο των τόξων που εισέρχονται στην κορυφή, δίνεται μια αρίθμηση (ένα προς ένα), στο οποίο κάθε τόξο λαμβάνει έναν αριθμό από το 1 έως το .
Όταν απεικονίζονται κυκλώματα, οι είσοδοι υποδεικνύονται με κύκλους και οι κορυφές που δεν είναι είσοδοι υποδεικνύονται με τρίγωνα, μέσα στα οποία αναγράφεται ο προσδιορισμός της συνάρτησης που σηματοδοτεί τη δεδομένη κορυφή. Οι έξοδοι σημειώνονται με βέλη "εξόδου". Στο σχ. Το 6.25 δείχνει το SFE πάνω από τη βάση.
Αν υπονοείται η βάση, τότε θα πούμε απλά «σχήμα». Επιπλέον, εάν το σύνολο των μεταβλητών είναι σταθερό "μια για πάντα" και, όταν εξετάζουμε διάφορα σχήματα, αλλάζουμε μόνο το σύνολο των συναρτήσεων , τότε, όπως κάναμε όταν εισάγαμε τις έννοιες του τύπου και της υπέρθεσης σε μια δεδομένη βάση, θα μιλήσει για το SFE πάνω από τη βάση , θέτοντας κάθε φορά, αυτό που εννοείται είναι ένα σταθερό σύνολο μεταβλητών, το οποίο (αν δεν βλάπτει την ακρίβεια) δεν αναφέρεται.
Ας ορίσουμε τώρα επαγωγικά την έννοια μιας Boolean συνάρτησης που υπολογίζεται από μια κορυφή κυκλώματος.
Ορισμός 6.15. Ας δοθεί SFE πάνω από τη βάση , το σύνολο των κορυφών της οποίας είναι .
1. Υποτίθεται ότι κάθε είσοδος SFE υπολογίζει τη Boolean συνάρτηση με την οποία έχει χαρακτηριστεί (δηλαδή, κάποια μεταβλητή ή σταθερά).
2. Εάν μια κορυφή επισημαίνεται με μια συνάρτηση, το τόξο με τον αριθμό που εισάγεται προέρχεται από την κορυφή , η οποία υπολογίζει τη συνάρτηση , τότε η κορυφή v υπολογίζει την υπέρθεση .
Έτσι, εάν κάθε κορυφή του CFE over υπολογίζει κάποια συνάρτηση, τότε η σειρά με την οποία παρατίθενται οι συναρτήσεις που έχουν αντικατασταθεί στη θέση τους μεταβλητές συνάρτησης, είναι ουσιαστικό στη γενική περίπτωση. Είναι φυσικό να ονομάζουμε μια Boolean συνάρτηση μεταβλητών ανταλλάξιμη εάν διατηρεί την τιμή της κάτω από μια αυθαίρετη μετάθεση των μεταβλητών της. Σε αυτήν την περίπτωση, μπορεί να μην μας ενδιαφέρει η αρίθμηση των τόξων που εισέρχονται στην κορυφή του κυκλώματος που φέρει ετικέτα με μια τέτοια συνάρτηση.
Παράδειγμα 6.23.Ας εξετάσουμε το SFE στο σχ. 6.25. Οι κορυφές και είναι οι είσοδοι του SFE. Αυτές οι κορυφές υπολογίζουν τις συναρτήσεις και , αντίστοιχα. Στη συνέχεια, η κορυφή , όπως και η κορυφή , σύμφωνα με τον ορισμό 6.15, υπολογίζει τη συνάρτηση (stroke Scheffer), και η κορυφή (έξοδος δικτύου) υπολογίζει τη συνάρτηση , η οποία, όπως είναι γνωστό, είναι ίση με τον σύνδεσμο .
SFE που φαίνεται στο Σχ. Το 6.26 έχει δύο εξόδους, συναρτήσεις υπολογισμού και .
Ορισμός 6.16. Η συνάρτηση Boolean που υπολογίζεται από το SFE πάνω από τη βάση είναι η συνάρτηση που υπολογίζεται από οποιαδήποτε από τις εξόδους του.
Έτσι, το SFE υπολογίζει ακριβώς τόσες Boolean συναρτήσεις όσες έχει εξόδους. SFE στο σχ. Το 6.25 υπολογίζει μία συνάρτηση και το SFE στο σχ. 6.26 - δύο.
Στη γενική περίπτωση, εάν είναι το σύνολο όλων των μεταβλητών που χρησιμεύουν ως ετικέτες για τις εισόδους του κυκλώματος πάνω από τη βάση , η οποία έχει m εξόδους, το CFE καθορίζει την αντιστοίχιση του κύβου Boole στον κύβο Boole , δηλ. boolean τελεστή.
Παρατήρηση 6.10.Σε ορισμένες περιπτώσεις, η συνάρτηση που υπολογίζεται από ένα δεδομένο CFE ορίζεται κάπως διαφορετικά, υποθέτοντας ότι είναι μια συνάρτηση που υπολογίζεται από οποιαδήποτε κορυφή από ένα υποσύνολο επιλεγμένων κορυφών CFE. Συγκεκριμένα, μπορεί να είναι έξοδοι. Σε κάθε περίπτωση, ας συμφωνήσουμε να σχεδιάσουμε ένα βέλος "εξόδου" από τις επιλεγμένες (με την έννοια που μόλις υποδεικνύονται) κορυφές του σχήματος.
Έτσι, κάθε κύκλωμα λειτουργικών στοιχείων υπολογίζει κάποιο Boolean τελεστή, συγκεκριμένα, εάν ο αριθμός των εξόδων του κυκλώματος είναι 1, τότε υπολογίζει κάποια Boolean συνάρτηση.
Το αντίστροφο μπορεί επίσης να αποδειχθεί: για οποιονδήποτε τελεστή Boole, ένας SFE μπορεί να κατασκευαστεί πάνω από τη βάση , όπου είναι το πλήρες σύνολο που υπολογίζει αυτόν τον τελεστή.
Παράδειγμα 6.24.Ας ορίσουμε τον πίνακα σε έναν Boolean τελεστή που αντιστοιχεί σε (Πίνακας 6.9).
Είναι εύκολο να διαπιστωθεί από τον πίνακα ότι (η συνάρτηση δεν είναι παρά η συνάρτηση πλειοψηφίας των μεταβλητών , και το ελάχιστο DNF για αυτήν είναι γραμμένο παραπάνω, βλέπε παράδειγμα 6.12). Ας αναπαραστήσουμε τη συνάρτηση στη βάση Zhegalkin. Χρησιμοποιώντας τους νόμους του de Morgan, παίρνουμε
Λαμβάνοντας υπόψη αυτό, θα έχουμε
(υπενθυμίζουμε ότι το άθροισμα modulo 2 οποιουδήποτε ζυγού αριθμού ίσων όρων είναι 0). Ετσι,
SFE για τον τελεστή Boolean που καθορίζεται στον Πίνακα. 6.9, πάνω από τη βάση Zhegalkin φαίνεται στο Σχ. 6.27.
Κατά το σχεδιασμό ενός SPV, είναι χρήσιμο να έχουμε κατά νου μια αριθμητική παράμετρο που ονομάζεται πολυπλοκότητά του.
Η πολυπλοκότητα του SFE είναι ο αριθμός των κορυφών του που δεν είναι είσοδοι.
Εμφανίζεται στο σχ. 6.27 Το CFE στη βάση Zhegalkin έχει πολυπλοκότητα 5.
Ας εξετάσουμε τώρα το CFE για τον ίδιο τελεστή πάνω από την τυπική βάση. Σύμφωνα με τον πίνακα (βλ. Πίνακα 6.9), κατασκευάζουμε SDNF για τη συνάρτηση
Ο χάρτης Carnot για αυτή τη συνάρτηση, που φαίνεται στο Σχ. Το 6.28 δείχνει ότι δεν μπορεί να ελαχιστοποιηθεί (πιο συγκεκριμένα, το SDNF που γράφτηκε παραπάνω είναι το ελάχιστο DNF για αυτήν τη συνάρτηση).
Αλλά μπορείς να πας από την άλλη. Μπορούμε να εξετάσουμε τον Πίνακα. 6.9 ως πίνακας που ορίζει μια μερική συνάρτηση Boole. Ελαχιστοποίηση αυτής της συνάρτησης σύμφωνα με τον χάρτη Carnot* που φαίνεται στην Εικ. 6.29, παίρνουμε
*Σε αυτόν τον χάρτη, έχουμε σημειώσει ρητά τα σύνολα στα οποία η συνάρτηση παίρνει την τιμή 0 βάζοντας μηδενικά στα αντίστοιχα κελιά. Έτσι, θέλουμε για άλλη μια φορά να δώσουμε προσοχή στο γεγονός ότι τα μηδενικά δεν πρέπει να συγχέονται με τις παύλες: μια παύλα σε ένα κελί ενός χάρτη που ορίζει μια μερική συνάρτηση σημαίνει ότι αυτό το σετη τιμή της συνάρτησης δεν ορίζεται, δηλ. δεν είναι ούτε 0 ούτε 1.
Το SFE πάνω από την τυπική βάση για τον εξεταζόμενο τελεστή Boolean φαίνεται στο Σχ. 6.30. Η πολυπλοκότητα αυτού του CFE είναι 11. Σημειώστε ότι ο κόμβος που αξιολογεί τη συνάρτηση δεν είναι έξοδος.
Ο τελεστής Boolean που συζητήθηκε σε αυτό το παράδειγμα υπολογίζει το διψήφιο άθροισμα (modulo 2) τριών μονοψήφιων όρων. Μπορεί επίσης να θεωρηθεί ως δυαδικός αθροιστής ενός bit - ένα λειτουργικό μπλοκ δυαδικού αθροιστή πολλών bit - για δύο όρους. Στη συνέχεια, η συνάρτηση r/1 ερμηνεύεται ως "σήμα μεταφοράς" στο πιο σημαντικό bit. Στο σχ. Το σχήμα 6.31 δείχνει μια "σύνδεση" τριών SFE (όπως φαίνεται στο Σχήμα 6.30), η οποία υπολογίζει το άθροισμα δύο τριψήφιων δυαδικών αριθμών. Μια σταθερά 0 εφαρμόζεται στην τρίτη είσοδο του αθροιστή για το λιγότερο σημαντικό bit και το "σήμα μεταφοράς" του πιο σημαντικού bit είναι το πιο σημαντικό bit του αθροίσματος, το οποίο στη γενική περίπτωση θα είναι τετραψήφιος αριθμός .
Μέγεθος: px
Έναρξη εμφάνισης από τη σελίδα:
αντίγραφο
1 Διάλεξη 2. Σχήματα λειτουργικών στοιχείων (SFE) σε κάποια βάση. Η πολυπλοκότητα και το βάθος του σχήματος. Παραδείγματα. Μέθοδος σύνθεσης SFE από DNF. Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana N. Selezneva Lectures on Discrete Mathematics 2. 1ο έτος, ομάδα 141 Διαλέξεις Lomonosov στον ιστότοπο
2 Κυκλώματα από λειτουργικά στοιχεία Ας ορίσουμε κυκλώματα από λειτουργικά στοιχεία σε κάποια βάση. Ας μας δοθεί ένα σύνολο συναρτήσεων Boole B = (g 1 (x 1,..., x n1),..., g s (x 1,..., x ns)) P 2, όπου n 1, .. ., n s 0. Αυτό το σύνολο ονομάζουμε βάση. Σημειώστε ότι αυτή η έννοια της βάσης δεν σχετίζεται σε καμία περίπτωση με την έννοια της βάσης P 2, η οποία θεωρήθηκε στην άλγεβρα της λογικής. Κατά κανόνα, θα εξετάσουμε την τυπική βάση B 0 = (x&y, x y, x).
3 Ορισμός κυκλώματος λειτουργικών στοιχείων Ένα κύκλωμα λειτουργικών στοιχείων (SFE) στη βάση B 0 = (x&y, x y, x) είναι 1) ένα κατευθυνόμενο ακυκλικό γράφημα G = (V, E), κάθε κορυφή v V του οποίου έχει βαθμό d (v ) που δεν υπερβαίνει το δύο (d (v) 2). 2) κάθε κορυφή v με βαθμό ίση με 0 (d (v) = 0) ονομάζεται είσοδος (ή είσοδος κυκλώματος) και κάποια μεταβλητή Boole x i έχει εκχωρηθεί σε αυτήν. 3) όλες οι άλλες κορυφές (εκτός των εισόδων) ονομάζονται εσωτερικές κορυφές του κυκλώματος.
4 Ορισμός κυκλώματος από λειτουργικά στοιχεία (συνέχεια) 4) σε κάθε κορυφή v με βαθμό ίση με 1 (d (v) = 1) εκχωρείται ένα (λειτουργικό) στοιχείο άρνησης. Όλες αυτές οι κορυφές ονομάζονται μετατροπείς. 5) σε κάθε κορυφή v με βαθμό ίσο με 2 (d (v) = 2) εκχωρείται είτε ένα (συναρτητικό) στοιχείο σύνδεσης & είτε ένα (συναρτητικό) στοιχείο διαχωρισμού. Όλες οι κορυφές στις οποίες αποδίδονται στοιχεία ενός συνδέσμου ονομάζονται σύνδεσμοι, όλες οι κορυφές στις οποίες αποδίδονται στοιχεία ενός συνδέσμου ονομάζονται διαχωριστές.
5 Ορισμός κυκλώματος από λειτουργικά στοιχεία (συνέχεια) 6) Επιπλέον, ανά ζεύγος διαφορετικές μεταβλητές εξόδου y 1,..., y m αντιστοιχίζονται σε ορισμένες από τις κορυφές. Εάν δοθεί ένα CFE S, στις εισόδους του οποίου εκχωρούνται μόνο μεταβλητές x 1,..., x n, και με μεταβλητές εξόδου y 1,..., y m, τότε θα συμβολίσουμε αυτό το CFE μέσω S(x 1,. .., x n, y 1,..., ym).
6 Παράδειγμα SFE Παράδειγμα 1. SFE S(x 1, x 2, x 3 ; y 1, y 2, y 3):
7 Παράδειγμα SFE Παράδειγμα 1. Κατά κανόνα, τα SFE απεικονίζονται ως εξής S(x 1, x 2, x 3; y 1, y 2, y 3):
8 Προσδιορισμός της πολυπλοκότητας του CFE Η πολυπλοκότητα L(S) του CFE S είναι ο αριθμός των εσωτερικών κορυφών αυτού του CFE, δηλ. ο αριθμός των λειτουργικών στοιχείων στο SFE S.
9 Πολυπλοκότητα SPE Παράδειγμα 2. Πολυπλοκότητα SPE S:
10 Προσδιορισμός του βάθους μιας κορυφής CFE Με επαγωγή, προσδιορίζουμε το βάθος d(v) μιας κορυφής v στο CFE S. 1. Βάση επαγωγής. Κάθε είσοδος v του SPS έχει βάθος ίσο με 0: d(v) = Επαγωγική μετάβαση. 1) Εάν ένα τόξο από την κορυφή v 1 οδηγεί στον μετατροπέα v CFE S, τότε d(v) = d(v 1)) Εάν τόξα από τις κορυφές v 1 και v 2 οδηγούν στον σύνδεσμο ή τον διαχωριστή v CFE S, τότε d (v) = max(d(v 1), d(v 2)) + 1. Το βάθος D(S) ενός CFE S είναι το μέγιστο των βάθους των κορυφών του.
11 Βάθος SPE Παράδειγμα 3. Βάθος κορυφής SPE S και βάθος SPE S:
12 Προσδιορισμός της λειτουργίας του SFE Σε κάθε κορυφή του SFE, υλοποιείται (ή υπολογίζεται) μια συγκεκριμένη συνάρτηση Boolean. Με επαγωγή, ορίζουμε μια Boolean συνάρτηση που υλοποιείται στην κορυφή v του CFE S. 1) Εάν v είναι μια κορυφή εισόδου και η μεταβλητή x i έχει εκχωρηθεί σε αυτήν, τότε η συνάρτηση f v = x i πραγματοποιείται στην κορυφή v . 2) Εάν ένα τόξο από την κορυφή v 1 οδηγεί στον αντιστροφέα v, και η συνάρτηση f v1 πραγματοποιείται στην κορυφή v 1, τότε η συνάρτηση f v = f v1 πραγματοποιείται στην κορυφή v. 3) Εάν τόξα από τις κορυφές v 1 και v 2 οδηγούν στον σύνδεσμο (ή διαχωριστή) v, και οι συναρτήσεις f v1 και f v2 πραγματοποιούνται στις κορυφές v 1 και v 2, αντίστοιχα, τότε η συνάρτηση f v = f v1 & f v2 πραγματοποιείται στο κορυφή v (αντίστοιχα f v = f v1 f v2).
13 Λειτουργία του SFE Πιστεύεται ότι το SFE S(x 1,..., x n ; y 1,..., y m) υλοποιεί ένα σύστημα Boolean συναρτήσεων F S = (f 1,..., f m ) που υλοποιείται στις κορυφές εξόδου του y 1,..., ym.
14 Λειτουργία του SFE Παράδειγμα 4. Συναρτήσεις Boolean που υλοποιούνται στις κορυφές του SFE S: F S = (x 3, x 1 x 2, x 1 x 2 x 3 ).
15 Γραμμικό πρόγραμμα Γραμμικό πρόγραμμα με εισόδους x 1,..., x n πάνω από τη βάση B 0 = (x&y, x y, x) είναι μια ακολουθία z 1, z 2,..., z t, στην οποία για κάθε αριθμό j, j = 1,..., t, 1) είτε z j = x i ; 2) είτε z j = z k για k< j; 3) либо z j = z k &z l при k, l < j; 4) либо z j = z k z l при k, l < j. Линейная программа последовательно вычисляет значения z 1,..., z t как функции булевых переменных x 1,..., x n.
16 CFE και γραμμικά προγράμματα Είναι σαφές ότι ο υπολογισμός στο CFE μπορεί να ξαναγραφτεί με τη μορφή γραμμικού προγράμματος. Και αντίστροφα, κάθε γραμμικό πρόγραμμα μπορεί να αναπαρασταθεί ως ένα συγκεκριμένο CFE.
17 SFE και γραμμικά προγράμματα Παράδειγμα 5. SFE S αντιστοιχεί σε γραμμικό πρόγραμμα z 1 \u003d x 1 & x 2, z 2 \u003d x 3, z 3 \u003d z 1 z 2.
18 SFE και τα χαρακτηριστικά τους Τα σχήματα λειτουργικών στοιχείων είναι ένα υπολογιστικό μοντέλο. Τα χαρακτηριστικά SPE που εισήχθησαν από εμάς δείχνουν διαφορετικές πτυχές της υπολογιστικής απόδοσης. Η πολυπλοκότητα του SFE αντιστοιχεί στο χρόνο του διαδοχικού υπολογισμού. Το βάθος του SPE αντιστοιχεί στον παράλληλο υπολογιστικό χρόνο. Ο μέγιστος αριθμός κορυφών με το ίδιο βάθος στο SFE αντιστοιχεί στον αριθμό των επεξεργαστών στο παράλληλος υπολογισμός.
19 Παράδειγμα: το άθροισμα δύο bit Παράδειγμα 6. Κατασκευάστε ένα SFE σε τυπική βάση που υλοποιεί (υπολογίζει) το άθροισμα δύο bit x και y. Λύση. Ας γράψουμε έναν πίνακα με το άθροισμα δύο bit x και y. Αυτό το άθροισμα μπορεί να είναι ένας αριθμός με δύο δυαδικά ψηφία, επομένως εισάγουμε δύο μεταβλητές Boolean z 0, z 1 έτσι ώστε x + y = 2z 1 + z 0: x y z 1 z
20 Παράδειγμα: άθροισμα δύο bit Λύση (συνέχεια). Τότε z 0 = x y, z 1 = xy. Λαμβάνοντας υπόψη ότι x y = (x y) (x y), παίρνουμε CFE: Είναι σαφές ότι L(S 1) = 3, και D(S 1) = 3.
21 CFE σε αυθαίρετη βάση Παρομοίως, εισάγεται η έννοια του CFE σε αυθαίρετη βάση B P 2.
22 Παράδειγμα: το άθροισμα τριών bit Παράδειγμα 7. Κατασκευάστε ένα SFE στη βάση P2 2 (δηλαδή από όλες τις συναρτήσεις Boolean ανάλογα με δύο μεταβλητές) πραγματοποιώντας (υπολογίζοντας) το άθροισμα τριών bit x, y και z.
23 Παράδειγμα: άθροισμα τριών bit Λύση. Ομοίως με το παράδειγμα 6, γράφουμε έναν πίνακα με το άθροισμα τριών bit x, y και z. Αυτό το άθροισμα μπορεί επίσης να είναι ένας αριθμός με δύο δυαδικά ψηφία, επομένως εισάγουμε δύο μεταβλητές Boolean u 0, u 1, έτσι ώστε x + y + z = 2u 1 + u 0: x y z u 1 u
24 Παράδειγμα: άθροισμα τριών bit Λύση (συνέχεια). Τότε u 0 = x y z, u 1 = xy xz yz. Λαμβάνοντας υπόψη ότι xy xz yz = xy z(x y), λαμβάνουμε CFE: Βλέπουμε ότι L(S) = 5, και D(S) = 3.
25 Υλοποίηση της Boolean συνάρτησης του CFE Είναι δυνατόν να υλοποιηθεί μια αυθαίρετη Boolean συνάρτηση (ή ένα σύστημα Boolean συναρτήσεων) του CFE στη βάση B 0 = (x&y, x y, x); Μπορώ. Πώς μπορεί να δικαιολογηθεί αυτό; Για παράδειγμα, ναι. Επειδή (x&y, x y, x) είναι ένα πλήρες σύστημα στο P 2, μια αυθαίρετη Boolean συνάρτηση f μπορεί να αναπαρασταθεί από έναν τύπο μόνο μέσω σύνδεσης, διαχωρισμού και άρνησης. Για παράδειγμα, με τη μορφή ενός τέλειου DNF, εάν f 0, και με τη μορφή x & x, εάν f = 0. Και στη συνέχεια, χρησιμοποιώντας αυτό το DNF (τύπο), κατασκευάστε το αντίστοιχο CFE. Αυτή η μέθοδος κατασκευής SFE για συναρτήσεις Boolean ονομάζεται μέθοδος σύνθεσης DNF.
26 Σύνθεση του CFE από DNF Και τι πολυπλοκότητα θα είναι το CFE S με DNF για μια Boolean συνάρτηση f (x 1,..., x n) ανάλογα με n μεταβλητές; Ένα τέλειο DNF για μια συνάρτηση f θα περιέχει το πολύ 2 n στοιχειώδεις συνδέσμους. Κάθε στοιχειώδης σύνδεσμος είναι ένας σύνδεσμος n μεταβλητών ή των αρνήσεων τους.
27 Σύνθεση SFE από DNF Επομένως, το κύκλωμα θα έχει: n μετατροπείς για την υλοποίηση όλων των αρνήσεων των μεταβλητών x 1,..., x n ; με (n 1) σύνδεσμο για την υλοποίηση καθενός από το πολύ 2 n στοιχειώδεις συνδέσμους σε ένα τέλειο DNF. το πολύ (2 n 1) διαχωριστικό για την υλοποίηση του διαχωρισμού των στοιχειωδών συνδέσμων του DNF. Παίρνουμε ότι L(S) n + (n 1) 2 n + (2 n 1) n 2 n + n.
28 Πολυπλοκότητα μιας Boolean συνάρτησης Η πολυπλοκότητα L(f) μιας Boolean συνάρτησης f (x 1,..., x n) στην κλάση CFE είναι η ελάχιστη πολυπλοκότητα μεταξύ όλων των CFE που υλοποιούν τη συνάρτηση f. Έτσι, αποδείξαμε το θεώρημα: Θεώρημα 1. Για μια αυθαίρετη συνάρτηση f (x 1,..., x n) είναι αληθής η P 2, η L(f) n 2 n + n.
29 Προβλήματα για ανεξάρτητη λύση 1. Για μια Boolean συνάρτηση f (x 1, x 2, x 3) = (), κατασκευάστε ένα CFE στη βάση της τυπικής πολυπλοκότητας Για μια Boolean συνάρτηση f (x 1, x 2, x 3) = (), κατασκευάστε ένα CFE στη βάση της τυπικής πολυπλοκότητας Για μια Boolean συνάρτηση f (x 1, x 2, x 3, x 4) = x 1 x 2 x 3 x 4, κατασκευάστε ένα SFE στη βάση τυπικού βάθους Αποδείξτε ότι στην τυπική βάση L(x y) = 4.
30 Λογοτεχνία για διάλεξη 4 1. Yablonsky S.V. Εισαγωγή στα διακριτά μαθηματικά. Μ .: Γυμνάσιο, Μέρος V, κεφ. 2, με τους Gavrilov G.P., Sapozhenko A.A. Εργασίες και ασκήσεις σε διακριτά μαθηματικά. Μόσχα: Fizmatlit, Ch. Χ 1,1, 1,5, 1,7, 1,17, 1,18.
31 Τέλος Διάλεξης 4
Διάλεξη: Σχήματα λειτουργικών στοιχείων με καθυστερήσεις (SFES), αυτοματισμός των αντιστοιχίσεων τους. Αντιπροσωπεία ΚΑΒ ΦΕΖ. Απλοποιήσεις του CAV. Διακρίσεις και δυσδιάκριση των καταστάσεων CAV. Το θεώρημα του Μουρ
Διάλεξη: Το θεώρημα του Ansel σχετικά με τη διαίρεση ενός n-διάστατου κύβου σε αλυσίδες. Θεώρημα για τον αριθμό των μονότονων συναρτήσεων της άλγεβρας της λογικής. Θεώρημα για την αποκρυπτογράφηση μονότονων συναρτήσεων της άλγεβρας της λογικής. Λέκτορας - Αναπληρώτρια Καθηγήτρια Selezneva Svetlana
Διάλεξη: Πεπερασμένα αυτόματα με έξοδο (KAV). Αυτόματες λειτουργίες, μέθοδοι αντιστοίχισης τους. Θεώρημα για τον μετασχηματισμό περιοδικών ακολουθιών από αυτόματες συναρτήσεις. Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana Nikolaevna Selezneva
Διάλεξη: Μερικώς παραγγελθέντα σετ (POS). Διάγραμμα CHUM. Μέγιστα, ελάχιστα, μεγαλύτερα και μικρότερα στοιχεία. Αλυσίδες και αντιαλυσίδες, το μήκος και το πλάτος του άκρου της πανώλης. Το θεώρημα για τη διάσπαση του PL σε αντιαλυσίδες.
Διάλεξη 2. Ιδιότητες διωνυμικών συντελεστών. Άθροιση και μέθοδος δημιουργίας συναρτήσεων (τελική περίπτωση). Πολυωνυμικοί συντελεστές. Εκτιμήσεις για διωνυμικούς και πολυωνυμικούς συντελεστές. Εκτιμήσεις ποσών
Διάλεξη: Αλγόριθμος για την αναγνώριση της πληρότητας στο Π κ. κλειστές τάξεις. Κατηγορίες συναρτήσεων που διατηρούν σύνολα και διατηρούν κατατμήσεις, την κλειστότητά τους. Το θεώρημα του Kuznetsov για τη λειτουργική πληρότητα. Προολοκλήρωση μαθημάτων.
Διάλεξη 2. Συνδυαστική. Ιδιότητες διωνυμικών συντελεστών. Καταμέτρηση αθροισμάτων και μέθοδος δημιουργίας συναρτήσεων. Πολυωνυμικοί συντελεστές. Εκτιμήσεις για διωνυμικούς και πολυωνυμικούς συντελεστές. Ασυμπτωτικό
Διάλεξη: Συναρτήσεις πεπερασμένων τιμών. Στοιχειώδεις συναρτήσεις με τιμή k. Τρόποι προσδιορισμού συναρτήσεων με τιμή k: πίνακες, τύποι, 1η και 2η μορφή, πολυώνυμα. Πληρότητα. Θεώρημα για την πληρότητα του συστήματος Post. Λειτουργία Webb.
Διάλεξη 3. Ακολουθίες που καθορίζονται από επαναλαμβανόμενες σχέσεις. Ομογενείς και ανομοιογενείς γραμμικές επαναλαμβανόμενες εξισώσεις (LORU και LNRU). Κοινές αποφάσεις LORU και LNRU. Λέκτορας - Αναπληρώτρια Καθηγήτρια Selezneva Svetlana
Διάλεξη 15. Συναρτήσεις λογικών πεπερασμένων τιμών. Στοιχειώδεις Συναρτήσειςλογική k-value. Μέθοδοι για τον καθορισμό λογικών συναρτήσεων με τιμή k: πίνακες, τύποι, μορφές I και II, πολυώνυμα. Πληρότητα. Λέκτορας - Αναπληρώτρια Καθηγήτρια Selezneva
Διάλεξη: Συναρτήσεις λογικών πεπερασμένων τιμών. Στοιχειώδεις συναρτήσεις της k-valued λογικής. Μέθοδοι για τον καθορισμό λογικών συναρτήσεων με τιμή k: πίνακες, τύποι, μορφές I και II, πολυώνυμα. Πληρότητα. Λέκτορας - Αναπληρώτρια Καθηγήτρια Selezneva Svetlana
Διάλεξη: Συνάρτηση Möbius στο CCM. Συνάρτηση Möbius στον n-διάστατο κύβο. Τύπος αντιστροφής Möbius. Η αρχή της ένταξης-αποκλεισμού. Το πρόβλημα της μέτρησης του αριθμού των μεταθέσεων-διαταραχών. Λέκτορας - Αναπληρώτρια Καθηγήτρια Selezneva Svetlana
Διάλεξη 2. Ιδιότητες διωνυμικών συντελεστών. Μέθοδος δημιουργίας συναρτήσεων, υπολογισμός αθροισμάτων και απόδειξη ταυτοτήτων. Πολυωνυμικοί συντελεστές. Η αρχή της ένταξης-αποκλεισμού. Λέκτορας - Αναπληρώτρια Καθηγήτρια Selezneva Svetlana
Διάλεξη: Βασικές λειτουργίες. Τρία λήμματα για τις βασικές λειτουργίες. Το κριτήριο πληρότητας του Yablonsky. Κριτήριο πληρότητας Slupetsky. Λειτουργίες Schaeffer. Λέκτορας Αναπληρώτρια Καθηγήτρια Svetlana Nikolaevna Selezneva [email προστατευμένο]
Διάλεξη: Βασικοί συνδυαστικοί αριθμοί. Εκτιμήσεις και ασυμπτωτικές για συνδυαστικούς αριθμούς. Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana Nikolaevna Selezneva, σχολή του CMC του Κρατικού Πανεπιστημίου της Μόσχας με το όνομα M.V. Διαλέξεις Lomonosov στον ιστότοπο http://mk.cs.msu.su
Διάλεξη: Ιδιότητες διωνυμικών συντελεστών. Άθροιση και μέθοδος δημιουργίας συναρτήσεων (τελική περίπτωση). Πολυωνυμικοί συντελεστές. Εκτιμήσεις για διωνυμικούς και πολυωνυμικούς συντελεστές. Εκτιμήσεις για αθροίσματα διωνύμων
Διάλεξη: Πεπερασμένα αυτόματα με έξοδο. Μετασχηματισμός περιοδικών ακολουθιών από πεπερασμένα αυτόματα με έξοδο. Διακρίσεις καταστάσεων σε πεπερασμένα αυτόματα με έξοδο. Απλοποίηση μηχανών. Λέκτορας Selezneva
Διάλεξη: Σετ εξώφυλλο και εξώφυλλο μήτρας. Κλίση κάλυψης. Λήμμα καλύμματος κλίσης. Εκτιμήσεις για την καρδινάτητα του συνόλου σκίασης ενός κύβου ν-διάστατων. Εκτιμήσεις για το μήκος πολυωνυμικών κανονικών μορφών συναρτήσεων
Διάλεξη 5. Σετ εξώφυλλου και καλύμματος μήτρας. Κλίση κάλυψης. Λήμμα καλύμματος κλίσης. Εκτιμήσεις για την καρδινάτητα του συνόλου σκίασης του κύβου Boolean. Εκτιμήσεις για το μήκος πολυωνυμικών κανονικών μορφών Boolean
Διάλεξη 3. Ακολουθίες που καθορίζονται από επαναλαμβανόμενες σχέσεις. Ομογενείς και ανομοιογενείς γραμμικές επαναλαμβανόμενες εξισώσεις (LORU και LNRU). Κοινές αποφάσεις LORU και LNRU. Παραδείγματα Λέκτορας - Αναπληρώτρια Καθηγήτρια Selezneva
Διάλεξη 3. Σχέσεις σε σύνολα. Ιδιότητες. Τύπος συμπερίληψης-αποκλεισμού. Σχέση ισοδυναμίας. Μερική σχέση παραγγελίας. Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana N. Selezneva Διαλέξεις για διακριτά μοντέλα.
Διάλεξη 4. Χαρακτηριστικά πολυτιμών λογικών. Κλειστή τάξη, βάση κλειστής τάξης. Τα θεωρήματα των Yanov και Muchnik για την ύπαρξη σε λογικές πολλών αξιών κλειστών τάξεων χωρίς βάση και κλειστών τάξεων με αριθμήσιμο
Διάλεξη. Συναρτήσεις φυσικού ορίσματος (ακολουθία). Ομογενείς και ανομοιογενείς γραμμικές επαναλαμβανόμενες εξισώσεις (LORU και LNRU). Κοινές αποφάσεις LORU και LNRU. Παραδείγματα Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana Selezneva
Διάλεξη: Χρωματικός αριθμός γραφήματος. Κριτήριο για δίχρωμο γράφημα. Θεωρήματα πάνω και κάτω ορίων για τον χρωματικό αριθμό μιας γραφικής παράστασης. Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana N. Selezneva Διαλέξεις για διακριτά μοντέλα.
Διάλεξη: Γραφήματα και δίκτυα. Μια εκτίμηση για τον αριθμό των ψευδογράφων με q άκρα. Μια εκτίμηση για τον αριθμό των δέντρων με q άκρες. Επίπεδα γραφήματα. Ο τύπος του Euler για επίπεδα γραφήματα. Ο μεγαλύτερος αριθμός ακμών σε επίπεδα γραφήματα. μη επιπεδότητα
Διάλεξη 1. Συνδυαστική. Τοποθετήσεις, μεταθέσεις, τοποθετήσεις με επαναλήψεις, συνδυασμοί, συνδυασμοί με επαναλήψεις. Ο αριθμός τους. Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana N. Selezneva Τμήμα Μαθηματικής Κυβερνητικής
Διάλεξη: Ακολουθίες. Ομογενείς και μη ομογενείς γραμμικές επαναλαμβανόμενες εξισώσεις. Γενικές λύσεις γραμμικών επαναλαμβανόμενων ομογενών και ανομοιογενών εξισώσεων. Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana Nikolaevna Selezneva
Διάλεξη 8. Σελίδες χρωματισμού. Ισοδυναμία χρωματισμών ως προς την ομάδα. Δημιουργία συναρτήσεων. Μια σειρά απαρίθμησης για τους αριθμούς και μια σειρά απαρίθμησης για τις συναρτήσεις. Το θεώρημα του Πόγια. Λέκτορας Selezneva Svetlana Nikolaevna
Διάλεξη: Χρωματισμός. Ισοδυναμία χρωματισμών ως προς την ομάδα μετάθεσης. Θεώρημα Polya (ειδική περίπτωση). Δημιουργία συναρτήσεων. Μια σειρά απαρίθμησης για τους αριθμούς και μια σειρά απαρίθμησης για τις συναρτήσεις. Θεώρημα
Διάλεξη 2. Συνδετικοί κανονικοί τύποι. Έννοια, το απλό υπονοούμενο μιας συνάρτησης. Συντομευμένες συναρτήσεις CNF της άλγεβρας της λογικής. Μέθοδοι για την κατασκευή ενός συντομευμένου CNF. Λέκτορας Selezneva Svetlana Nikolaevna [email προστατευμένο]
Μαθηματικά μοντέλακαι μέθοδοι λογικής σύνθεσης VLSI Φθινόπωρο 2015 Διάλεξη 4 Σχέδιο διάλεξης Λογική βελτιστοποίηση συνδυαστικών λογικά κυκλώματα Διάφοροι τρόποιαναπαραστάσεις συναρτήσεων της άλγεβρας της λογικής (FAL)
Διάλεξη: Μη ντετερμινιστικά πεπερασμένα αυτόματα (NFA) χωρίς έξοδο. Ένα θεώρημα για τη σύμπτωση κλάσεων συνόλων λέξεων που επιτρέπεται από πεπερασμένα ντετερμινιστικά και πεπερασμένα μη ντετερμινιστικά αυτόματα. Διαδικασία
Διάλεξη 1. Επιλογές. Τοποθετήσεις, μεταθέσεις, τοποθετήσεις με επαναλήψεις, συνδυασμοί, συνδυασμοί με επαναλήψεις, ο αριθμός τους. Παραδείγματα. Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana Nikolaevna Selezneva Διαλέξεις για το μάθημα Discrete
Διάλεξη 1. Συνδυαστικά αντικείμενα: επιλογές, τοποθετήσεις, μεταθέσεις, τοποθετήσεις με επαναλήψεις, συνδυασμοί, συνδυασμοί με επαναλήψεις, ο αριθμός τους. Συνδυαστικοί αριθμοί: παραγοντικοί, φθίνοντες παραγοντικοί, διωνυμικοί
ΔΙΑΛΕΞΗ 4 ΣΧΗΜΑΤΑ ΑΠΟ ΛΕΙΤΟΥΡΓΙΚΑ ΣΤΟΙΧΕΙΑ 1. Βασικοί ορισμοί Πρώτα απ 'όλα, είναι απαραίτητο να εξεταστεί η σύνθεση. Μια συνάρτηση μπορεί να αναπαρασταθεί ως ένα "μαύρο κουτί" που έχει μια είσοδο και μια έξοδο. Αφήνω
Διάλεξη 2. Αλγόριθμος αναγνώρισης πληρότητας στο Π κ. Το θεώρημα του Kuznetsov. κλειστές τάξεις. Κατηγορίες συναρτήσεων που διατηρούν ένα σύνολο. Κλάσεις συναρτήσεων που διατηρούν το διαμέρισμα. Προολοκλήρωση μαθημάτων. Ομιλητής Σελεζνέβα
Διάλεξη 3. Πολυώνυμο Zhegalkin. Μέθοδοι κατασκευής του πολυωνύμου της συνάρτησης Zhegalkin. Γραμμική άρρητη συνάρτηση. Γραμμική συνδετική κανονική μορφή (LCNF). Εύρεση όλων των γραμμικών συναρτήσεων. Εξέταση
Διάλεξη 2. Δημιουργία συναρτήσεων: μέτρηση συνδυαστικών αθροισμάτων και απόδειξη ταυτοτήτων, λίστα συνδυαστικών αντικειμένων. Η αρχή της ένταξης-αποκλεισμού. Μετρώντας τον αριθμό των μεταθέσεων-διαταραχών. Ομιλητής -
Διάλεξη 5. Γραφήματα. Σελίδες χρωματισμού γραφημάτων. Ο χρωματικός αριθμός του γραφήματος. Κριτήριο διχρωματικότητας για γράφημα. Ανώτερα όρια για τον χρωματικό αριθμό ενός γραφήματος. Ομιλητής Selezneva Svetlana Nikolaevna [email προστατευμένο]Διαλέξεις
Διάλεξη: Πεπερασμένα αυτόματα (ΚΑ) χωρίς έξοδο (πεπερασμένα αυτόματα-αναγνωριστές). Διαγράμματα μετάβασης. Σετ (γλώσσες) αυτόματα. Λήμμα για τις ιδιότητες των συνόλων αυτόματων. Ένα παράδειγμα ενός μη αυτόματου συνόλου. Ομιλητής
Διάλεξη 1. Συναρτήσεις πεπερασμένων τιμών. Στοιχειώδεις συναρτήσεις με τιμή k. Τρόποι προσδιορισμού συναρτήσεων με τιμή k: πίνακες, τύποι, 1η και 2η μορφή, πολυώνυμα. Πληρότητα. Θεώρημα για την πληρότητα του συστήματος Post. Λειτουργία Webb.
Διάλεξη 7 Μοντέλο γραφήματος για το έργο της διανομής των πτήσεων. Ο χρωματικός αριθμός του γραφήματος. Κριτήριο για να είναι δίχρωμο ένα γράφημα.
Το μάθημα «Βασικές αρχές Κυβερνητικής» για φοιτητές ειδικότητας 01.02.09.01 (μαθηματικά και λογισμικόυπολογιστές) 1. γενικές πληροφορίες(προπονητικό φόρτο, μορφές ελέγχου κ.λπ.). Το μάθημα είναι
Διάλεξη 6. Γραφήματα. Κληρονομικές ιδιότητες γραφημάτων. Εκτίμηση του αριθμού των ακμών σε γραφήματα με κληρονομική ιδιότητα. Ακραία Γραφήματα. Ο μεγαλύτερος αριθμός ακμών σε επίπεδα και χωρίς τρίγωνα γραφήματα με δεδομένο
Math-Net.Ru Παν-ρωσική μαθηματική πύλη DS Romanov, Μέθοδος σχεδιασμού κυκλωμάτων εύκολα στη δοκιμή που επιτρέπουν δοκιμές ελέγχου μονάδας σταθερού μήκους, Diskr. Ματ., 2014, τόμος 26, τεύχος 2,
Διάλεξη: Πεπερασμένα αυτόματα χωρίς έξοδο, ντετερμινιστικά και μη ντετερμινιστικά. Ένα θεώρημα για τη σύμπτωση κλάσεων συνόλων λέξεων που επιτρέπεται από πεπερασμένα ντετερμινιστικά και μη ντετερμινιστικά αυτόματα. Διαδικασία
Πρακτική δουλειά 2 Κατασκευή κανονικών μορφών λογικής συνάρτησης Σκοπός της εργασίας: Να μάθουν πώς να χτίζουν συνδετικές, διαζευκτικές, τέλειες κανονικές μορφές λογικής συνάρτησης Περιεχόμενο εργασίας: Βασικό
Σεμινάριο για την πολυπλοκότητα των συναρτήσεων Boole Διάλεξη 1: Εισαγωγή A. Kulikov Computer Science club στο POMI http://compsciclub.ru 25/09/2011 25/09/2011 1 / 26 Σχέδιο διάλεξης 1 Συναρτήσεις Boole 2 κυκλώματα Boole 3 Σχεδόν
Πρακτική εργασία 1 Ανάλυση και σύνθεση συστημάτων λογικού και ρελέ ελέγχου
Διάλεξη: Κανονικές εκφράσεις και κανονικά σύνολα. Το θεώρημα του Kleene για τη σύμπτωση τάξεων συνόλων αυτόματα και κανονικών συνόλων. Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana Nikolaevna Selezneva Διαλέξεις για τα διακριτά μαθηματικά
Διάλεξη 3 Boolean algebras and Boolean functions Boolean algebras Η έννοια των αλγεβρικών συστημάτων Ένα αλγεβρικό σύστημα ή μια αλγεβρική δομή είναι ένα σύνολο συμβόλων κάποιου αλφαβήτου (φορέας) με δεδομένο
Διάλεξη 5. Γραφήματα. Παραδείγματα εφαρμογών γραφημάτων. έργο μεταφοράς. Ροή στο δίκτυο, Θεώρημα Ford και Fulkerson για την τιμή της μέγιστης ροής στο δίκτυο. Αλγόριθμος για την κατασκευή της μέγιστης ροής στο δίκτυο. Ομιλητής
Διάλεξη: Γραφήματα. Παραδείγματα εφαρμογών γραφημάτων. έργο μεταφοράς. Ροή στο δίκτυο, Θεώρημα Ford και Fulkerson για την τιμή της μέγιστης ροής στο δίκτυο. Αλγόριθμος για την κατασκευή της μέγιστης ροής στο δίκτυο. Ομιλητής -
Μάθημα 8 Θυμηθείτε ότι για αυθαίρετα σύνολα A και B υπάρχουν σύνολα A B = (x x A και x B). (τομή Α και Β) A B = (x x A ή x B); (ένωση Α και Β) A \ B = (x x A και x / B) (διαφορά Α και Β).
Διάλεξη 7. Αριθμοί Ramsey. Ανώτερο όριο για τον αριθμό Ramsey. Κάτω όριο για τον αριθμό Ramsey. Λέκτορας Selezneva Svetlana Nikolaevna [email προστατευμένο]σχολή του CMC του Κρατικού Πανεπιστημίου της Μόσχας με το όνομα M.V. Διαλέξεις Lomonosov στον ιστότοπο http://mk.cs.msu.ru
Διάλεξη: Γραφήματα. ΒΑΣΙΚΕΣ ΕΝΝΟΙΕΣ. Συνδεδεμένα γραφήματα. Δέντρα. Δέντρο πυρήνα. Ο αριθμός των κρεμασμένων κορυφών στο εκτεινόμενο δέντρο. Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana N. Selezneva Διαλέξεις για διακριτά μοντέλα. αρχή,
Διάλεξη 11. Κυκλώματα Boolean. Διακριτά Μαθηματικά, HSE, Σχολή Επιστήμης Υπολογιστών (Φθινόπωρο 2014 Άνοιξη 2015) Ένα κύκλωμα Boole σε μεταβλητές x 1,..., x n είναι μια ακολουθία Boolean συναρτήσεων g
ΕΓΚΕΚΡΙΜΕΝΟΣ Αντιπρύτανης Ακαδημαϊκών Υποθέσεων Yu. A. Samarsky 10 Ιουνίου 2008 ΠΡΟΓΡΑΜΜΑ ΚΑΙ ΚΑΘΗΚΟΝΤΑ για το μάθημα ΔΙΑΚΡΙΤΕΣ ΔΟΜΕΣ στην κατεύθυνση 010600 σχολή του FIVT Τμήμα ανάλυσης δεδομένων μάθημα II εξάμηνο 4 Δύο
Lomonosov Moscow State University Faculty of Computational Mathematics and Cybernetics S. A. Lozhkin ΣΤΟΙΧΕΙΑ ΤΗΣ ΘΕΩΡΙΑΣ ΣΥΝΘΕΤΗΣΗΣ ΔΙΑΚΡΙΤΩΝ ΣΥΣΤΗΜΑΤΩΝ ΕΛΕΓΧΟΥ Μόσχα 2016 Περιεχόμενα
Διάλεξη: Κληρονομικές ιδιότητες γραφημάτων. Ακραία Γραφήματα. Αριθμοί Ramsey. Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana Nikolaevna Selezneva, σχολή του CMC του Κρατικού Πανεπιστημίου της Μόσχας με το όνομα M.V. Lomonosov Διαλέξεις στον ιστότοπο http://mk.cs.msu.su Heritary
Διάλεξη: Λειτουργίες σε πεπερασμένα σύνολα αυτόματων. Συμπλήρωση, ένωση, διασταύρωση, προϊόν και επανάληψη συνόλων αυτόματων, ο αυτοματισμός τους. Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana Nikolaevna Selezneva Διαλέξεις
Υπουργείο Ρωσική Ομοσπονδίαστις Επικοινωνίες και την Πληροφορία Κρατική Ακαδημία Τηλεπικοινωνιών και Πληροφορικής της Περιφέρειας Βόλγα Τμήμα Ανώτατων Μαθηματικών Εγκρίθηκε από το Μεθοδολογικό Συμβούλιο PGATI 29 Μαρτίου 2002
Διάλεξη 5. Χρωματισμοί ακμών γραφημάτων. Ο χρωματικός δείκτης του γραφήματος. Χρωματικός δείκτης διμερών γραφημάτων. Άνω και κάτω όρια για τον χρωματικό δείκτη ενός γραφήματος. Λέκτορας Selezneva Svetlana Nikolaevna [email προστατευμένο]
Math-Net.Ru Παν-ρωσική μαθηματική πύλη NP Red'kin, Σε κυκλώματα που δέχονται σύντομες μεμονωμένες διαγνωστικές δοκιμές, Diskr. Mat., 1989, τόμος 1, τεύχος 3, 71 76 Use of the All-Russian
ΜΑΘΗΜΑΤΙΚΗ ΛΟΓΙΚΗ(1) Εργασίες για πρακτικές ασκήσεις 1. Άλγεβρα δηλώσεων Μια πρόταση είναι μια τιμή που μπορεί να πάρει δύο τιμές: true και false. Οι δηλώσεις σημειώνονται με κεφαλαία γράμματα
31. Σχέδια λειτουργικών στοιχείων, κανόνες κατασκευής και λειτουργίας, μέθοδος σύνθεσης sfe με βάση sdnf και sknf.
ΟρισμόςΟρισμός.Ένα λειτουργικό στοιχείο είναι ένα μαθηματικό μοντέλο ενός στοιχειώδους διακριτού μετατροπέα, ο οποίος, σύμφωνα με έναν ορισμένο νόμο, μετατρέπει τα σήματα που λαμβάνει στην είσοδο σε σήμα στην έξοδο του μετατροπέα. Από λειτουργικά στοιχεία, με τη βοήθεια ορισμένων κανόνων, είναι δυνατή η κατασκευή μοντέλων που είναι πιο σύνθετα στη δομή και τη λειτουργία - διαγράμματα λειτουργικών στοιχείων. Σε αυτά τα μοντέλα, τα σήματα εισόδου και εξόδου κωδικοποιούνται με τα σύμβολα 0 και 1.
Κανόνες κατασκευής.Για να ληφθούν πολύπλοκα SPE από απλούστερα, εφαρμόζονται διαδοχικά σε αυτά οι λειτουργίες διαχωρισμού της εισόδου ή της εξόδου του κυκλώματος, της σύνδεσης ενός λειτουργικού στοιχείου στο κύκλωμα και της σύνδεσης του λειτουργικού στοιχείου στην είσοδο ή την έξοδο του κυκλώματος. Αυτές οι πράξεις μοιάζουν με τους κανόνες για τη λήψη ενός σύνθετου τύπου από απλούστερους χρησιμοποιώντας υπέρθεση.
Σύνθεση ΣΦΕ.Δεδομένου ότι ο διαχωρισμός, ο σύνδεσμος και η άρνηση μορφή πλήρες σύστημαστην τάξη R 2, στη συνέχεια οποιαδήποτε Boolean συνάρτηση από nορίσματα μπορούν να υλοποιηθούν από ένα κύκλωμα λειτουργικών στοιχείων - διαχωριστές, συνδέσμους και μετατροπείς - με nεισόδους και μία έξοδο. Για να το κάνετε αυτό, μπορείτε, για παράδειγμα, να εκφράσετε μια δεδομένη συνάρτηση Boole ως SDNF ή SKNF και στη συνέχεια να «συνθέσετε» τον τύπο που προκύπτει με τη μορφή ενός κυκλώματος λειτουργικών στοιχείων, εφαρμόζοντας διαδοχικά τις λειτουργίες διαχωρισμού, ένωσης και σύνδεσης που αναφέρονται πάνω από.
32. Μέθοδος σύνθεσης SPE που βασίζεται στη συμπαγή υλοποίηση όλων των συνδέσμων με χρήση καθολικού πολλαπλού πόλου, η πολυπλοκότητα των κυκλωμάτων που προκύπτουν.
Ορισμός. Μια συνάρτηση από n ορίσματα ονομάζεται δυαδική συνάρτηση (ή συνάρτηση της άλγεβρας της λογικής) εάν συσχετίζει έναν αριθμό με κάθε σύνολο.
Για να ορίσουμε συναρτήσεις Boolean, θα χρησιμοποιήσουμε πίνακες, διανύσματα, τύπους και γραφήματα. Ας πάρουμε τον ακόλουθο συμβολισμό: είναι το σύνολο όλων των συνόλων, όπου.
Ορισμός.Ένα λειτουργικό στοιχείο είναι ένα μαθηματικό μοντέλο ενός στοιχειώδους διακριτού μετατροπέα, ο οποίος, σύμφωνα με έναν ορισμένο νόμο, μετατρέπει τα σήματα που λαμβάνει στην είσοδο σε σήμα στην έξοδο του μετατροπέα. Από λειτουργικά στοιχεία, με τη βοήθεια ορισμένων κανόνων, είναι δυνατή η κατασκευή μοντέλων που είναι πιο σύνθετα στη δομή και τη λειτουργία - διαγράμματα λειτουργικών στοιχείων. Σε αυτά τα μοντέλα, τα σήματα εισόδου και εξόδου κωδικοποιούνται με τα σύμβολα 0 και 1.
Μέθοδος σύνθεσης SPE που βασίζεται στη συμπαγή υλοποίηση όλων των συνδέσμων με χρήση ενός καθολικού πολυπόλου. Αυτή η μέθοδος βασίζεται επίσης στην αναπαράσταση της συνάρτησης με τη μορφή SDNF, αλλά σας επιτρέπει να δημιουργήσετε λιγότερα σύνθετα σχήματαλόγω της πιο συμπαγούς εφαρμογής των συνδέσμων. Η αποσύνθεση μιας συνάρτησης στο SDNF μπορεί να περιέχει συνδέσμους που έχουν κοινούς παράγοντες. Εάν δύο τέτοιοι σύνδεσμοι υλοποιούνται από ένα υποκύκλωμα σε ένα μπλοκ, τότε αυτό θα απαιτήσει συνδέσμους τουλάχιστον έναν λιγότερο από ό,τι απαιτούνταν πριν, με ανεξάρτητη υλοποίηση όλων των συνδέσμων με την πρώτη μέθοδο σύνθεσης. Μια συμπαγής υλοποίηση όλων των πιθανών συνδέσμων μήκους nμπορεί να επιτευχθεί χρησιμοποιώντας ένα επαγωγικά κατασκευασμένο καθολικό πολυπολικό που έχει nεισροές και 2 n εξόδους, όπου n = 1,2,3,… Τα πλεονεκτήματα της μεθόδου είναι ιδιαίτερα αισθητά όταν απαιτείται να εφαρμοστεί ένα σύστημα πολλών Boolean συναρτήσεων χρησιμοποιώντας ένα κύκλωμα. Σε αυτήν την περίπτωση, θα ήταν δυνατό να διαιρεθούν και στη συνέχεια να περάσουν μέσα από διαχωριστές εκείνες οι έξοδοι του καθολικού πολυπόλου που αντιστοιχούν στους συνδέσμους που περιλαμβάνονται στο SDNF των συναρτήσεων του δεδομένου συστήματος. Αυτό θα επέτρεπε να τα βγάλουμε πέρα με λιγότερους συνδέσμους από ό,τι αν κάθε λειτουργία ενός δεδομένου συστήματος υλοποιούνταν ανεξάρτητα από το δικό του υποκύκλωμα.
Η πολυπλοκότητα ενός τέτοιου πολυπόλου είναι ίση με μεγάλο() =.
Αν το κύκλωμα των λειτουργικών στοιχείων Σ περιέχει ακριβώς rλειτουργικά στοιχεία, τότε λέμε ότι έχει πολυπλοκότητα rκαι γράψτε το ως εξίσωση μεγάλο(Σ) = r.
| " |
Διάλεξη 2
(SFE) σε κάποια βάση. Πολυπλοκότητα και βάθος
σχέδιο. Παραδείγματα. Μέθοδος σύνθεσης SFE από DNF.
Λέκτορας - Αναπληρώτρια Καθηγήτρια Svetlana Nikolaevna Selezneva
Διαλέξεις με θέμα «Διακριτά Μαθηματικά 2».
1ο μάθημα, ομάδα 141,
σχολή του CMC του Κρατικού Πανεπιστημίου της Μόσχας με το όνομα M.V. Λομονόσοφ
Διαλέξεις στον ιστότοπο http://mk.cs.msu.su
Παραδείγματα SPE Σύνθεση SPE από DNF
Κυκλώματα από λειτουργικά στοιχεία
Ας ορίσουμε κυκλώματα λειτουργικών στοιχείων σε κάποια βάση.
Ας μας δοθεί ένα σύνολο συναρτήσεων Boole B = (g1 (x1,..., xn1),..., gs (x1,..., xns)) P2, όπου n1,..., ns 0.
Ας ονομάσουμε αυτό το σύνολο τη βάση.
Σημειώστε ότι αυτή η έννοια της βάσης δεν σχετίζεται σε καμία περίπτωση με την έννοια της βάσης P2, η οποία θεωρήθηκε στην άλγεβρα της λογικής.
Κατά κανόνα, θα εξετάσουμε την τυπική βάση B0 = (x&y, x y, x ).
SFE Παραδείγματα Σύνθεση SFE από DNF Ορισμός κυκλώματος από λειτουργικά στοιχεία
1) ένα κατευθυνόμενο άκυκλο γράφημα G = (V, E), του οποίου κάθε κορυφή v V έχει βαθμό d (v) που δεν υπερβαίνει τους δύο (d (v) 2).
2) κάθε κορυφή v με βαθμό ίση με 0 (d (v) = 0) ονομάζεται είσοδος (ή είσοδος κυκλώματος) και σε αυτήν έχει εκχωρηθεί κάποια Boolean μεταβλητή xi.
3) όλες οι άλλες κορυφές (εκτός των εισόδων) ονομάζονται εσωτερικές κορυφές του κυκλώματος.
4) σε κάθε κορυφή v με βαθμό ίσο με 1 (d (v) = 1) εκχωρείται ένα (συναρτητικό) στοιχείο άρνησης. Όλες αυτές οι κορυφές ονομάζονται μετατροπείς.
5) σε κάθε κορυφή v με βαθμό ίσο με 2 (d (v) = 2) εκχωρείται είτε ένα (συναρτητικό) στοιχείο σύνδεσης & είτε ένα (συναρτητικό) στοιχείο διαχωρισμού. Όλες οι κορυφές στις οποίες αποδίδονται στοιχεία ενός συνδέσμου ονομάζονται σύνδεσμοι, όλες οι κορυφές στις οποίες αποδίδονται στοιχεία ενός συνδέσμου ονομάζονται διαχωριστές.
Παραδείγματα CFE Σύνθεση CFE από DNF Ορισμός κυκλώματος από λειτουργικά στοιχεία (συνέχεια)
6) Επιπλέον, ανά ζεύγος διαφορετικές μεταβλητές εξόδου y1,..., ym αντιστοιχίζονται σε ορισμένες από τις κορυφές.
Εάν δοθεί ένα CFE S, στις εισόδους του οποίου εκχωρούνται μόνο οι μεταβλητές x1,..., xn, και με μεταβλητές εξόδου y1,..., ym, τότε θα συμβολίσουμε αυτό το CFE με S(x1,..., xn, y1,... ., ym).
Παραδείγματα SPE Σύνθεση SPE από DNF
– – –
Προσδιορισμός του βάθους μιας κορυφής CFE Με επαγωγή, προσδιορίζουμε το βάθος d(v) μιας κορυφής v στο CFE S.
1. Βάση επαγωγής. Κάθε είσοδος v του SPE S έχει βάθος ίσο με 0: d(v) = 0.
– – –
Το SFE και τα χαρακτηριστικά τους Τα σχήματα λειτουργικών στοιχείων είναι ένα υπολογιστικό μοντέλο.
Τα χαρακτηριστικά SPE που εισήχθησαν από εμάς δείχνουν διαφορετικές πτυχές της υπολογιστικής απόδοσης.
Η πολυπλοκότητα του SFE αντιστοιχεί στο χρόνο του διαδοχικού υπολογισμού.
Το βάθος του SPE αντιστοιχεί στον παράλληλο υπολογιστικό χρόνο.
Ο μέγιστος αριθμός κορυφών με το ίδιο βάθος στο CFE αντιστοιχεί στον αριθμό των επεξεργαστών στον παράλληλο υπολογισμό.
Παραδείγματα CFE Σύνθεση CFE από DNF Παράδειγμα: το άθροισμα τριών bit Λύση. Ομοίως με το παράδειγμα 6, γράφουμε έναν πίνακα με το άθροισμα τριών bit x, y και z. Αυτό το άθροισμα μπορεί επίσης να είναι ένας αριθμός με δύο δυαδικά ψηφία, οπότε εισάγουμε δύο δυαδικές μεταβλητές
u0, u1 έτσι ώστε x + y + z = 2u1 + u0:
– – –
Λογοτεχνία για τη διάλεξη 4
1. Yablonsky S.V. Εισαγωγή στα διακριτά μαθηματικά. Μ.:
Ανώτατο Σχολείο, 2001. Μέρος V, Ch. 2, σελ. 336-355.
2. Gavrilov G.P., Sapozhenko A.A. Εργασίες και ασκήσεις σε διακριτά μαθηματικά. Μ.: Fizmatlit, 2004. Ch. Χ 1,1, 1,5, 1,7, 1,17, 1,18.
Παραδείγματα SPE Σύνθεση SPE από DNF
Φόρτωση...