Sljedeći "inženjersko-konstruktivni" smisao može se dati predstavljanju Bulovih funkcija formulama. Formulu F (x 1, ..., xn) nad nekim proizvoljno fiksnim skupom F smatraćemo "crnom kutijom", određenim uređajem, na čiji se ulaz unose svi mogući skupovi vrijednosti varijabli, i izlaz koji odgovara ovim skupovima vrijednosti funkcije f predstavljene formulom F (slika 6.22).
Da bismo razumjeli kako funkcionira "crna kutija", moramo rastaviti proces konstruiranja formule iz podformula. Dolazak do "osnovnih" podformula, tj. elemenata skupa F, dolazimo do "građevinskih blokova", strukturnih elemenata od kojih je sastavljena "crna kutija" koja izračunava funkciju f. Svaku funkciju "baze" F izračunava odgovarajući "čvor", koji se smatra najmanjom strukturnom jedinicom naše "crne kutije", a njena unutrašnja struktura se više ne analizira.
Primjer 6.22. Odaberimo standardnu osnovu za skup F. Tada se formula preko standardne baze, koja predstavlja funkciju ~ (ekvivalentnost), konstruira na sljedeći način:
Proračun prema ovoj formuli (i proces njegove konstrukcije od elemenata standardne osnove) može se shematski prikazati kao što je prikazano na sl. 6.23.
Varijabla x 1 (tačnije, vrijednost ove varijable) se dovodi na ulaz konstruktivnog elementa koji se zove inverter (slika 6.24, a) i izračunava negaciju. Negativni x 1 uklonjen sa izlaza pretvarača, tj. funkcija x 1, se dovodi na jedan od ulaza konjunkora (slika 6.24, b), na čiji se drugi ulaz dovodi varijabla x 2. Na izlazu spojnika pojavljuje se funkcija x 1 x 2. Izračunavanje funkcije x 1 x 2 može se pratiti na sličan način, obje ove funkcije se unose na ulaze disjunktora (slika 6.24, c), iz čijeg se izlaza dobija funkcija x 1 x 2 ∨ x 1 x 2 se uklanja (ovo nije ništa drugo do zbir po modulu 2: x 1 ⊕ x 2). I konačno, ova funkcija se dovodi na ulaz pretvarača, na čijem se izlazu već dobija funkcija ~ (ekvivalencija). #
Tako dolazimo do ideje "kola" - matematičkog modela kalkulatora Booleove funkcije, predstavljenog određenom formulom, sastavljenom od strukturnih elemenata, od kojih svaki izračunava jednu od "osnovnih" Booleovih funkcija. U opštem slučaju, "kolo" izračunava Boolean operator, a svaka koordinatna funkcija ovog operatora se uklanja iz jednog od izlaza kola.
Matematički, "šema" je definirana kao usmjereni graf posebne vrste, u kojem su označeni i vrhovi i lukovi.
Uvedemo oznaku: ako je F neki skup Bulovih funkcija, onda sa F (n) označavamo podskup F koji se sastoji od svih funkcija n varijabli (n≥0).
Definicija 6.14. Neka su skupovi fiksni: F (Booleove funkcije) i X (Booleove varijable).
Dijagram funkcionalnih elemenata na bazi F ∪ X (C Φ E), ili jednostavno kontrahovan preko baze F ∪ X, također (F, X) -šema, naziva se otvorenim usmjerenim grafom (tj. mrežom), čiji je svaki vrh označen jednim od elemenata skupa FU X tako da su ispunjeni sljedeći zahtjevi:
- svaki ulaz mreže je označen ili nekom promenljivom iz X, ili nekom konstantom iz F (0);
- ako je vrh v mreže označen funkcijom f od n varijabli (tj. f ∈ F (n)), tada je njegov polustepen ulaska jednak n, a na skupu lukova koji ulaze u vrh v, numeracija (jedan prema jedan) je data tako da je svaki luk numerisan od 1 do n.
Ako se osnova podrazumijeva, onda ćemo reći jednostavno "šema". Osim toga, ako je skup varijabli fiksiran "jednom za svagda" i kada se razmatraju različite sheme mijenjamo samo skup funkcija F, tada, kao što smo to učinili, uvodeći koncepte formule i superpozicije nad datom bazom, mi će govoriti o SFE preko baze F, pretpostavljajući svaki put, što znači jednom fiksni skup varijabli X, koji (ako to ne šteti tačnosti) se ne spominje.
Sada indukcijom definišemo pojam boolean funkcija izračunata od strane vrha kola .
Definicija 6.15. Neka se da CFE S preko baze F ∪ X, čiji je skup vrhova V.
- Pretpostavlja se da svaki ulaz CFE izračunava Booleovu funkciju kojom je označen (tj. neku varijablu ili konstantu).
- Ako je vrh v ∈ V označen funkcijom f ∈ F (n), luk sa brojem i (1≤i≤n) koji ulazi u njega dolazi iz vrha ui ∈ V, koji izračunava funkciju gi, tada je vrh v izračunava superpoziciju f (g 1, ..., gn).
Dakle, ako svaki vrh CFE-a nad F izračunava neku funkciju, tada je redoslijed kojim su funkcije g 1, ..., gn nabrojane, zamjenjene na mjestima varijabli funkcije f, bitan u općem slučaju . Prirodno je nazvati Bulovu funkciju f u n varijabli komutativnom ako čuva svoju vrijednost pod proizvoljnom permutacijom svojih varijabli. U ovom slučaju ne moramo brinuti o numeraciji lukova koji ulaze u vrh kruga, označenih takvom funkcijom.
Primjer 6.23. Razmotrite SPE na sl. 6.25. Vrhovi v 1 i v 2 su ulazi u SFE. Ovi vrhovi izračunavaju funkcije x i y, respektivno. Tada vrh v 3, kao i vrh v 4, prema definiciji 6.15, izračunava funkciju x | y (Schaefferov potez), a vrh v 5 (izlaz mreže) izračunava funkciju (x | y) l (x | y), za koju je poznato da je jednako konjunkciju x y.
SPE prikazan na sl. 6.26 ima dva izlaza koji izračunavaju funkcije (x | x) | (y | y) = x ∨ y i (x | y) | (x | y) = x y.
Definicija 6.16. Boolean funkcija izračunata CFE preko baze F ∪ X, je funkcija izračunata bilo kojim od njenih izlaza.
Dakle, CFE izračunava tačno koliko Booleovih funkcija, koliko izlaza. SFE na sl. 6.25 izračunava jednu funkciju, a SPE na sl. 6.26 - dva.
U opštem slučaju, ako je (x 1, ..., x n) skup svih varijabli koje služe kao oznake za ulaze kola S preko baze F ∪ X sa m izlaza, CFE S definira prikaz logičke kocke B n u logičku kocku B m, tj. boolean operator.
Napomena 6.10. U nekim slučajevima, funkcija izračunata datim SFE je nešto drugačije definirana, pod pretpostavkom da je to funkcija izračunata bilo kojim vrhom iz podskupa odabranih SFE vrhova. Konkretno, to mogu biti izlazi. U svakom slučaju, dogovorimo se da iz odabranih (u upravo naznačenom smislu) vrhova kola nacrtamo "izlaznu" strelicu. #
Dakle, svaki krug kapija izračunava neki Bulov operator, posebno ako je broj izlaza kola jednak 1, onda izračunava neku Booleovu funkciju.
Može se dokazati i obrnuto: za bilo koji Bulov operator, SFE se može konstruisati preko baze F, gde je F kompletan skup koji izračunava dati operator.
Funkciju y 1 predstavljamo u Žegalkinovoj bazi. Koristeći de Morganove zakone, dobijamo
(podsjetimo da je zbir po modulu 2 bilo kojeg parnog broja jednakih članova jednak 0).
y 1 = x 1 x 2 ⊕ x 1 x 3 ⊕ x 2 x 3 = x 1 x 2 ⊕ x 3 (x 1 ⊕ x 2).
SFE za Boolean operator dat u tabeli. 6.9, preko baze Žegalkina prikazana je na Sl. 6.27.
Prilikom dizajniranja SFE-a, korisno je imati na umu numerički parametar koji se zove njegova složenost.
Složenost SFE je broj njegovih vrhova koji nisu inputi.
Prikazano na sl. 6.27 CFE preko baze Žegalkina ima složenost 5.
Razmotrimo sada CFE za istog operatera preko standardne osnove.
Prema tabeli (vidi tabelu 6.9), konstruišemo SDNF za funkciju y 2:
y 2 = x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3.
Karnotova karta za ovu funkciju, prikazana na Sl. 6.28 pokazuje da se ne može minimizirati (tačnije, gore napisani SDNF je minimalni DNF za ovu funkciju). Ali možete ići drugim putem. Možemo uzeti u obzir tabelu. 6.9 kao tabela koja definiše parcijalnu logičku funkciju y 2 = y 2 (x 1 x 2 x 3 y 1). Minimiziranjem ove funkcije po
Karnotova karta * prikazana na sl. 6.29, dobijamo
* Na ovoj karti smo označili skupove na kojima funkcija uzima vrijednost 0, stavljajući nule u odgovarajuće ćelije. Stoga želimo još jednom skrenuti pažnju na činjenicu da ne treba brkati nule sa crticama: crtica u ćeliji karte koja navodi djelomičnu funkciju znači da vrijednost funkcije nije definirana na ovom skupu, tj. nije ni 0 ni 1.
y 2 = x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).
CFE preko standardne osnove za razmatrani Bulov operator prikazan je na Sl. 6.30. Složenost ovog SFE-a je 11. Imajte na umu da vrh koji izračunava funkciju y 1 nije izlaz.
Boolean operator u ovom primjeru izračunava dvocifreni zbir (modulo 2) tri jednocifrena člana. Takođe se može smatrati jednobitnim binarnim sabiračem — funkcionalnim blokom višebitnog binarnog sabirača — za dva pojma. Tada se funkcija y 1 tumači kao "prenosni signal" u najznačajnijem bitu. Na sl. 6.31 prikazuje "vezu" tri SFE-a (kao što je prikazano na slici 6.30), uz pomoć kojih se izračunava zbir dva trocifrena binarna broja. Konstanta 0 se dovodi na treći ulaz sabirača za najmanji bitni bit, a "prenosni signal" najznačajnijeg bita je najznačajniji bit sume, koji će u opštem slučaju biti četvorocifreni broj .
Napomena 6.11. Ako dizajniramo SFE na standardnoj osnovi i želimo da minimiziramo njegovu složenost, tada moramo prije svega konstruirati odgovarajući minimalni DNF. U ovom slučaju možemo uzeti u obzir još jedan kriterij po kojem se sam DNF minimizira – broj negacija. Među svim minimalnim (u smislu definicije 6.6) DNF-ovima treba odabrati one u kojima je najmanji broj pojavljivanja varijabli pod negativnim predznakom. Sa stanovišta složenosti SFE-a, koji će se graditi na bazi minimalnog DNF-a, to znači da se minimizira broj "invertera" - SFE vrhova označenih funkcijom negacije.
Na primjer, za funkciju definiranu Karnotovom mapom (slika 6.32), jezgru, koja se sastoji od jednostavnih implikanata x 1 x 2 x 4 i x 1 x 3 x 4, trebate dodati jednostavan implikant x 2 x 3 x 4, a ne x 1 x 2 x 3 jer ne sadrži negative.
31. Dijagrami funkcionalnih elemenata, pravila konstrukcije i funkcionisanja, metoda sinteze SFE, zasnovana na SDNF i SKNF.
DefinicijaDefinicija. Funkcionalni element je matematički model elementarnog diskretnog pretvarača, koji, prema određenom zakonu, pretvara signale koji mu dolaze na ulazu u signal na izlazu pretvarača. Od funkcionalnih elemenata, uz pomoć nekih pravila, moguće je graditi modele složenije strukture i funkcionisanja - dijagrame od funkcionalnih elemenata. U ovim modelima, ulazni i izlazni signali su kodirani znakovima 0 i 1.
Pravila izgradnje. Za dobivanje složenih SFE-ova od jednostavnijih, sekvencijalno se primjenjuju operacije razdvajanja ulaza ili izlaza kola, povezivanja funkcionalnog elementa u kolo i povezivanja funkcionalnog elementa na ulaz ili izlaz kola. Ove operacije liče na pravila za dobivanje složene formule od jednostavnijih korištenjem superpozicije.
Sinteza SFE. Pošto disjunkcija, konjunkcija i negacija čine kompletan sistem u klasi R 2, zatim bilo koju Booleovu funkciju od n argumenti se mogu implementirati pomoću kola funkcionalnih elemenata - disjunktori, konjuktori i invertori - sa n ulaza i jednog izlaza. Da biste to učinili, možete, na primjer, izraziti ovu Booleovu funkciju kroz SDNF ili SKNF, a zatim "sintetizirati" rezultirajuću formulu u obliku kola funkcionalnih elemenata, uzastopno primjenjujući gore navedene operacije cijepanja, spajanja i povezivanja.
32. Metoda sinteze SFE, zasnovana na kompaktnoj implementaciji svih konjunkcija pomoću univerzalnog multipola, složenost rezultirajućih kola.
Definicija... Funkcija argumenta naziva se Boolean funkcija (ili Boolean funkcija) ako svakom skupu dodjeljuje broj.
Za definiranje Booleovih funkcija koristit ćemo tabele, vektore, formule i grafikone. Uzmimo sljedeću notaciju: je skup svih skupova, gdje.
Definicija. Funkcionalni element je matematički model elementarnog diskretnog pretvarača, koji, prema određenom zakonu, pretvara signale koji mu dolaze na ulazu u signal na izlazu pretvarača. Od funkcionalnih elemenata, uz pomoć nekih pravila, moguće je graditi modele složenije strukture i funkcionisanja - dijagrame od funkcionalnih elemenata. U ovim modelima, ulazni i izlazni signali su kodirani znakovima 0 i 1.
Metoda za sintezu SFE, zasnovana na kompaktnoj implementaciji svih konjunkcija pomoću univerzalnog multipola. Ova metoda se također temelji na predstavljanju funkcije u obliku SDNF-a, ali omogućava izgradnju manje složenih kola zbog kompaktnije implementacije konjunkcija. Dekompozicija funkcije u SDNF-u može sadržavati konjunkcije koje imaju zajedničke faktore. Ako se dvije takve konjunkcije implementiraju s jednim potkolom u bloku, onda će to zahtijevati najmanje jedan konjunktor manje nego što je bilo potrebno prije, uz nezavisnu implementaciju svih konjunkcija prvom metodom sinteze. Kompaktna implementacija svih mogućih konjukcija dužina n može se postići korištenjem induktivno izgrađenog univerzalnog multipola, koji ima n ulazi i 2 n izlazi gdje n = 1,2,3, ... Prednosti metode su posebno uočljive kada jedno kolo treba da implementira sistem od nekoliko Bulovih funkcija. U ovom slučaju bilo bi moguće podijeliti i zatim proći kroz disjunktore one izlaze univerzalnog multipola koji odgovaraju konjunkcijama uključenim u SDNF funkcija datog sistema. Ovo bi omogućilo da se prođe sa manje konjuktora nego da je svaka funkcija datog sistema nezavisno implementirana od strane sopstvenog podkola.
Složenost takvog multipola je L() =.
Ako kolo kapija Σ sadrži tačno r funkcionalnih elemenata, onda kažu da ima složenost r i zapišite to u obliku jednakosti L(Σ) = r.
| " |
Predavanje 2. Dijagrami funkcionalnih elemenata
(SFE) na određenoj osnovi. Kompleksnost i dubina
shema. Primjeri. Metoda za sintezu SFE iz DNP.
Predavač - vanredni profesor Svetlana Nikolaevna Selezneva
Predavanja na temu “Diskretna matematika 2”.
1. godina, grupa 141,
Fakultet CMC, Moskovski državni univerzitet po imenu M.V. Lomonosov
Predavanja na sajtu http://mk.cs.msu.su
SFE primjeri Sinteza SFE iz DNP-a
Dijagrami funkcionalnih elemenata
Definirajmo kola funkcionalnih elemenata u određenoj bazi.
Neka nam je dat neki skup Bulovih funkcija B = (g1 (x1, ..., xn1), ..., gs (x1, ..., xns)) P2, gdje je n1, ..., ns 0.
Nazovimo ovaj skup osnovom.
Imajte na umu da ovaj koncept baze nema nikakve veze sa konceptom baze P2, koji je razmatran u algebri logike.
Po pravilu ćemo uzeti u obzir standardnu bazu B0 = (x & y, x y, x).
SFE primjeri Sinteza SFE prema DNF-u Određivanje kola od funkcionalnih elemenata Kolo od funkcionalnih elemenata (SFE) u bazi B0 = (x & y, x y, x) je
1) usmereni aciklični graf G = (V, E), čiji svaki vrh v V ima polovinu stupnja ulaza d (v) koji ne prelazi dva (d (v) 2);
2) svaki vrh v sa polustepenom ulaska jednakim 0 (d (v) = 0) naziva se ulaz (ili ulaz kola) i neka Booleova varijabla xi mu je dodijeljena;
3) svi ostali čvorovi (osim ulaza) nazivaju se unutrašnjim čvorovima kola;
4) svakom vrhu v sa polustepenom pristupa jednakim 1 (d (v) = 1) dodeljuje se (funkcionalni) element negacije; svi takvi vrhovi se nazivaju invertori;
5) svakom tjemenu v sa polustepenom ulaska jednakim 2 (d (v) = 2) dodjeljuje se ili (funkcionalni) konjunkcijski element &, ili (funkcionalni) element disjunkcije; svi vrhovi kojima su dodijeljeni elementi konjunkcije nazivaju se konjunktori, svi vrhovi kojima su dodijeljeni elementi disjunkcije nazivaju se disjunktori;
SFE primjeri Sinteza SFE prema DNF-u Određivanje kola od funkcionalnih elemenata (nastavak)
6) pored toga, u paru su različite izlazne varijable y1, ..., ym dodijeljene nekim od vrhova.
Ako je zadan SPE S, čijim ulazima su dodijeljene samo varijable x1, ..., xn, a sa izlaznim varijablama y1, ..., ym, tada ćemo ovaj SPE označiti sa S (x1, .. ., xn; y1, .. ., ym).
SFE primjeri Sinteza SFE iz DNP-a
- & nbsp– & nbsp–
Određivanje dubine vrha SPE Indukcijom određujemo dubinu d (v) vrha v u SPE S.
1. Osnova indukcije. Svaki ulaz v SFE S ima dubinu jednaku 0: d (v) = 0.
- & nbsp– & nbsp–
SFE i njihove karakteristike Šeme funkcionalnih elemenata su računski model.
Karakteristike CFE-a koje smo uveli pokazuju različite aspekte računske efikasnosti.
Složenost CFE odgovara vremenu sekvencijalnog izračunavanja.
Dubina CFE odgovara vremenu paralelnog izračunavanja.
Maksimalan broj vrhova sa istom dubinom u SFE odgovara broju procesora u paralelnom izračunavanju.
SFE primjeri Sinteza SFE iz DNF Primjer: zbir tri bita Rješenje. Slično kao u primjeru 6, pišemo tablicu zbira tri bita x, y i z. Ovaj zbir može biti i broj sa dvije binarne cifre, tako da uvodimo dvije logičke varijable
u0, u1 tako da je x + y + z = 2u1 + u0:
- & nbsp– & nbsp–
Literatura za predavanje 4
1. Yablonsky S.V. Uvod u diskretnu matematiku. M .:
Viša škola, 2001. Dio V, Ch. 2, str. 336-355.
2. Gavrilov G.P., Sapozhenko A.A. Zadaci i vježbe iz diskretne matematike. Moskva: Fizmatlit, 2004. Ch. X 1.1, 1.5, 1.7, 1.17, 1.18.
SFE primjeri Sinteza SFE iz DNP-a
Sljedeći "inženjersko-konstruktivni" smisao može se dati predstavljanju Bulovih funkcija formulama. Formulu nad nekim proizvoljno fiksiranim skupom ćemo smatrati "crnom kutijom", svojevrsnim uređajem, na čiji se ulaz unose sve vrste skupova varijabilnih vrijednosti, a izlaz koji odgovara tim skupovima vrijednosti funkcije predstavljene formulom (slika 6.22).
Da bismo razumjeli kako funkcionira "crna kutija", moramo rastaviti proces konstruiranja formule iz podformula. Dolazak do "osnovnih" podformula, tj. elemenata skupa, dolazimo do "građevinskih blokova", strukturnih elemenata od kojih se sklapa "crna kutija" koja izračunava funkciju. Svaku funkciju "baze" izračunava odgovarajući "čvor", koji se smatra najmanjom strukturnom jedinicom naše "crne kutije", a njena unutrašnja struktura se više ne analizira.
Primjer 6.22. Odaberimo standardnu osnovu kao skup. Tada se formula nad standardnom bazom koja predstavlja funkciju (ekvivalentnost) konstruira na sljedeći način:
Proračun prema ovoj formuli (i proces njegove konstrukcije od elemenata standardne osnove) može se shematski prikazati kao što je prikazano na sl. 6.23.
Varijabla (tačnije, vrijednost ove varijable) se dovodi na ulaz strukturalnog elementa koji se zove inverter (slika 6.24, a) i izračunava negaciju. Negativ uklonjen sa izlaza pretvarača, tj. funkcija se dovodi na jedan od ulaza konjunkora (slika 6.24.5), na čiji se drugi ulaz dovodi varijabla. Na izlazu spojnika pojavljuje se funkcija. Izračunavanje funkcije može se pratiti na sličan način. Obje ove funkcije se unose na ulaze disjunktora (slika 6.24, c), sa čijeg se izlaza funkcija uklanja (ovo nije ništa drugo do zbir po modulu 2:). Konačno, ova funkcija se dovodi na ulaz pretvarača, čiji je izlaz već funkcija (ekvivalentnost).
Tako dolazimo do ideje "kola" - matematičkog modela kalkulatora Booleove funkcije, predstavljenog određenom formulom, sastavljenom od strukturnih elemenata, od kojih svaki izračunava jednu od "osnovnih" Booleovih funkcija. U opštem slučaju, "kolo" izračunava Boolean operator, a svaka koordinatna funkcija ovog operatora se uklanja iz jednog od izlaza kola.
Matematički, "šema" je definirana kao usmjereni graf posebne vrste, u kojem su označeni i vrhovi i lukovi.
Hajde da uvedemo notaciju: ako je neki skup Bulovih funkcija, onda sa označava podskup koji se sastoji od svih funkcija varijabli.
Definicija 6.14. Neka su skupovi fiksni: (Booleove funkcije) i (Booleove varijable).
Kolo funkcionalnih elemenata preko baze (SFE), ili jednostavno kolo preko baze, također (F, X) -shema, naziva se otvoreni usmjereni graf (tj. mreža), čiji je svaki vrh označen sa jednim od elemenata seta tako da su ispunjeni sljedeći zahtjevi:
1) svaki ulaz mreže je označen ili nekom promenljivom iz, ili nekom konstantom iz;
2) ako je vrh v mreže označen funkcijom varijabli (tj.), tada je njegov polustepen ulaska jednak, a na skupu lukova koji ulaze u vrh, numeracija (jedan prema jedan) je dato, u kojem svaki luk dobiva broj od 1 do.
Prilikom crtanja dijagrama ulazi se označavaju kružićima, a vrhovi koji nisu ulazni se označavaju trouglovima, unutar kojih je upisana oznaka funkcije koja označava ovaj vrh. Izlazi su označeni strelicama "izlaz". Na sl. 6.25 prikazuje SPE preko osnove.
Ako se osnova podrazumijeva, onda ćemo reći jednostavno "šema". Osim toga, ako je skup varijabli fiksiran "jednom za svagda" i kada se razmatraju različite sheme mijenjamo samo skup funkcija, tada ćemo, kao što smo to učinili, uvodeći koncepte formule i superpozicije nad datom bazom, govoriti o SFE-u na bazi, uz pretpostavku svaki put, što implicira jednom fiksni skup varijabli, koji se (ako to ne šteti tačnosti) ne spominje.
Definirajmo sada indukcijom pojam Booleove funkcije izračunate vrhom kola.
Definicija 6.15. Neka je CFE dat preko baze čiji je skup vrhova.
1. Pretpostavlja se da svaki ulaz CFE izračunava Booleovu funkciju kojom je označen (tj. neku varijablu ili konstantu).
2. Ako je vrh označen funkcijom, luk sa brojem koji ulazi u njega dolazi iz vrha koji procjenjuje funkciju, tada vrh v izračunava superpoziciju.
Dakle, ako svaki vrh CFE over izračunava određenu funkciju, tada je redosljed kojim se nabrajaju funkcije zamjenjene umjesto varijabli funkcije bitan u opštem slučaju. Prirodno je nazvati Booleovu funkciju varijabli komutativnom ako čuva svoju vrijednost pod proizvoljnom permutacijom svojih varijabli. U ovom slučaju ne moramo brinuti o numeraciji lukova koji ulaze u vrh kruga, označenih takvom funkcijom.
Primjer 6.23. Razmotrite SPE na sl. 6.25. Vrhovi i su ulazi SFE. Ovi vrhovi izračunavaju funkcije i, respektivno. Tada vrh, kao i vrh, prema definiciji 6.15, izračunava funkciju (Schaefferov potez), a vrh (izlaz mreže) izračunava funkciju za koju se zna da je jednaka konjunkciji.
SPE prikazan na sl. 6.26, ima dva izlaza koji izračunavaju funkcije i.
Definicija 6.16. Booleova funkcija koju CFE izračunava na bazi je funkcija izračunata bilo kojim od njenih izlaza.
Dakle, CFE izračunava tačno onoliko Bulovih funkcija koliko ima izlaza. SFE na sl. 6.25 izračunava jednu funkciju, a SPE na sl. 6.26 - dva.
U opštem slučaju, ako je skup svih varijabli koje služe kao oznake za ulaze kola preko baze koja ima g izlaza, CFE definira preslikavanje iz Bulove kocke u Booleovu kocku, tj. boolean operator.
Napomena 6.10. U nekim slučajevima, funkcija izračunata datim SFE je nešto drugačije definirana, pod pretpostavkom da je to funkcija izračunata bilo kojim vrhom iz podskupa odabranih SFE vrhova. Konkretno, to mogu biti izlazi. U svakom slučaju, dogovorimo se da iz odabranih (u upravo naznačenom smislu) vrhova kola nacrtamo "izlaznu" strelicu.
Dakle, svaki krug kapija izračunava neki Bulov operator, posebno ako je broj izlaza kola jednak 1, onda izračunava neku Booleovu funkciju.
Može se dokazati i obrnuto: za bilo koji Bulov operator, SFE se može konstruisati preko baze, gdje je kompletan skup koji izračunava dati operator.
Primjer 6.24. Postavimo tablicu na Boolean operator koji se preslikava na (Tabela 6.9).
Iz tabele je lako vidjeti da (funkcija nije ništa drugo do funkcija većine varijabli, a minimalni DNF za nju je napisan gore, vidi primjer 6.12). Predstavljamo funkciju u bazi Žegalkina. Koristeći de Morganove zakone, dobijamo
S obzirom na to, imaćemo
(podsjetimo da je zbir po modulu 2 bilo kojeg parnog broja jednakih članova jednak 0). dakle,
SFE za Boolean operator dat u tabeli. 6.9, preko baze Žegalkina prikazana je na Sl. 6.27.
Prilikom dizajniranja SFE-a, korisno je imati na umu numerički parametar koji se zove njegova složenost.
Složenost SPE je broj njegovih vrhova koji nisu inputi.
Prikazano na sl. 6.27 CFE preko baze Žegalkina ima složenost 5.
Razmotrimo sada CFE za istog operatera preko standardne osnove. Koristeći tabelu (vidi tabelu 6.9), konstruišemo SDNF za funkciju
Karnotova karta za ovu funkciju, prikazana na Sl. 6.28 pokazuje da se ne može minimizirati (tačnije, gore napisani SDNF je minimalni DNF za ovu funkciju).
Ali možete ići drugim putem. Možemo uzeti u obzir tabelu. 6.9 kao tabela koja definira djelomičnu Booleovu funkciju. Minimiziranjem ove funkcije prema Karnot karti * prikazanoj na Sl. 6.29, dobijamo
* Na ovoj karti smo eksplicitno označili skupove na kojima funkcija poprima vrijednost 0 stavljanjem nula u odgovarajuće ćelije. Stoga želimo još jednom skrenuti pažnju na činjenicu da ne treba brkati nule sa crticama: crtica u ćeliji karte koja navodi djelomičnu funkciju znači da vrijednost funkcije nije definirana na ovom skupu, tj. nije ni 0 ni 1.
CFE preko standardne osnove za razmatrani Bulov operator prikazan je na Sl. 6.30. Složenost ovog SFE-a je 11. Imajte na umu da vrh koji izračunava funkciju nije izlaz.
Boolean operator u ovom primjeru izračunava dvocifreni zbir (modulo 2) tri jednocifrena člana. Takođe se može smatrati jednobitnim binarnim sabiračem — funkcionalnim blokom višebitnog binarnog sabirača — za dva pojma. Tada se funkcija r / 1 tumači kao "prenosni signal" u najznačajnijem bitu. Na sl. 6.31 prikazuje "vezu" tri SFE-a (kao što je prikazano na slici 6.30), uz pomoć kojih se izračunava zbir dva trocifrena binarna broja. Konstanta 0 se dovodi na treći ulaz sabirača za najmanji bitni bit, a "prenosni signal" najznačajnijeg bita je najznačajniji bit sume, koji će u opštem slučaju biti četvorocifreni broj .
Veličina: px
Počnite prikazivati sa stranice:
Transkript
1 Predavanje 2. Šeme funkcionalnih elemenata (SFE) u određenoj osnovi. Složenost i dubina sheme. Primjeri. Metoda za sintezu SFE iz DNP. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja iz diskretne matematike 2. 1. godina, grupa 141, Fakultet računarske matematike i kibernetike, Moskovski državni univerzitet po imenu M.V. Lomonosov Predavanja na sajtu
2 Dijagrami funkcionalnih elemenata Definirajmo dijagrame funkcionalnih elemenata u određenoj osnovi. Neka nam je dat neki skup Bulovih funkcija B = (g 1 (x 1, ..., x n1), ..., gs (x 1, ..., x ns)) P 2, gdje je n 1, .. ., ns 0. Ovaj skup nazivamo bazom. Imajte na umu da ovaj koncept baze nema nikakve veze sa konceptom baze P 2, koji je razmatran u algebri logike. Po pravilu ćemo uzeti u obzir standardnu bazu B 0 = (x & y, x y, x).
3 Određivanje kola funkcionalnih elemenata Kolo funkcionalnih elemenata (CFE) u bazi B 0 = (x & y, xy, x) je 1) orijentirani aciklički graf G = (V, E), svaki vrh v V od kojih ima polovinu stupnja ulaska d (v ) ne više od dva (d (v) 2); 2) svaki vrh v sa polustepenom ulaska jednakim 0 (d (v) = 0) naziva se ulaz (ili ulaz kola) i pripisuje mu se neka Bulova varijabla x i; 3) svi ostali čvorovi (osim ulaza) nazivaju se unutrašnjim čvorovima kola;
4 Definicija kola funkcionalnih elemenata (nastavak) 4) svakom vrhu v sa polustepenom ulaska jednakim 1 (d (v) = 1) dodjeljuje se (funkcionalni) element negacije; svi takvi vrhovi se nazivaju invertori; 5) svakom tjemenu v sa polustepenom ulaska jednakim 2 (d (v) = 2) dodjeljuje se ili (funkcionalni) konjunkcijski element &, ili (funkcionalni) element disjunkcije; svi vrhovi kojima su dodijeljeni elementi konjunkcije nazivaju se konjunktori, svi vrhovi kojima su dodijeljeni elementi disjunkcije nazivaju se disjunktori;
5 Definicija sklopa funkcionalnih elemenata (nastavak) 6) Osim toga, nekim od vrhova su dodijeljene parno različite izlazne varijable y 1, ..., y m. Ako je dat SPE S, čijim su ulazima dodijeljene samo varijable x 1, ..., xn, a sa izlaznim varijablama y 1, ..., ym, tada ćemo ovaj SPE označiti sa S (x 1 , ..., xn; y 1, ..., ym).
6 Primjer SFE Primjer 1. SFE S (x 1, x 2, x 3; y 1, y 2, y 3):
7 Primjer SFE Primjer 1. Po pravilu, SFE se prikazuju na sljedeći način S (x 1, x 2, x 3; y 1, y 2, y 3):
8 Određivanje složenosti SFE Složenost L (S) SFE S je broj unutrašnjih vrhova ovog SFE, tj. broj funkcionalnih elemenata u SFE S.
9 Složenost SFE Primjer 2. Složenost SFE S:
10 Određivanje dubine vrha CFE Indukcijom određujemo dubinu d (v) vrha v u CFE S. 1. Osnova indukcije. Svaki ulaz v SFE S ima dubinu jednaku 0: d (v) = Induktivni prijelaz. 1) Ako luk iz vrha v 1 vodi do pretvarača v CFE S, tada je d (v) = d (v 1)) Ako lukovi iz vrhova v 1 i v 2 vode do konjuktora ili disjunktora v CFE S, onda je d (v) = max (d (v 1), d (v 2)) + 1. Dubina D (S) SFE S naziva se maksimumom dubina njegovih vrhova.
11 Dubina SFE Primjer 3. Dubina vrhova SFE S i dubina SFE S:
12 Definicija funkcioniranja SFE Na svakom vrhu SFE-a se realizuje (ili izračunava) određena Booleova funkcija. Indukcijom definiramo Booleovu funkciju koja se realizuje na vrhu v CFE S. 1) Ako je v ulazni vrh, a varijabla xi mu je dodijeljena, tada se funkcija fv = xi realizuje na vrhu v . 2) Ako luk iz vrha v 1 vodi do pretvarača v, a funkcija f v1 se realizuje na vrhu v 1, tada je funkcija f v = f v1 realizovana na vrhu v. 3) Ako lukovi iz vrhova v 1 i v 2 vode do konjunktora (ili disjunktora) v, a funkcije f v1 i f v2 se realizuju na vrhovima v 1 i v 2, tada na vrhu v funkcija fv = f v1 i f v2 (fv = f v1 f v2).
13 Funkcioniranje CFE Vjeruje se da CFE S (x 1, ..., xn; y 1, ..., ym) implementira sistem Booleovih funkcija FS = (f 1, ..., fm), koji se realizuju na njegovim izlaznim vrhovima y 1, ..., y m.
14 Funkcioniranje SFE Primjer 4. Booleove funkcije realizovane na vrhovima SFE S: F S = (x 3, x 1 x 2, x 1 x 2 x 3).
15 Linearni program Linearni program sa ulazima x 1, ..., xn preko baze B 0 = (x & y, xy, x) je niz z 1, z 2, ..., zt, u kojem za svaki broj j, j = 1, ..., t, važi da 1) ili zj = xi; 2) ili z j = z k za 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 SFE i linearni programi Jasno je da se proračun u SFE može prepisati kao linearni program. Obrnuto, svaki linearni program može biti predstavljen u obliku nekog SFE.
17 CFE i linearni programi Primjer 5. CFE S odgovara linearnom programu z 1 = x 1 & x 2, z 2 = x 3, z 3 = z 1 z 2.
18 SFE i njihove karakteristike Šeme funkcionalnih elemenata su računski model. Karakteristike CFE-a koje smo uveli pokazuju različite aspekte računske efikasnosti. Složenost CFE odgovara vremenu sekvencijalnog izračunavanja. Dubina CFE odgovara vremenu paralelnog izračunavanja. Maksimalan broj vrhova sa istom dubinom u SFE odgovara broju procesora u paralelnom izračunavanju.
19 Primjer: zbir dva bita Primjer 6. Konstruirajte SPE na standardnoj bazi koja implementira (izračunava) zbir dva bita x i y. Rješenje. Napišimo tabelu zbira dva bita x i y. Ovaj zbir može biti broj sa dvije binarne cifre, pa uvodimo dvije Bulove varijable z 0, z 1, tako da je x + y = 2z 1 + z 0: x y z 1 z
20 Primjer: zbir dva bita Rješenje (nastavak). Tada je z 0 = x y, z 1 = xy. Uzimajući u obzir da je x y = (x y) (x y), dobijamo SPE: Jasno je da je L (S 1) = 3, a D (S 1) = 3.
21 SFE u proizvoljnoj osnovi Koncept SFE u proizvoljnoj bazi B P 2 uvodi se na sličan način.
22 Primjer: zbir tri bita Primjer 7. Konstruirajte CFE u bazi P2 2 (tj. od svih Bulovih funkcija u zavisnosti od dvije varijable), realizirajući (izračunavajući) zbir tri bita x, y i z.
23 Primjer: zbir tri bita Rješenje. Slično kao u primjeru 6, pišemo tablicu zbira tri bita x, y i z. Ovaj zbir može biti i broj sa dvije binarne cifre, pa uvodimo dvije Bulove varijable u 0, u 1, tako da je x + y + z = 2u 1 + u 0: x y z u 1 u
24 Primjer: zbir tri bita Rješenje (nastavak). Tada je u 0 = x y z, u 1 = xy xz yz. Uzimajući u obzir da je xy xz yz = xy z (x y), dobijamo CFE: Vidimo da je L (S) = 5, a D (S) = 3.
25 Implementacija Bulove funkcije CFE Da li je moguće implementirati proizvoljnu Booleovu funkciju (ili sistem Bulovih funkcija) u bazi B 0 = (x & y, x y, x)? Može. Kako se to može opravdati? Na primjer, ovako. Jer (x & y, x y, x) je kompletan sistem u P 2, proizvoljna Bulova funkcija f može biti predstavljena formulom samo kroz konjunkciju, disjunkciju i negaciju. Na primjer, u obliku savršenog DNF-a, ako je f 0, i u obliku x & x, ako je f = 0. I onda, koristeći ovu DNF (formulu), konstruirajte odgovarajući SFE. Ova metoda konstruisanja CFE-a za Bulove funkcije naziva se metoda DNF sinteze.
26 Sinteza SFE-ova iz DNF-a I koja je složenost dobivena iz SFE-a S iz DNF-a za Booleovu funkciju f (x 1, ..., x n), ovisno o n varijabli? Savršen DNF za funkciju f će sadržavati najviše 2 n elementarne konjunkcije. Svaka elementarna konjunkcija je konjunkcija n varijabli ili njihovih negacija.
27 Sinteza SFE prema DNF-u Dakle, kolo će sadržavati: n pretvarača za implementaciju svih negacija varijabli x 1, ..., x n; pomoću (n 1) konjuktora za implementaciju svake od najviše 2 n elementarnih konjunkcija u savršenom DNF; najviše (2 n 1) disjunktori za implementaciju disjunkcije elementarnih konjunkcija DNF-a. Dobijamo da je L (S) n + (n 1) 2 n + (2 n 1) n 2 n + n.
28 Složenost Bulove funkcije Složenost L (f) Bulove funkcije f (x 1, ..., x n) u klasi CFE je minimalna složenost među svim CFE-ovima koji implementiraju funkciju f. Dakle, dokazali smo teorem: Teorem 1. Za proizvoljnu funkciju f (x 1, ..., x n) P 2, L (f) n 2 n + n je tačno.
29 Zadaci za nezavisno rješenje 1. Za Bulovu funkciju f (x 1, x 2, x 3) = (), konstruirajte SPE u standardnoj bazi složenosti. Za Booleovu funkciju f (x 1, x 2, x 3 ) = (), konstruirajte SPE u standardnoj bazi složenosti Za Booleovu funkciju f (x 1, x 2, x 3, x 4) = x 1 x 2 x 3 x 4, konstruirajte CFE u standardnoj bazi dubine Dokazati da je u standardnoj bazi L (xy) = 4.
30 Literatura za predavanje 4 1. Yablonskiy S.V. Uvod u diskretnu matematiku. M.: Viša škola, dio V, gl. 2, sa Gavrilov G.P., Sapozhenko A.A. Zadaci i vježbe iz diskretne matematike. Moskva: Fizmatlit, Ch. X 1.1, 1.5, 1.7, 1.17, 1.18.
31 Kraj predavanja 4
Predavanje: Šeme funkcionalnih elemenata sa kašnjenjem (SPEZ), automatizam preslikavanja koje oni vrše. Zastupstvo KAV SFEZ. Pojednostavljenja KAV-a. Različitost i nerazlučivost CAV stanja. Moorova teorema
Predavanje: Anselova teorema o podjeli n-dimenzionalne kocke na lance. Teorema o broju monotonih funkcija u algebri logike. Teorema o dekodiranju monotonih funkcija algebre logike. Predavač - vanredni profesor Svetlana Selezneva
Predavanje: Konačne mašine sa izlazom (KAV). Automatske funkcije, metode njihovog dodjeljivanja. Teorema o transformaciji periodičnih nizova automatskim funkcijama. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva
Predavanje: Djelomično uređeni skupovi (PNS). CHUM dijagram. Maksimalni, minimalni, najveći i najmanji artikli. Lanci i antilanci, dužina i širina konačnog PLS-a. Teorema o dekompoziciji PN na antilančeve.
Predavanje 2. Osobine binomnih koeficijenata. Izračunavanje suma i metoda generisanja funkcija (konačni slučaj). Polinomski koeficijenti. Procjene za binomne i polinomske koeficijente. Zbroj procjena
Predavanje: Algoritam za prepoznavanje kompletnosti u P k. Zatvorena nastava. Klase funkcija koje čuvaju skupove i čuvaju particije, njihovu zatvorenost. Kuznjecovljev teorem o funkcionalnoj potpunosti. Predzavršena nastava.
Predavanje 2. Kombinatorika. Svojstva binomnih koeficijenata. Izračunavanje suma i metoda generiranja funkcija. Polinomski koeficijenti. Procjene za binomne i polinomske koeficijente. Asymptotic
Predavanje: Konačne funkcije. Elementarne k-vrijedne funkcije. Metode za specifikaciju k-vrijednih funkcija: tabele, formule, 1. i 2. oblici, polinomi. Kompletnost. Teorema o potpunosti Post sistema. Webb funkcija.
Predavanje 3. Sekvence definirane rekurentnim relacijama. Homogene i nehomogene linearne rekurentne jednadžbe (LORU i LNRU). Opšta rješenja LORU i LNRU. Predavač - vanredni profesor Svetlana Selezneva
Predavanje 15. Funkcije logike konačnih vrijednosti. Elementarne funkcije k-vrijedne logike. Metode za specifikaciju k-vrijednih logičkih funkcija: tabele, formule, I i II oblici, polinomi. Kompletnost. Predavač - vanredni profesor Selezneva
Predavanje: Funkcije logike konačnih vrijednosti. Elementarne funkcije k-vrijedne logike. Metode za specifikaciju k-vrijednih logičkih funkcija: tabele, formule, I i II oblici, polinomi. Kompletnost. Predavač - vanredni profesor Svetlana Selezneva
Predavanje: Möbiusova funkcija na PLM-u. Möbiusova funkcija na n-dimenzionalnoj kocki. Mobiusova formula za inverziju. Princip uključivanja-isključivanja. Problem izračunavanja broja permutacija-poremećaja. Predavač - vanredni profesor Svetlana Selezneva
Predavanje 2. Osobine binomnih koeficijenata. Metoda generisanja funkcija, izračunavanje suma i dokaz identiteta. Polinomski koeficijenti. Princip uključivanja-isključivanja. Predavač - vanredni profesor Svetlana Selezneva
Predavanje: Osnovne funkcije. Tri leme o bitnim funkcijama. Jablonskijev kriterijum potpunosti. Slupeckijev kriterij potpunosti. Schefferove funkcije. Predavač vanredni profesor Svetlana Nikolaevna Selezneva [email protected]
Predavanje: Osnovni kombinatorni brojevi. Procjene i asimptotika kombinatornih brojeva. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva, Fakultet računarske matematike i kibernetike, Moskovski državni univerzitet po imenu M.V. Lomonosov Predavanja na web stranici http://mk.cs.msu.su
Predavanje: Osobine binomnih koeficijenata. Izračunavanje suma i metoda generisanja funkcija (konačni slučaj). Polinomski koeficijenti. Procjene za binomne i polinomske koeficijente. Procjene za sume binoma
Predavanje: Konačne mašine sa izlazom. Transformacija periodičnih nizova pomoću konačnih mašina sa izlazom. Različitost stanja u mašinama konačnih stanja sa izlazom. Pojednostavljivanje mašina. Predavač Selezneva
Predavanje: Pokrivanje skupova i pokrivanje matrice. Gradijentni premaz. Gradient Cover Lema. Procjene kardinalnosti skupa sjenčanja n-dimenzionalne kocke. Procjene dužine polinomskih normalnih oblika funkcija
Predavanje 5. Pokrivanje skupa i pokrivanje matrice. Gradijentni premaz. Gradient Cover Lema. Procjene kardinalnosti skupa sjenčanja Booleove kocke. Granice dužine za normalne forme Boolean polinoma
Predavanje 3. Sekvence definirane rekurentnim relacijama. Homogene i nehomogene linearne rekurentne jednadžbe (LORU i LNRU). Opšta rješenja LORU i LNRU. Primjeri Predavač - vanredni profesor Selezneva
Predavanje 3. Relacije na skupovima. Svojstva. Formula za uključivanje-isključivanje. Relacija ekvivalencije. Parcijalni odnos poretka. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja o diskretnim modelima.
Predavanje 4. Osobine viševrijednih logika. Zatvorena klasa, zatvorena klasa. Teoreme Yanova i Muchnika o postojanju zatvorenih klasa bez osnove i zatvorenih klasa sa prebrojivim u viševrijednim logikama
Predavanje. Funkcije prirodnog argumenta (sekvence). Homogene i nehomogene linearne rekurentne jednadžbe (LORU i LNRU). Opšta rješenja LORU i LNRU. Primeri Predavač - vanredni profesor Svetlana Selezneva
Predavanje: Hromatski broj grafa. Kriterijum za dvobojni graf. Teoreme o gornjim i donjim granicama za kromatski broj grafa. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja o diskretnim modelima.
Predavanje: Grafovi i mreže. Procjena broja pseudografa sa q ivicama. Procjena za broj stabala sa q rubovima. Planarni grafovi. Ojlerova formula za planarne grafove. Najveći broj ivica u planarnim grafovima. Neplanarnost
Predavanje 1. Kombinatorika. Položaji, permutacije, plasmani s ponavljanjima, kombinacije, kombinacije s ponavljanjima. Njihov broj. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Katedra za matematičku kibernetiku
Predavanje: Sekvence. Homogene i nehomogene linearne rekurentne jednadžbe. Opća rješenja linearnih rekurentnih homogenih i nehomogenih jednačina. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva
Predavanje 8. Bojanje. Ekvivalencija boja u odnosu na grupu. Produktivne funkcije. Niz nabrajanja za oblike i niz nabrajanja za funkcije. Polyin teorem. Predavač Selezneva Svetlana Nikolaevna
Predavanje: Bojanje. Ekvivalencija boja u odnosu na grupu permutacija. Polyin teorem (poseban slučaj). Produktivne funkcije. Niz nabrajanja za oblike i niz nabrajanja za funkcije. Teorema
Predavanje 2. Konjunktivni normalni oblici. Implikentna, jednostavna implikacija funkcije. Skraćena CNF funkcija algebre logike. Metode za izradu skraćenog CNF-a. Predavač Selezneva Svetlana Nikolaevna [email protected]
Matematički modeli i metode logičke sinteze VLSI jesen 2015. Predavanje 4 Plan predavanja Logička optimizacija kombinacionih logičkih kola Različiti načini predstavljanja funkcija logičke algebre (FAL)
Predavanje: Nedeterministički konačni automati (NFA) bez izlaza. Teorema o podudarnosti klasa skupova riječi koje priznaju konačni deterministički i konačni nedeterministički automati. Procedura
Predavanje 1. Uzorci. Položaji, permutacije, plasmani sa ponavljanjima, kombinacije, kombinacije sa ponavljanjima, njihov broj. Primjeri. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja na predmetu Diskretno
Predavanje 1. Kombinatorski objekti: odabiri, rasporedi, permutacije, rasporedi s ponavljanjima, kombinacije, kombinacije s ponavljanjima, njihov broj. Kombinatorni brojevi: faktorijalni, opadajući faktorijal, binom
PREDAVANJE 4 ŠEME IZ FUNKCIONALNIH ELEMENTA 1. Osnovne definicije Prije svega, potrebno je razmotriti sastav. Funkcija se može zamisliti kao "crna kutija" koja ima ulaz i izlaz. Neka
Predavanje 2. Algoritam za prepoznavanje kompletnosti u P k. Kuznjecovljev teorem. Zatvorena nastava. Klase funkcija koje čuvaju skup. Klase funkcija očuvanja split-a. Predzavršena nastava. Predavač Doktor fizičko-matematičkih nauka Selezneva
Predavanje 3. Žegalkinov polinom. Metode za konstruisanje polinoma Žegalkina za funkciju. Linearna implikacija funkcije. Linearni konjunktivni normalni oblik (LCNF). Pronalaženje svih linearnih implikacija funkcije. Ispitivanje
Predavanje 2. Generirajuće funkcije: izračunavanje kombinatornih suma i dokazivanje identiteta, nabrajanje kombinatornih objekata. Princip uključivanja-isključivanja. Brojanje broja permutacija-poremećaja. Predavač -
Predavanje 5. Grafovi. Bojanje grafikona. Hromatski broj grafa. Kriterijum za dvobojni graf. Gornje granice za hromatski broj grafa. Predavač Doktor fizičko-matematičkih nauka Selezneva Svetlana Nikolaevna [email protected] Predavanja
Predavanje: Konačni automati (KA) bez izlaza (prepoznavači konačnih automata). Dijagrami prijelaza. Setovi automata (jezici). Lema o svojstvima automatskih skupova. Primjer neautomatskog seta. Predavač
Predavanje 1. Konačne funkcije. Elementarne k-vrijedne funkcije. Metode za specifikaciju k-vrijednih funkcija: tabele, formule, 1. i 2. oblici, polinomi. Kompletnost. Teorema o potpunosti Post sistema. Webb funkcija.
Predavanje 7. Problem izbora ruta i njegov poseban slučaj je problem raspodjele letova po danu. Grafički model za problem distribucije leta. Hromatski broj grafa. Kriterijum za dvobojnost grafa.
Kurs "Osnove kibernetike" za studente specijalizacije 01.02.01. (matematika i softver za računare) 1. Opšte informacije (nastavno opterećenje, oblici upravljanja i dr.). Kurs je
Predavanje 6. Grafovi. Naslijeđena svojstva grafova. Procjena broja rubova u grafovima s nasljednim svojstvom. Ekstremni grafovi. Najveći broj ivica u ravnim grafovima i grafovima bez trougla sa datim
Math-Net.Ru sve-ruski matematički portal D. S. Romanov, Metoda za sintezu lako testiranih kola koja dozvoljavaju jednokratne provjere konstantne dužine, Diskr. Mat., 2014, Svezak 26, Broj 2,
Predavanje: Konačne mašine bez izlaza, determinističke i nedeterminističke. Teorema o podudarnosti klasa skupova riječi koje priznaju konačni deterministički i nedeterministički automati. Procedura
Praktični rad 2 Konstrukcija normalnih oblika logičke funkcije Svrha rada: Naučiti graditi konjunktivne, disjunktivne, perfektne normalne oblike logičke funkcije Sadržaj rada: Osnovni
Seminar o složenosti Bulovih funkcija Predavanje 1: Uvod A. Kulikov Klub računarskih nauka u POMI http://compsciclub.ru 25.09.2011. 25.09.2011. 1/26 Plan predavanja 1 Bulove funkcije 2 Bulova kola 3 Gotovo
Praktični rad 1 Analiza i sinteza logičkih i relejnih upravljačkih sistema UVOD Uređaji diskretnog djelovanja, izrađeni na elementima hidro-, pneumo- i elektroautomatike i upravljačkih mikroprocesora
Predavanje: Regularni izrazi i regularni skupovi. Kleeneova teorema o podudarnosti klasa automatskih skupova i regularnih skupova. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja o diskretnoj matematici
Predavanje 3 Bulove algebre i Bulove funkcije Bulove algebre Pojam algebarskih sistema Algebarski sistem ili algebarska struktura skup simbola određene abecede (podrška) sa datim
Predavanje 5. Grafovi. Primjeri primjene grafova. Problem sa transportom. Mrežni tok, Fordova i Fulkersonova teorema o maksimalnom protoku mreže. Algoritam za konstruisanje maksimalnog protoka u mreži. Predavač
Predavanje: Grafovi. Primjeri primjene grafova. Problem sa transportom. Mrežni tok, Fordova i Fulkersonova teorema o maksimalnom protoku mreže. Algoritam za konstruisanje maksimalnog protoka u mreži. Predavač -
Lekcija 8 Podsjetimo da za proizvoljne skupove A i B postoje skupovi A B = (x x A i x B); (presecanje A i B) A B = (x x A ili x B); (unija A i B) A \ B = (x x A i x / B) (razlika A i B).
Predavanje 7. Ramsey brojevi. Gornja granica za Ramsey broj. Donja granica za Ramsey broj. Predavač Selezneva Svetlana Nikolaevna [email protected] Fakultet CMC, Moskovski državni univerzitet po imenu M.V. Lomonosov Predavanja na web stranici http://mk.cs.msu.ru
Predavanje: Grafovi. Osnovni koncepti. Povezani grafovi. Drveće. Spanning tree. Broj visećih vrhova u razapinjućem stablu. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja o diskretnim modelima. majstore,
Predavanje 11. Bulove šeme. Diskretna matematika, HSE, Fakultet računarskih nauka (jesen 2014. proljeće 2015.) Pod Booleovim krugom u varijablama x 1, ..., x n podrazumijevamo niz Bulovih funkcija g
ODOBRENO Prorektor za nastavu Yu. A. Samarskiy 10.06.2008. PROGRAM I ZADACI za predmet DISKREtne strukture na smeru 010600 Fakultet FIET Katedra za analizu podataka Kurs II semestar 4 Dva
Moskovski državni univerzitet Lomonosov Fakultet računarske matematike i kibernetike S. A. Lozhkin ELEMENTI TEORIJE SINTEZE SISTEMA DISKRETNOG UPRAVLJANJA Moskva 2016 Sadržaj
Predavanje: Naslijeđena svojstva grafova. Ekstremni grafovi. Ramsey brojevi. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva, Fakultet računarske matematike i kibernetike, Moskovski državni univerzitet po imenu M.V. Lomonosov Predavanja na web stranici http://mk.cs.msu.su Hereditary
Predavanje: Operacije nad skupovima konačnih automata. Komplement, unija, presek, proizvod i iteracija skupova automata, njihova automatizam. Predavač - vanredni profesor Svetlana Nikolaevna Selezneva Predavanja
Ministarstvo Ruske Federacije za komunikacije i informatizaciju Povolzhskaya Državna akademija za telekomunikacije i informatiku Odsjek za višu matematiku Odobren od strane Metodičkog vijeća PSATI-ja 29. marta 2002.
Predavanje 5. Bojenje ivica grafa. Hromatski indeks grafa. Hromatski indeks bipartitnih grafova. Gornje i donje granice za hromatski indeks grafa. Predavač Selezneva Svetlana Nikolaevna [email protected]
Math-Net.Ru Sveruski matematički portal NP Red'kin, O krugovima koji dozvoljavaju kratke pojedinačne dijagnostičke testove, Diskr. Mat., 1989, svezak 1, broj 3, 71 76 Upotreba sveruskog
MATEMATIČKA LOGIKA (1) Zadaci za praktične vježbe 1. Algebra iskaza Tvrdnja je veličina koja može imati dva značenja: istinito i netačno. Izgovori su naznačeni velikom latinicom
