Způsoby, jak minimalizovat funkce. Tabulkové metody pro minimalizaci funkcí. Základy matematické logiky
Algebry logiky
3.3.1. Minimalizace FAL pomocí Carnotovy matice
Carnotova matice je druh pravdivostní tabulky FAL, která je rozdělena do buněk. Počet buněk matrice je 2 n, Kde n– počet argumentů FAL. Sloupce a řádky matice jsou určeny sadami argumentů. Každá buňka matice odpovídá prvku jednotky FAL (binární číslo). Binární číslo buňky se skládá ze sady argumentů řádků a sloupců. Carnotova matice pro FAL v závislosti na dvou argumentech je uvedena ve formě tabulky 3.3. ze tří argumentů v tabulce 3.4. a ze čtyř argumentů tabulky 3.5.
Tabulka 3.3.
Tabulka 3.5.
| X 3 X 4 X 1 X 2 | ||||
| 0 0 0 0 | 0 0 0 1 | 0 0 1 1 | 0 0 1 0 | |
| 0 1 0 0 | 0 1 0 1 | 0 1 1 1 | 0 1 1 0 | |
| 1 1 0 0 | 1 1 0 1 | 1 1 1 1 | 1 1 1 0 | |
| 1 0 0 0 | 1 0 0 1 | 1 0 1 1 | 1 0 1 0 |
Buňky matic (tabulky 3.3., 3.4. a 3.5.) jsou číslovány desetinnými ekvivalenty binárních čísel buněk. Sousední buňky matice, horizontálně i vertikálně, obsahují sousední binární čísla. Kromě toho se sousední binární čísla nacházejí ve všech sloupcích horního a spodního řádku a také ve všech řádcích nejvzdálenějších sloupců.
Proces minimalizace FAL pomocí Carnotovy matice je založen na zákonu slepování sousedních binárních čísel. Binární čísla sousedních buněk můžete slepit dohromady, ale doporučuje se slepit dohromady sady argumentů, které označují řádky a sloupce matic. Uvažujme slepení binárních čísel buněk prvního sloupce matice (tab. 3.5.).
Buňky 0 a 4, binární čísla 0000 a 0100, výsledek slepení je 0-00.
Buňky 8 a 12, binární čísla 1000 a 1100, výsledek 1-00. Výsledné implikanty jsou slepeny dohromady, protože Pomlčka je na stejném místě a implikantní binární čísla jsou vedle sebe, konečný výsledek je - 00.
Buňky 8 a 12
Pokud jsou tedy všechna binární čísla jednoho sloupce slepena, pak ty bity, které označují řádky, zmizí. Podobně, pokud se slepí všechna binární čísla jednoho řádku, například 4, 5, 7, 6, pak zmizí všechny číslice, které označují sloupce, tzn. výsledek bude následující 01- -.
Pokud jsou binární čísla pouze libovolných dvou buněk slepena, pak se místo této číslice binárních čísel řádku nebo sloupce umístí pomlčka, která se změní, když se buňky přesunou z jednoho řádku na druhý (nebo z jednoho sloupce do druhého). . Například čísla buněk 5 a 13 slepíme dohromady, dostaneme výsledek -101, nebo buňky 7 a 6 výsledek je 011-.
Při slepování binárních čísel osmi sousedních buněk zmizí tři proměnné, například pro buňky 3, 7, 15, 11, 2, 6, 14, 10 zmizí proměnné X 1 , X 2 , X 3. Proměnné X 1 , X 2 zmizí, protože všechny buňky sloupců jsou slepeny dohromady, a X 3, protože poslední dva sloupce jsou slepené.
Před zvažováním příkladů minimalizace FAL pomocí Carnotovy matice je nutné klasifikovat množiny argumentů, pomocí kterých se určují funkce algebry logiky.
Je známo, že pro každý FAL existují 2 sady argumentů n, Kde n– počet argumentů, na kterých funkce závisí popř logický výraz.
Sady argumentů jsou rozděleny do tří typů
1. Množiny argumentů, na kterých je funkce rovna jedné, se nazývají pracovní.
2. Množiny argumentů, na kterých je funkce rovna nule, se nazývají zakázané.
3. Množiny argumentů, pro které může být funkce rovna jedné nebo nule, se nazývají indiferentní.
Pokud daný FAL nemá indiferentní množiny, pak může být zastoupen v doslovný výraz ve formě SDNF. Pokud jsou v dané FAL indiferentní množiny, může mít její reprezentace následující podobu.
kde jsou desetinné ekvivalenty pracovní sady,
– desetinné ekvivalenty zakázaných množin.
Soubory argumentů, které nepatří mezi pracovní a zakázané, budou lhostejné.
Příklad 3.3. Minimalizujte daný FAL ve formě SDNF pomocí Carnotovy matice.
Proto je funkce určena pouze pracovními sadami. Zbytek bude zakázán. Funkce závisí pouze na třech argumentech. Sestavíme Carnotovu matici a do jejích buněk vložíme jedničky, které odpovídají pracovním množinám, a do zbývajících buněk vložíme nuly.
Tabulka 3.5.
| X 2 X 3 X 1 | ||||
| 0 | ||||
Pro minimalizaci jsou buňky matice obsahující jedničky sloučeny do obrysů. Obvod může obsahovat dva články, čtyři nebo všech osm. V v tomto příkladu obrys obsahuje čtyři sousední buňky stejného řádku. Implikant dané kontury bude 1 - -. Výsledek minimalizace je následující, tzn. došlo ke snížení danou funkci v SDNF s 11 písmeny.
Příklad 3.4. Minimalizujte booleovský výraz daný pracovní a zakázanou množinou pomocí Carnotovy matice.
Sestavíme Carnotovu matici pro čtyři proměnné a naplníme buňky jedničkami a nulami pro pracovní a zakázané množiny.
Tabulka 3.6.
| X 3 X 4 X 1 X 2 |
 00
| |||
| (1) | ||||
| (1) | (1) | |||
Při kombinování buněk s jednotkami do obrysů je žádoucí, aby každý obrys zahrnoval největší počet buněk z maxima možného. K tomu využíváme buňky některých indiferentních množin jako buňky pracovních množin a dosazujeme do nich ty v závorkách. Výsledkem jsou tři obrysy obsahující 4 buňky. Ve zobecněném kódu obvodu, který zahrnuje všechny buňky jednoho řádku, proměnné zmizí X 2 X 3 (10 - -). V zobecněném kódu obvodu, který zahrnuje všechny buňky jednoho sloupce, proměnné zmizí X 1 X 2 (- - 11) a pro obrys obsahující dvě buňky po dvou řádcích proměnné zmizí X 2 (při přechodu z jedné linie na druhou v obrysu) a X 3 (při přesunu z jednoho sloupce do druhého). V důsledku toho získáme minimální DNF v následujícím tvaru
Možné možnosti kombinace buněk Carnotovy matice do obrysů jsou znázorněny na obrázku 3.4.
 X 3 X 4
X 1 X 2
| ||||||||||||||||
| A = 0 - 0 - | Z = -0-0 | |||||||||||||||
| N | B = 1 - 1 - | K = - - - 1 | ||||||||||||||
| B = - - 0 0 | L = - 1 - - | |||||||||||||||
| Г = 1 0 - - | M = - - - 0 | |||||||||||||||
| D = - 0 0 1 | H = - 0 - - | |||||||||||||||
| E = - 0 1 - | ||||||||||||||||
| F = -1-1 |
Rýže. 3.1. Možné možnosti pro kombinování buněk Carnotovy matice do obrysů
3.3.2. Minimalizace funkcí logické algebry pomocí matice pěti proměnných
Minimalizační matice pro pět proměnných je konstruována podobně jako Carnotova matice, tzn. v této matici musí být sousední sloupce a řádky označeny sousedními binárními čísly sad proměnných
V matici pěti proměnných (tabulka 3.7.) odpovídají řádky množinám proměnných X 1 X 2 X 3 a sloupce jsou sady proměnných X 4 X 5. Každé buňce matice odpovídá pětimístné číslo binární číslo. Buňky matice (tabulka 3.7.) obsahují desetinné ekvivalenty odpovídajících binárních čísel.
Tabulka 3.7.
| X 4 X 5 X 1 X 2 X 3 | ||||
Minimalizace FAL pomocí matice pěti proměnných spočívá ve spojení buněk s pracovními sadami (včetně, pokud je to nutné, buněk s indiferentními sadami) do obrysů a získání zobecněných kódů odpovídajících těmto obrysům.
Zvláštností je, že ve sloupcích matice pěti proměnných můžete spojit čtyři buňky pouze do obrysů nebo čtyři buňky nahoře, čtyři buňky dole nebo čtyři buňky uprostřed. Například pro poslední sloupec matice mohou obrysy sestávat z buněk 2, 6, 14, 10 nebo 26, 30, 22, 18 nebo 14, 10, 26, 30.
Příklad 3.6. Použijte matici pěti proměnných k minimalizaci následujícího logického výrazu
Sestavíme matici pěti proměnných a buňky pracovních množin vyplníme jedničkami a buňky zakázaných množin nulami.
Buňky s pracovními sestavami spojujeme do obrysů, včetně potřebných buněk indiferentních sad. Pro každý obvod definujeme zobecněný kód.
Tabulka 3.8.
X 4 X 5
 X 1 X 2 X 3
| ||||
| (1) | (1) | (1) | ||
| (1) | ||||
| (1) | (1) | |||
| (1) | (1) | |||
| (1) | (1) | |||
| (1) | ||||
| (1) | (1) | |||
Získáme minimální DNF
1. Definujte zkrácený DNF.
2. Co je to slepá ulička DNF?
3. Jak se vybírá minimální DNF ze slepých DNF?
4. K čemu slouží implikantní tabulka a jak se konstruuje?
5. Vysvětlete analytickou metodu pro minimalizaci Quine-McClasského FAL.
6. Jak je sestrojena Carnotova matice pro tři a čtyři proměnné?
7. Minimalizovat analyticky následující booleovské výrazy určené pouze pracovními sadami
8. Pomocí Carnaughovy matice minimalizujte logické výrazy určené pracovní a zakázanou množinou
Související informace.
Všechny logické funkce jsou zadány buď jako vzorec nebo jako tabulka hodnot. Někdy je potřeba určit nejjednodušší forma záznam této funkce s minimálním počtem elementárních logických funkcí A, NEBO, NE pro snadné použití. K tomu se používají všechny uvažované operace od č. 4 a metody Quine a Veitch.
Quineova metoda umožňuje najít nejjednodušší normální disjunktivní formu logického výrazu, tzn. napište logický výraz ve formě disjunkce nebo konjunkce, přičemž inverzní znaménko se může objevit pouze nad jedním argumentem nebo vůbec. Algoritmus je uveden v odborné literatuře.
Veitchova metoda (Karnaughovy mapy)
V této metodě se pro zobrazení funkce n proměnných nakreslí speciální tabulka, která obsahuje 2n buněk. Každá buňka odpovídá jedné z množin n proměnných. Buňka zaznamená hodnotu přijatou funkcí pro tuto sadu argumentů. Všechny buňky odpovídající množinám obsahujícím nějakou proměnnou bez inverzního znaménka tvoří oblast 2 n -1 buněk. Tato oblast se nazývá plocha dané proměnné(například rozsah proměnné x). Zbývající buňky tvoří oblast této inverzní proměnné. Možné sady argumentů jsou mezi buňky rozmístěny tak, že hranice oblastí všech proměnných a jejich inverze jsou jasné a příslušnost libovolné buňky k určité oblasti je vizuálně snadno identifikovatelná.
1) Funkce jedné proměnné:
2) Funkce dvou proměnných:
3) Diagram pro disjunkci:
4) Diagram pro spojení:
5) Pro tři argumenty:
6) Pro čtyři argumenty:
Daný booleovský výraz můžete minimalizovat seskupením stojící poblíž jednotek a zároveň vyloučit proměnnou, která přechází z přímého do inverzního stavu. Kombinovat můžete nejen vertikálně a horizontálně, ale i podél okrajů, protože in obecný případ Carnotova mapa tvoří torus. Příklad:
b) 
Existují dva směry pro minimalizaci:
- Ш Nejkratší forma zápisu (cílem je minimalizovat hodnost každého termínu);
- Ш Získání minimální formy záznamu (cílem je získat minimální počet znaků pro zápis celé funkce najednou).
- 1. Metoda ekvivalentních transformací
Metoda minimalizace booleovských funkcí ekvivalentními transformacemi je založena na důsledném používání zákonů Booleovy algebry. Metodu ekvivalentních transformací je vhodné používat pouze pro jednoduché funkce a pro počet logických proměnných ne více než 4. Na více proměnné a komplexní funkce zvyšuje se pravděpodobnost chyb při převodu.
2. Quineova metoda.
Při minimalizaci pomocí Quineovy metody se předpokládá, že logická funkce, která má být minimalizována, je dána ve formě SDNF. Je zde použit zákon neúplného spojení. Minimalizace probíhá ve dvou fázích: nalezení jednoduchých implikantů, umístění štítků a určení zásadních implikantů.
Neoznačené termíny se nazývají primární implikanty. Výsledné logické vyjádření není vždy minimální, proto se zkoumá možnost dalšího zjednodušení.
Pro tohle:
- Ш Sestaví se tabulky, v jejichž řádcích jsou zapsány nalezené primární implikanty a ve sloupcích jsou uvedeny podmínky primárního FAL.
- Ш Buňky této tabulky jsou označeny, pokud je primární implikant součástí nějakého primárního termínu.
- Ш Problém zjednodušení spočívá v nalezení minimálního počtu implikantů, které pokrývají všechny sloupce.
Algoritmus Quineovy metody (kroky):
- 1. Nalezení primárních implikantů (původní termíny z DNF jsou zapsány do sloupce a slepeny shora dolů, neoznačené implikanty v tomto kroku přejdou do funkcí).
- 2. Uspořádání redundantních štítků (sestaví se tabulka, ve které jsou řádky primární implikanty, sloupce jsou původní termíny, pokud nějaký min-termín obsahuje primární implikant, pak dáme štítek na průsečík řádku a sloupce) .
- 3. Nalezení podstatných implikantů (pokud je v libovolném sloupci pouze jeden štítek, pak je podstatný primární implikant odpovídajícího řádku).
- 4. Řádek obsahující podstatný implikant a odpovídající sloupce jsou přeškrtnuty (pokud se v důsledku smazání sloupců objeví řady primárních implikantů, které neobsahují štítky nebo obsahují v řádcích totožné štítky, pak se takové primární implikanty přeškrtnou ven a ve druhém případě je ponechán jeden z nižších pozic).
- 5. Výběr minimálního pokrytí (z tabulky získané v kroku 3 vyberte sadu primárních implikantů, která zahrnuje štítky ve všech sloupcích s alespoň jedním štítkem v každém, s několika možné možnosti přednost se dává krytině s minimálním celkovým počtem prvků v implikantech tvořících krytinu).
- 6. Výsledek se zapíše jako funkce.
Nechť je dána funkce:
Pro usnadnění prezentace označme každý prvek jednotky z funkce SDNF F nějakým desetinným číslem (libovolně). Provádíme lepení. Složka 1 je slepena pouze složkou 2 (proměnnou x3) a složkou 3 (proměnnou x2) složky 2 se složkou 4 atd. Výsledkem je:
Všimněte si, že výsledkem lepení je vždy elementární výrobek, který je společná část lepené složky.
se vzhledem stejného elementárního díla. Další lepení není možné. Po provedení absorpcí (vymažeme všechny absorbované elementární produkty z výsledného DNF) získáme redukovaný DNF:
Pojďme k další fáze. Pro získání minimálního DNF je nutné odstranit všechny nepotřebné primární implikanty ze sníženého DNF. To se provádí pomocí speciální matice Quine implikant. Řádky takové matice jsou označeny primárními implikanty booleovská funkce, tj. členy zkrácené DNF, a sloupce jsou prvky jednotky, tj. členy SDNF booleovské funkce.
Implikantní matice má tvar viz tabulka. 1.1
Tabulka 1.1 Matice implikantů
Jak již bylo uvedeno, jednoduchý implikant pohlcuje nějakou složku jednotky, pokud je její vlastní částí. Odpovídající buňka matice implikantu na průsečíku řádku (s uvažovaným jednoduchým implikantem) a sloupce (s prvkem jednoty) je označena křížkem (tabulka 1). Minimální DNF jsou konstruovány z implikantní matice následovně:
- 1. jsou prohledány sloupce implikantní matice, které mají pouze jeden křížek. Jednoduché implikanty odpovídající těmto křížkům se nazývají základní a tvoří tzv. jádro booleovské funkce. Jádro je nutně zahrnuto v minimálním DNF.
- 2. jsou zvažovány různé možnosti výběr sady jednoduchých implikantů, které překryjí zbývající sloupce matice implikantů křížky, a výběr možností s minimálním celkovým počtem písmen v takové sadě implikantů.
Funkce tedy vypadá takto:
3. Quine-McCluskeyho metoda.
Metoda je Quineova metoda formalizovaná ve fázi hledání jednoduchých implikantů. Formalizace se provádí takto:
- 1. Všechny jednotkové složky z SDNF booleovské funkce F jsou zapsány svými binárními čísly.
- 2. Všechna čísla jsou rozdělena do nepřekrývajících se skupin. Znak vzniku i-té skupiny: i jednotky v každém binárním čísle jsou prvky jedné.
- 3. Lepení se provádí pouze mezi čísly sousedních skupin. Slepená čísla jsou označena nějakým znakem (přeškrtnutá, hvězdička atd.).
- 4. Provádějí se všechny druhy lepení, jako u metody Quine. Čísla neoznačená po nalepení jsou jednoduchými implikanty.
Tvoříme skupiny binárních čísel. Znakem vzniku i-té skupiny je i jednotek v binárním čísle konstituční jednotky (tab. 1.2).
Tabulka 1.2 Skupiny binárních čísel
Slepíme čísla ze sousedních skupin tabulky. 1.3 Sloučit lze pouze čísla, která mají na stejných pozicích pomlčky. Označme si slepená čísla. Výsledky lepení zapíšeme do tabulky. 1.4.
Tabulka 1.4 Výsledky lepení 2
Podle tabulky 5. Určíme množinu jednoduchých implikantů - 0--1 a 111-, odpovídajících minimálnímu DNF. K obnovení doslovné formy jednoduchého implikantu stačí zapsat součiny těch proměnných, které odpovídají zbývajícím binárním číslicím:
Rozdělení prvků do skupin umožňuje snížit počet párových porovnávání při lepení.
4. Metoda Veitchova diagramu.
Tato metoda vám umožňuje rychle získat minimální DNF booleovské funkce f malý počet proměnné. Metoda je založena na specifikaci booleovských funkcí pomocí diagramů speciálního typu, nazývaných Veitchovy diagramy. Pro booleovskou funkci dvou proměnných vypadá Veitchův diagram (obrázek 1).
Obr. 1.
Každá buňka v diagramu odpovídá sadě proměnných booleovské funkce v její pravdivostní tabulce. Na (obr. 1) je tato korespondence zobrazena, je-li buňka ve Veitchově diagramu označena jedničkou, pokud má booleovská funkce na odpovídající množině jednu hodnotu. Nulové hodnoty Booleovské funkce nejsou zahrnuty ve Veitchově diagramu. Pro booleovskou funkci tří proměnných má Veitchův diagram další pohled(Obrázek 2).
Obr.2.
Přidáním stejné tabulky k ní vznikne diagram pro funkci 4 proměnných (obr. 3).
Obr.3.
Stejným způsobem, tedy přidáním dalšího diagramu 3 proměnných k právě uvažovanému, můžete získat diagram pro funkci 5 proměnných atd., ale diagramy pro funkce s více než 4 proměnnými se používají zřídka.
5. Carnotovy mapy.
Karnaughova mapová metoda je jednou z grafické metody minimalizaci funkce. Tyto metody jsou založeny na použití funkcí vizuálního vnímání, protože s jeho pomocí lze téměř okamžitě rozpoznat určité jednoduché konfigurace.
Sestavme tabulku pro metodu Karnaughovy mapy (tabulka 1.6).
Tabulka 1.6 Carnotovy mapy
Nyní spočítejme celkový počet všech křížků se štítky s minimálním počtem křížků. V našem případě bude takových křížů 5: tři čtyřčlánkové a dva dvoučlánkové. Tyto kříže odpovídají následujícím jednoduchým implikantům:
pro první - X3 X 4;
pro druhé - X 1 X 3;
pro třetí - X2 X 3;
pro čtvrtý - Xi X 2 X 4;
pro páté - X 1 X 2 X 4;
Minimální DNF by vypadalo takto:
6. Metoda nejisté koeficienty.
Tuto metodu lze použít pro libovolný počet argumentů. Ale protože je tato metoda poměrně těžkopádná, používá se pouze v případech, kdy počet argumentů není větší než 5-6.
Metoda neurčitých koeficientů využívá zákonů univerzální a nulové množiny a zákonů opakování. Na začátku jsou všechny koeficienty nejisté (odtud název metody).
Sestrojme matici nejistých koeficientů pro čtyři argumenty. V tomto případě budeme mít soustavu 16 rovnic.
Přirovnejme všechny koeficienty k 0 v těch řádcích, které odpovídají 0 ve vektorovém sloupci. Potom odpovídající koeficienty v dalších řádcích srovnáme s 0. Po těchto transformacích bude mít systém následující podobu (obr. 4):
Obr.4.
Nyní v každém řádku musíte vybrat minimální koeficient pořadí a nastavit jej na jednu a zbývající koeficienty na 0. Poté přeškrtněte identické linie, přičemž jeden z nich ponecháme (přeškrtnou se i ty řádky, u kterých jsou všechny koeficienty rovny 0).
Zapišme si nyní spojky odpovídající koeficientům, rovné jednotkám. Dostaneme minimální DNF.
Metody hledání minima funkcí. Hledání maxim se změnou znaménka funkce redukuje na hledání minim. M. f. m. je obor výpočetní matematiky, který hraje důležitou roli v aplikacích, jako je optimální výběr. možnosti v plánování, projektování a operačním výzkumu, úkoly řízení technologických postupů, kontrola pohybu složité objekty atd. M. f. m se používají i k řešení soustav rovnic a nerovnic při hledání spektra operátorů, při řešení okrajových úloh atp.
Nejstudovanější jsou M. f. m - ve vztahu k funkcím definovaným v celém -rozměrném euklidovském prostoru. Zvažme je, aniž bychom se dotkli diskrétních a diskrétně spojitých minimalizačních problémů, stejně jako problémů minimalizace za přítomnosti omezení. To druhé lze v mnoha případech zredukovat na problém bezpodmínečné minimalizace (například pomocí penalizačních funkcí). Nebudeme uvažovat o metodách hledání minima na základě přímého použití nutné podmínky extremum, neboť řešení výsledných soustav nelineárních rovnic lze považovat za problém minimalizace součtu kvadrátů reziduí (resp. maximálního modulu reziduí). Možnost aplikace a srovnávací účinnosti různých M. f. m. je do značné míry určeno třídou funkcí, na které jsou aplikovány. Většina M. f. m. umožňují najít lokální minimum a pouze apriorní informace o vlastnostech funkce (konvexita, unimodalita) nám umožňují považovat toto minimum za globální. Metody, které zaručují hledání globálního minima s danou přesností pro dostatečně obecné třídy funkce jsou velmi pracné. Na
V praxi se pro nalezení globálního minima používá především kombinace metody Monte Carlo a jedné z lokálních minimalizačních metod.
Široká třída M. f. m. je popsána následujícím výpočtovým schématem. Nechť je funkce, která má být minimalizována, definována v libovolně zvoleném počátečním bodě. Předpokládejme, že má spojité parciální derivace až do řádu včetně, budeme ho považovat za derivaci nultého řádu). Pro získání postupné aproximace do lokálního minima se zkonstruuje posloupnost bodů podle následujícího tvaru:
kde označuje vektor parciálních derivací řádu vypočitatelných funkcí jeho argumentů. Nazývá se řád vyšších parciálních derivací vypočítaných pro implementaci vzorce (1). pořadí metody. Základní skupina metod používaných v praxi má tu zvláštnost, že informace nutné k výpočtu další hodnoty jsou vyjádřeny prostřednictvím omezeného počtu parametrů vypočítaných na tento krok A předchozí kroky proces. Metoda se nazývá -step, pokud schéma algoritmu má, počínaje některými, následující strukturu: v kroku vypočítáme parametry, kde - některé přirozené číslo a vektor v následujícím tvaru:
(počáteční parametry jsou vypočteny pomocí speciálních postupů). V široce používaných metodách sestupu je operátor specifikován v následujícím tvaru:
Kde reálné číslo, který se nazývá krokový násobič, vektor určuje směr sestupu. Mezi sestupovými metodami vynikají monotónní sestupové metody nebo relaxační metody. Metoda je relaxační, je-li při k Beli spojitě diferencovatelná, pak je relaxace metody (3) zajištěna, když se tvoří směr sestupu ostrý roh se směrem sklonu a je poměrně malý. Obecná teorie relaxačních procesů je nejúplněji rozvinuta pro případ konvexních funkcí. Jako základ uvažují se parametry charakterizující proces, relaxační úhly mezi a směr gradientu), stejně jako relaxační faktory určené rovností
kde je gradient funkce (pro kvadratický funkcionál s nejstrmějším sestupem). Označme redukovaným koeficientem. relaxace. Nutné a dostatečný stav konvergence relaxačního procesu pro silně konvexní funkci:
Mezi relaxačními metodami jsou nejznámější metody gradientní. Podívejme se blíže na jednostupňové gradientní metody. Obecné schéma jsou následující:
V rámci tohoto schématu lze rozlišit následující modifikace:
A) gradientní sestup s konstantním krokem: matice identity;
b) nejrychlejší klesání gradientu: , kde je určeno z minimální podmínky
c) Newton-Raphsonova metoda: , kde je Hessián v bodě
d) meziobvody: . Mezi nejběžnější dvoustupňové gradientové metody patří metody konjugovaného gradientu; Příkladem dvoufázového schématu je metoda konjugovaného gradientu Fletcher-Reeves:
Metody a) a b) s dostatečným všeobecné podmínky(první - pro dostatečně malé a) konvergovat k lokálnímu minimu s rychlostí geom. postup. Metoda c) za dostatečně obecných podmínek konverguje z dostatečně malého okolí minima s kvadratickou rychlostí. Mezischéma d) je flexibilnější a umožňuje při určité úpravě sekvencí získat také kvadratický konvergenční poměr při vyšší slabé požadavky k počátečnímu přístupu.
Nevýhodou metod c), d) je nutnost počítat Hessián. Metody sdružených gradientů a tzv. variabilní metrické algoritmy, které mají vlastnosti zrychlené konvergence pro dostatečně hladké funkce v blízkosti minima, tuto nevýhodu nemají. Schémata variabilních metrických algoritmů jsou ve své podstatě kombinací schématu konjugovaného gradientu a Newton-Raphsonovy metody. Současně s pohybem podle schématu, jako jsou konjugované gradienty, dochází k iterativní aproximaci matice, která je inverzí k Hessianu v minimálním bodě. Po každých n krocích procesu následuje krok podle Newton-Raphsonovy metody, kde je místo toho použita její aproximace.
Pokud je přechod porušen, výše uvedené metody neplatí. Proto velká důležitost mít metody pro minimalizaci konvexních (ne nutně diferencovatelných) funkcí; Tyto metody lze rozdělit do 2 skupin: 1) metody gradientního typu a 2) metody „řezné roviny“. Skupina 1 zahrnuje různé modifikace metody zobecněného gradientu a také schémata se zrychlenou konvergencí na základě roztahování prostoru. ve směru gradientu nebo rozdílu dvou po sobě následujících gradientů. Mezi metody 2. skupiny patří např. Kellyho metoda. Nechť ZP je konvexní (ohraničená) množina, na které je definována posloupnost bodů, ve kterých se počítá zobecněný gradient. Pak se to najde jako řešení problému: najít
Kellyho metoda konverguje ve funkcionálu pro jakékoli počáteční . Z běžných minimalizačních metod je třeba poznamenat zejména roklinovou metodu pro minimalizaci funkcí s vysoce protáhlými úrovňovými hyperplochy; metody vyhledávání souřadnic variabilní systém souřadnice; metody náhodného vyhledávání; kombinované metody rychlého sestupu a náhodného vyhledávání, kdy je směr klesající funkce určen metodou Monte Carlo; metody diferenciálního sestupu, metody stochastické aproximace atd. V optimálních úlohách. regulace mají velký význam vyhledávací metody nultého řádu. Minimalizační algoritmy jsou pro tento případ obvykle založeny na myšlence lineární nebo kvadratické aproximace minimalizované funkce nebo diferenční aproximace odpovídajících parciálních derivací. Pro hledání globálního extrému byla navržena řada metod. Základní z toho: metoda Monte Carlo, kombinace metody Monte Carlo pro určení výchozího bodu s jedním z algoritmů místní vyhledávání, metody založené na konstrukci spodní obálky dané funkce, metody sekvenčního ořezávání podmnožin, metody konstrukce trajektorií, které všude hustě pokrývají doménu definice funkce, a minimalizace podél těchto trajektorií.
K řešení speciální třídy multiextrémních úloh, používají se metody dynamického programování.
V dnešní době se vytváří optimální časy. algoritmy pro minimalizaci funkcí různých tříd. Nechť je třída funkcí definovaných v krychli a mající parciální derivace až do s-tého řádu, splňující Lipschitzovu podmínku s konstantou L. Libovolný minimalizační algoritmus od , využívající informace o hodnotách f a jeho derivacích až do řádu včetně při ne více než N bodů je ekvivalentní (ve smyslu výsledku) nějakému algoritmu A pro získání sekvence iterací (1) pro aproximaci požadované hodnoty pomocí konečné operace
kde je nějaká vypočítatelná funkce. Představme si následující zápis:
Algoritmus, pro který je dosaženo optimální. Podmínky znamenají asymptotickou optimalitu, resp. řádovou optimalitu algoritmu
Navíc volba , ovlivňuje pouze konstantu v zadaném odhadu. V konkrétním případě máme:
kde je min. síť v .
Další přístup k budování optimální. Minimalizační algoritmy jsou spojeny se zobecněním myšlenek pro sekvenční statistická řešení. Minimalizační algoritmus je považován za řízenou sekvenci experimentů, z nichž každý poskytuje určitý výsledek. Apriorní pravděpodobnostní míra je určena na základě souboru výsledků. Po získání konkrétního výsledku dalšího experimentu jsou pravděpodobnosti přerozděleny podle Bayesova vzorce a je vybrán další experiment nebo je učiněno konečné rozhodnutí. Algoritmy se od sebe liší v pravidle, podle kterého se vybírá další experiment, v pravidlech pro zastavení a volbu konečného řešení. Kvalita řešení je určena ztrátovou funkcí, která je zprůměrována v souladu s výsledkem získaným dne v tomto stádiu rozdělení pravděpodobnosti. V těchto termínech je nastolen problém výběru optimálního. algoritmus jako konstrukce sekvenčního Bayesova pravidla pro hledání řešení. Tato formulace je zajímavá tím, že v jejím rámci lze zohlednit statistické vlastnosti třídy řešených problémů a porovnat „průměrné“ ztráty spojené s chybou řešení s náklady spojenými s dolaďováním řešení. Lit.: Lyubich Yu I., Maistrovsky G. D. Obecná teorie relaxační procesy pro konvexní funkcionály. “Advances in Mathematical Sciences”, 1970, roč. 25, století. 1; Mikhalevich V. S. Sekvenční optimalizační algoritmy a jejich aplikace. "Kybernetika", 1965, N5 1-2; Ivanov V.V optimálních algoritmů minimalizace funkcí některých tříd. "Kybernetika", 1972, č. 4; Divoký D. Dk. Metody hledání extrému. Za. z angličtiny M., 1967.
V. V. Ivanov, V. S. Michalevič, N. Z. Shor.
8.3. Analytické metody pro minimalizaci spínacích funkcí
Quineova metoda.
Metoda je založena na párovém porovnání a slepení pokud možno všech složek (členů SDNF). K tomu je každá složka porovnána s následujícími, což vede k získání implikantu. Výsledné implikanty se opět porovnají a pokud možno slepí – atp. dokud zbývající implikanty již nelze slepit. Jsou to jednoduché implikanty, jejich disjunkce je zkrácená DNF.
Pro řazení je vhodné rozdělit složky do skupin podle počtu neinvertovaných proměnných. V tomto případě je každá následující složka, počínaje shora, porovnávána pouze se složkami skupiny sousedící se spodní částí, s počtem neinvertovaných proměnných o jednu více.
Nechť existuje spínací funkce definovaná pomocí SDNF:
Rozdělme složky do skupin podle počtu neinvertovaných proměnných.
Římské číslo čísla skupiny odpovídá počtu neinverzních proměnných. Nakreslete čáry označující složky, které se mají slepit. Výsledkem lepení je vždy elementární spojka, která je běžnou součástí původních spojek (zejména složkou).
Výsledné implikanty umožňují i lepení a výsledkem je stejný implikant 
.
Další lepení je nemožné, proto jsou výsledné implikanty jednoduché a zkrácené DNF má tvar:
První etapa je dokončena. Ve druhé fázi je nutné odstranit zbytečné primární implikanty. To se provádí pomocí speciální tabulky Quine implikant (krycí tabulka). Řádky tabulky jsou označeny jednoduchými implikanty spínací funkce, tzn. členy zkráceně DNF, a kolony jsou složkami jednotky, tzn. členy spínací funkce SDNF.
Jak již bylo uvedeno, jednoduchý implikant pohlcuje nějakou složku jednotky, pokud je její vlastní částí. Odpovídající buňka tabulky implikantů na průsečíku řádku daného jednoduchého implikantu a sloupců se složkami jednotky je označena např. znaménkem „+“. Minimální DNF jsou konstruovány pomocí implikantní tabulky takto:
1) prohledají se sloupce tabulky implikantů, které mají pouze jeden křížek, jednoduché implikanty odpovídající těmto křížkům se nazývají základní a tvoří tzv. jádro spínací funkce. Jádro je nutně zahrnuto v minimálním DNF;
2) zvažují se různé možnosti pro výběr sady jednoduchých implikantů, které překryjí zbývající sloupce matice implikantů křížky, a jsou vybrány možnosti s minimálním celkovým počtem písmen.
Jádrem naší funkce (Tabulka 35) jsou implikanty 
a x 1 x 2 x 3, tj. funkce má unikátní uváznutí a minimální DNF:
Tabulka 35
Quineova implikační tabulka
|
Složky 1 (členové SDNF) |
|||||||
|
implikanti |
|
|
|
|
|
|
|
|
| |||||||
Je vidět, že implikant x 2 x 3 x 4 je nadbytečný, protože pokrývá složky již pokryté implikanty. 
, x 1 x 2 x 3 .
Počet křížků v řádku je mocninou 2; Navíc se můžete ujistit, že se rovná N=2 n - k, kde k je počet písmen v jednoduchém implikantu, n je počet proměnných, na kterých funkce závisí.
Pokud není SDNF nejprve specifikován, pak je třeba jej získat například pomocí nám již známých metod.
Je jasné, že pro velké implikantní tabulky je obtížné vizuálně identifikovat možnosti s minimálním počtem písmen. Proto se používá Petrikova metoda, která umožňuje získat všechny slepé DNF z implikantní tabulky konstrukcí její tzv. konjunktivní reprezentace. K tomu se všechny jednoduché implikanty označí různými písmeny (A, B, C v tabulce 35) a pak se pro každý sloupec zkonstruuje disjunkce všech písmen označujících řádky tabulky, jejichž průsečík s daným sloupcem je označené křížkem. Konjunktivní reprezentace implikantní matice je vytvořena jako konjunkce vytvořených disjunkcí pro všechny sloupce. Všechny vztahy Booleovy algebry přepínacích funkcí lze za účelem zjednodušení aplikovat na konjunktivní reprezentaci implikantní tabulky. Po otevření závorek a provedení všech možných absorpcí získáme disjunkci konjunkcí, z nichž každá obsahuje všechny implikanty slepé uličky DNF.
To znamená, že slepá ulička DNF obsahuje dva hlavní implikanty ( 
a zároveň C=x 1 x 2 x 3) a má tvar:
Quine-McCluskeyho metoda.
Metoda je formalizací Quineovy metody, orientovaná na využití počítačů. Formalizace spočívá v zaznamenání složek jednotky (členů SDNF) s jejich binárními čísly. Všechna čísla jsou rozdělena do disjunktních skupin podle počtu jedniček v binárním čísle. Vazby se provádějí pouze mezi sousedními skupinami. Kategorie, která má být vyřazena, je označena znakem „–“ („pomlčka“). Další skupiny z výsledných implikantů jsou tvořeny s ohledem na identické umístění pomlčky. Toto označení implikantů se nazývá zobecněné kódy. Nechť je dána logická funkce
111101001000110.
Seskupme tyto složky jednotky podle počtu jednotek:
Další lepení není možné. Minimální DNF jsou pak nalezeny pomocí implikantní tabulky (Tabulka 36):
To znamená, že slepé DNF obsahují tři hlavní implikanty a mají tvar:
(dvě inverze);
(tři inverze).
Tabulka 36
Quine-McCluskeyho implikační tabulka
|
implikanti |
Složky jednotek |
|||||||
Všimněte si, že slepení dvou implikantů s pomlčkou je možné pouze v případě, že jsou vhodně umístěny, například:
|
|
|
|
|
Můžete si vybrat kterýkoli ze získaných TDNF a s ohledem na menší počet inverzí i první.
Blake-Poretského metoda.
Metoda umožňuje získat redukovanou DNF booleovské funkce z jejího libovolného DNF, a nikoli z SDNF, jako v metodách Quine a Quine-McCluskey, za použití zákona zobecněného lepení. Metoda je založena na následujícím tvrzení: pokud se v libovolném DNF booleovské funkce provedou všechny možné operace inverzní ke zobecněnému slepení a poté se provedou všechny absorpce, pak je výsledkem snížená DNF funkce.
Nechť je dána funkce DNF:
Je vidět, že zákon zobecněného lepení vzhledem k proměnné x 1 lze aplikovat na první a druhou spojku; dostaneme:
Podobně pro první a třetí spojku:
těch. vše zůstává jak je!
Druhá a třetí spojka umožňují zobecněné lepení podél x2:
Pojďme k DNF:
Po aplikaci zákona idempotence (opakování) a absorpce dostaneme:
Pokusy o další použití generalizované vazby a absorpce nepřinášejí výsledky. V důsledku toho se získá snížená funkce DNF.
Tabulka 37
Implikační tabulka pro ilustraci Blake-Poretského metody
|
implikanti |
Sady funkcí a jeho významy |
|||||||||
Pracovní (jednotkové) množiny tak mohou být pokryty třemi primárními implikanty, např. 
,
,
. Jádro zahrnuje implikanty 
,
. DNF uváznutí pak mají tvar:
(lepší co do počtu inverzí).
