Algorytm ekspansji

Wikipedia:Weryfikowalność
Ten artykuł od 2024-08 wymaga zweryfikowania podanych informacji.
Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Algorytm ekspansji – element metody Espresso, która jest używana do minimalizacji funkcji boolowskich. Jednakże używany samodzielnie również prowadzi do znalezienia minimalnej realizacji zadanej funkcji boolowskiej.

Algorytm ekspansji działa na zbiorach F i R (patrz Zapis funkcji boolowskiej w artykule Funkcja boolowska). Jego idea polega na maksymalnym powiększeniu kostek zbioru F. Ograniczeniem są tu kostki ze zbioru R.

Algorytm

Działanie algorytmu przebiega następująco:

  1. Wyznaczenie macierzy blokujących B(ki, R) dla ki∈F.
  2. Wyznaczenie implikantów prostych funkcji f=(F, R).
  3. Wyznaczenie zbioru implikantów prostych pokrywających wszystkie kostki ki.

Macierze blokujące

Macierz blokującą B(ki, R) tworzy się negując -te kolumny macierzy R przy czym -te elementy kostki ki są jedynkami. Przykładowo:

Należy wyznaczyć macierz blokującą dla każdej kostki ze zbioru F.

Wyznaczenie implikantów prostych

Dla danej kostki ki wyznaczamy ekspansje k+(L,ki). Jeśli L jest minimalnym pokryciem kolumnowym macierzy blokującej, to k+ jest implikantem prostym funkcji f.

Należy zatem znaleźć minimalne pokrycia kolumnowe macierzy Bi. Dla macierzy B1, wyznaczonej powyżej, minimalnymi pokryciami kolumnowymi są i Zauważmy, że istnieje też pokrycie ale nie jest to pokrycie minimalne.

Kostkę k+(L,k) wyznacza się następująco:

Zatem:

Końcowy krok

Gdy mamy już wyznaczone wszystkie implikanty proste, należy wyznaczyć taki ich podzbiór, który pokrywa wszystkie kostki ki ze zbioru F. Suma tych implikantów będzie minimalną realizacją zadanej funkcji f(F, R).

Read other articles:

Basis (majalah)

BASISMajalah Basis 15 Agustus 1951 No. 01 (Nomor Percobaan). (Sumber: Koleksi Majalah Basis)FrekuensiDwibulananTerbitan pertama1 Oktober 1951NegaraIndonesiaBerpusat diDaerah Istimewa YogyakartaBahasaBahasa IndonesiaSitus webwww.majalahbasis.com Basis adalah majalah kebudayaan di Indonesia yang sejauh ini merupakan majalah sejenis yang terpanjang di Indonesia. Terbit perdana pada 1 Oktober 1951, majalah Basis mengusung motto: Jurnalisme Seribu Mata: Basis Menembus Fakta. Banyak pihak mengakui ...

 

Ikan demersal

ikan flounder bersembunyi di bawah pasir berbatu Ikan hag umumnya merayap di dasar laut atau menggali lubang Ikan demersal atau ikan dasar air adalah ikan yang hidup dan makan di dasar laut dan danau (zona demersal). Lingkungan mereka pada umumnya berupa lumpur, pasir, dan bebatuan, jarang sekali terdapat terumbu karang.[1] Sehingga berdasarkan definisi ini, ikan demersal dapat ditemukan dari lingkungan pantai hingga zona laut dalam (abyssal zone), dan banyak ditemukan di lingkungan d...

 

Villa Isola

Artikel ini sebagian besar atau seluruhnya berasal dari satu sumber. Tolong bantu untuk memperbaiki artikel ini dengan menambahkan rujukan ke sumber lain yang tepercaya. Villa IsolaTampak depan (c. 1933-40)Location within JawaTampilkan peta JawaVilla Isola (Indonesia)Tampilkan peta IndonesiaInformasi umumGaya arsitekturArt-decoKotaBandungNegaraIndonesiaKoordinat6°51′40″S 107°35′38″E / 6.861°S 107.594°E / -6.861; 107.594Mulai dibangunOktober 1932Rampun...

WRFX

Classic rock radio station in Kannapolis–Charlotte, North Carolina WRFXKannapolis, North CarolinaBroadcast areaCharlotte/MetrolinaFrequency99.7 MHz (HD Radio)Branding99.7 The FoxProgrammingFormatClassic rockSubchannelsHD2: Black-oriented news (Black Information Network)AffiliationsPremiere NetworksOwnershipOwneriHeartMedia, Inc.(iHM Licenses, LLC)Sister stationsW254AZ, WEND, WHQC, WKKT, WLKOHistoryFirst air dateSeptember 1964; 59 years ago (1964-09) (as WRKB-FM)Former...

 

Hari Australia

Hari AustraliaPelabuhan Sydney pada Hari Australia, 2004Nama lainHari Pendirian, Survival Day, Hari PenjajahanDirayakan olehWarga negara Australia, pemukim dan ekspatriatJenisNasionalMaknaHari pendaratan kapal First Fleet di Port Jackson pada tahun 1788KegiatanPertemuan keluarga, kembang api, piknik dan barbeku; parade; upacara kewarganegaraan; Gelar kehormatan Hari Australia; presentasi Australian of the YearTanggal26 JanuariFrekuensitahunan Hari Australia (bahasa Inggris: Australia Day) ial...

 

2024 European Parliament election in Latvia

Latvia component of the 2024 European Parliament election 2024 European Parliament election in Latvia ← 2019 8 June 2024 2029 → ← outgoing members9 Latvian seats to the European Parliament   Candidate Valdis Dombrovskis Nils Ušakovs Roberts Zīle Party JV Harmony NA Alliance EPP S&D ECR Last election 26.4%, 2 seats 17.6%, 2 seats 16.5%, 2 seats Current seats 3 2 1   Leader Ivars Ijabs Party For Latvia's Development Alliance ALDE Last&#...

2012 United States presidential election in West Virginia

Election in West Virginia Main article: 2012 United States presidential election 2012 United States presidential election in West Virginia ← 2008 November 6, 2012 2016 →   Nominee Mitt Romney Barack Obama Party Republican Democratic Home state Massachusetts Illinois Running mate Paul Ryan Joe Biden Electoral vote 5 0 Popular vote 417,655 238,269 Percentage 62.14% 35.45% County Results Romney  50-60%  60-70%  70-80%&#...

 

Zygmunt Bauman

Polish sociologist and philosopher (1925–2017) Zygmunt BaumanBauman in 2013Born(1925-11-19)19 November 1925Poznań, Second Polish RepublicDied9 January 2017(2017-01-09) (aged 91)Leeds, West Yorkshire, EnglandAlma materUniversity of WarsawLondon School of EconomicsSchoolContinental philosophy · Western MarxismMain interestsEthics · Political philosophy · Sociology · Postmodernity · Postmodern artNotable idea...

 

Propaganda del fatto

L'assassinio del re Umberto I di Savoia ad opera dell'anarchico Gaetano Bresci nel 1900, uno dei più celebri episodi di azione diretta e propaganda del fatto La propaganda del fatto, o propaganda col fatto, è una concezione tipica del movimento anarchico, storicamente concretizzatasi sia in tentativi insurrezionali (un esempio tipico è la cosiddetta Banda del Matese), sia in attentati individuali o collettivi contro sovrani, capi di Stato o altre importanti personalità, sia in atti terror...

Zhongshan railway station

Railway station in Zhongshan, China For the station on the Taipei Metro, Taiwan, see Zhongshan MRT station. Zhongshan中山General informationLocationShiji Dadao, Zhongshan Torch District, Zhongshan, GuangdongChinaCoordinates22°32′48.228″N 113°25′41.4228″E / 22.54673000°N 113.428173000°E / 22.54673000; 113.428173000Line(s)Guangzhou–Zhuhai intercity railwayPlatforms2 (side platforms)Connections Bus routes 02, 05, 08, 18, 61, 68, 90 ConstructionStructure ty...

 

Leandro Lo

Brazilian jiu-jitsu athlete (1989–2022) In this Portuguese name, the first or maternal family name is Pereira and the second or paternal family name is Nascimento. Leandro LoLeandro Lo at the 2022 IBJJF WorldsBornLeandro Lo Pereira do Nascimento(1989-05-11)11 May 1989[1]São Paulo, BrazilDied7 August 2022(2022-08-07) (aged 33)São Paulo, Brazil[2]DivisionGI weight classes Lightweight: −76 kg (168 lb) Middleweight: −82.3 kg (181 lb) Middle-Hea...

 

Bjergbygaard

Manor house at Holbæk, Denmark Bjergbygaard at Golbæk, Denmark Bjergbygaard is a manor house and estate located at Holbæk, Denmark. History The estate is first mentioned in the Danish Census Book under the name Stighsburg and was then crown land. In the 14th century, Bjergbygaard came in the hands of Peder Karlsen and later his daughter, Christine, who was married to Mogens Johansen. He pledged the estate in 1371 and after that the ownership seems to have been divided between multiple owne...

Psalm 84

This article is about Psalm 84 in Hebrew (Masoretic) numbering. For Psalm 84 in Greek Septuagint or Latin Vulgate numbering, see Psalm 85. Psalm 84How amiable are thy tabernaclesHymn psalm · Pilgrimage psalmThe reference to the courts of the Lord can be seen at synagogues and churches, here at the synagogue of Châlons-en-ChampagneOther name Quam dilecta tabernacula tua Domine virtutum Wie lieblich sind deine Wohnungen Written6th century BCE or earlierTextby KorahitesLanguageHebrew (origina...

 

2022–23 Bosnia and Herzegovina Football Cup

Football tournament season Football tournament season 2022–23 Bosnia and Herzegovina Football Cup27th Bosnia and Herzegovina Football CupBilino Polje Stadium hosted the final on 17 May 2023Tournament detailsCountryBosnia and HerzegovinaDates18 October 2022 – 17 May 2023Teams32Defending championsVelež MostarFinal positionsChampionsZrinjski Mostar (2nd title)Runner-upVelež MostarTournament statisticsMatches played37Goals scored127 (3.43 per match)Top goal scorer(s)Nemanja B...

 

Death of Linda Norgrove

2010 aid worker kidnapping in Afghanistan Linda NorgroveNorgrove in Afghanistan, 2010Born1974Altnaharra, ScotlandDied8 October 2010(2010-10-08) (aged 35–36)Korengal Valley, Kunar Province, AfghanistanEducation University of Manchester (PhD) University of London (MA) University of Oregon University of Warwick University of Aberdeen OccupationHumanitarian aid worker On 26 September 2010, British aid worker Linda Norgrove and three Afghan colleagues were kidnapped by members of the Taliba...

KMEX-DT

Univision TV station in Los Angeles KMEX-DTLos Angeles, CaliforniaUnited StatesChannelsDigital: 34 (UHF)Virtual: 34BrandingUnivision 34ProgrammingAffiliations34.1: Univision34.2: UniMásfor others, see § SubchannelsOwnershipOwnerTelevisaUnivision(KMEX License Partnership, G.P.)Sister stationsKFTR-DTKLVEKRCDKSCAHistoryFirst air dateSeptember 29, 1962(61 years ago) (1962-09-29)Former call signsKMEX-TV (1962–2009)Former channel number(s)Analog: 34 (UHF, 1962–2009)Digital: 35 ...

 

منتخب غانا لدوري الرغبي

هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (يوليو 2019) منتخب غانا لدوري الرغبي بلد الرياضة غانا  أكبر فوز أكبر خسارة تعديل مصدري - ت�...

 

قلعة حسين أباد

قلعة حسين‌ أبادمعلومات عامةنوع المبنى قلعةالمنطقة الإدارية مقاطعة تفت البلد  إيرانالصفة التُّراثيَّةتصنيف تراثي المعالم الوطنية الإيرانية التصميم والإنشاءالمهندس المعماري عمارة فارسيةمعلومات أخرىموقع الويب مقاطعة تفتتعديل - تعديل مصدري - تعديل ويكي بيانات قلعة حس�...

超級製作人

此條目需要更新。 (2019年1月13日)請更新本文以反映近況和新增内容。完成修改後請移除本模板。 此條目需要擴充。 (2014年6月5日)请協助改善这篇條目，更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。 超級製作人30 RockLogo格式喜劇开创蒂娜·費主演蒂娜·費 崔西·摩根珍·卡拉寇斯基傑克·麥克布雷爾史考特·阿達斯特猶大·弗雷德蘭德亞歷·...