Lupanovská reprezentace - Lupanov representation - Wikipedia

tento článek ne uvést žádný Zdroje. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Lupanovská reprezentace"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Prosince 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Tento článek může vyžadovat vyčištění setkat se s Wikipedií standardy kvality. Specifický problém je: Neúplná definice Prosím pomozte vylepšit tento článek jestli můžeš. (Srpna 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Lupanov (k, s)-zastoupení, pojmenoval podle Oleg Lupanov, je způsob reprezentace Booleovské obvody aby se ukázalo, že převrácená část Shannonův efekt. Shannon to ukázal téměř všechno Booleovské funkce z n proměnné potřebují a obvod o velikosti nejméně 2ⁿn⁻¹. Reciproční je to, že:

Všechny booleovské funkce n proměnné lze vypočítat s obvodem maximálně 2ⁿn⁻¹ + o (2ⁿn⁻¹) brány.

Definice

Cílem je představit hodnoty booleovské funkce ƒ v tabulce 2^k řádky představující možné hodnoty souboru k první proměnné X₁, ..., ,X_ka 2^n−k sloupce představující hodnoty ostatních proměnných.

Nechat A₁, ..., A_p být oddílem řádků této tabulky tak, že pro i < p, |A_i| = s a ${ displaystyle | A_ {p} | = s ' leq s}$.Nechat ƒ_i(X) = ƒ(X) iff  X ∈ A_i.

Navíc nechte ${ displaystyle B_ {i, w}}$ být množina sloupců, jejichž průsečík s ${ displaystyle A_ {i}}$ je ${ displaystyle w}$.

Viz také

• Učební materiál popisující reprezentaci Lupanova
• Další příklad ze stejného materiálu kurzu