Formas de minimizar funciones. Métodos tabulares para minimizar funciones. Elementos de la lógica matemática.
Álgebras de lógica
3.3.1. Minimizando FAL usando la matriz de Carnot
La matriz de Carnot es una especie de tabla de verdad FAL, que se divide en celdas. El número de celdas de la matriz es 2. norte, Dónde norte– número de argumentos FAL. Las columnas y filas de una matriz se designan mediante conjuntos de argumentos. Cada celda de la matriz corresponde a un constituyente de la unidad FAL (número binario). El número binario de una celda consta de un conjunto de argumentos de fila y columna. La matriz de Carnot para FAL, que depende de dos argumentos, se presenta en forma de tabla 3.3., a partir de tres argumentos en la tabla 3.4. y de cuatro argumentos cuadro 3.5.
Tabla 3.3.
Tabla 3.5.
| incógnita 3 incógnita 4 incógnita 1 incógnita 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 |
Las celdas de las matrices (Tablas 3.3., 3.4. y 3.5.) están numeradas con equivalentes decimales de los números binarios de las celdas. Las celdas de la matriz adyacentes, tanto horizontal como verticalmente, contienen números binarios adyacentes. Además, los números binarios adyacentes se encuentran en todas las columnas de las filas superior e inferior, así como en todas las filas de las columnas más externas.
El proceso de minimizar FAL utilizando la matriz de Carnot se basa en la ley de pegar números binarios adyacentes. Puede pegar números binarios de celdas adyacentes, pero se recomienda pegar conjuntos de argumentos que indiquen las filas y columnas de las matrices. Consideremos pegar los números binarios de las celdas de la primera columna de la matriz (Tabla 3.5.).
Celdas 0 y 4, números binarios 0000 y 0100, respectivamente, el resultado del pegado es 0-00.
Celdas 8 y 12, números binarios 1000 y 1100, resultado 1-00. Los implicantes resultantes están pegados entre sí, porque El guión está en el mismo lugar y los números binarios implicantes son adyacentes, el resultado final es - 00.
Celdas 8 y 12
Por lo tanto, si todos los números binarios de una columna se pegan, los bits que indican las filas desaparecen. De manera similar, si todos los números binarios de una fila están pegados, por ejemplo 4, 5, 7, 6, entonces todos los dígitos que indican las columnas desaparecen, es decir. el resultado será el siguiente 01- -.
Si los números binarios de solo dos celdas cualesquiera están pegados, entonces se coloca un guión en lugar de ese dígito de los números binarios de una fila o columna que cambiará cuando las celdas se muevan de una línea a otra (o de una columna a otra). . Por ejemplo, si pegamos los números de las celdas 5 y 13, obtenemos el resultado -101, o las celdas 7 y 6, el resultado es 011-.
Al pegar números binarios de ocho celdas adyacentes, desaparecen tres variables, por ejemplo, para las celdas 3, 7, 15, 11, 2, 6, 14, 10, las variables desaparecen incógnita 1 , incógnita 2 , incógnita 3. variables incógnita 1 , incógnita 2 desaparecen porque todas las celdas de las columnas están pegadas entre sí, y incógnita 3 porque las dos últimas columnas están pegadas.
Antes de considerar ejemplos de minimización de FAL utilizando la matriz de Carnot, es necesario clasificar los conjuntos de argumentos con cuya ayuda se determinan las funciones del álgebra lógica.
Se sabe que para cada FAL existen 2 conjuntos de argumentos norte, Dónde norte– el número de argumentos de los que depende la función o expresión lógica.
Los conjuntos de argumentos se dividen en tres tipos.
1. Los conjuntos de argumentos en los que la función es igual a uno se denominan de trabajo.
2. Los conjuntos de argumentos en los que la función es igual a cero se denominan prohibidos.
3. Los conjuntos de argumentos para los cuales una función puede ser igual a uno o a cero se denominan indiferentes.
Si un FAL dado no tiene conjuntos indiferentes, entonces se puede representar en expresión literal en forma de SDNF. Si existen conjuntos indiferentes en un FAL determinado, su representación puede tener la siguiente forma.
¿Dónde están los equivalentes decimales? conjuntos de trabajo,
– equivalentes decimales de lances prohibidos.
Los conjuntos de argumentos que no se encuentren entre los válidos y los prohibidos serán indiferentes.
Ejemplo 3.3. Minimice el FAL dado en forma de SDNF usando la matriz de Carnot.
Por lo tanto, la función se especifica únicamente mediante conjuntos de trabajo. El resto estará prohibido. La función depende sólo de tres argumentos. Construimos una matriz de Carnot y colocamos unos en sus celdas que corresponden a los conjuntos de trabajo, y ceros en las celdas restantes.
Tabla 3.5.
| incógnita 2 incógnita 3 incógnita 1 | ||||
| 0 | ||||
Para minimizar, las celdas de la matriz que contienen unos se combinan en contornos. El circuito puede incluir dos celdas, cuatro o las ocho. EN en este ejemplo el contorno incluye cuatro celdas adyacentes de la misma fila. El implicante del contorno dado será 1 - -. El resultado de la minimización es el siguiente, es decir hubo una reducción función dada en SDNF con 11 letras.
Ejemplo 3.4. Minimizar la expresión booleana dada por los conjuntos de trabajo y prohibidos utilizando la matriz de Carnot.
Construimos una matriz de Carnot para cuatro variables y llenamos las celdas con unos y ceros, respectivamente, para los conjuntos de trabajo y prohibidos.
Tabla 3.6.
| incógnita 3 incógnita 4 incógnita 1 incógnita 2 |
 00
| |||
| (1) | ||||
| (1) | (1) | |||
Al combinar celdas con unidades en contornos, es deseable que cada contorno incluya mayor numero células desde el máximo posible. Para hacer esto, utilizamos las celdas de algunos conjuntos indiferentes como celdas de conjuntos de trabajo, sustituyéndolas por las que están entre paréntesis. Como resultado, obtenemos tres contornos que contienen 4 celdas cada uno. En el código de circuito generalizado, que incluye todas las celdas de una línea, las variables desaparecen. incógnita 2 incógnita 3 (10 - -). En el código de circuito generalizado, que incluye todas las celdas de una columna, las variables desaparecen. incógnita 1 incógnita 2 (- - 11) y para un contorno que contiene dos celdas de dos líneas, las variables desaparecen incógnita 2 (al pasar de una línea a otra en un contorno) y incógnita 3 (al pasar de una columna a otra). Como resultado, obtenemos el DNF mínimo de la siguiente forma
En la Figura 3.4 se muestran posibles opciones para combinar celdas de la matriz de Carnot en contornos.
 incógnita 3 incógnita 4
incógnita 1 incógnita 2
| ||||||||||||||||
| Un = 0 - 0 - | Z = - 0 - 0 | |||||||||||||||
| norte | B = 1 - 1 - | k = - - - 1 | ||||||||||||||
| B = - - 0 0 | L = - 1 - - | |||||||||||||||
| Г = 1 0 - - | METRO = - - - 0 | |||||||||||||||
| D = - 0 0 1 | H = - 0 - - | |||||||||||||||
| mi = - 0 1 - | ||||||||||||||||
| F = - 1 - 1 |
Arroz. 3.1. Posibles opciones para combinar celdas de la matriz de Carnot en contornos
3.3.2. Minimizar funciones de álgebra lógica usando una matriz de cinco variables
La matriz de minimización para cinco variables se construye de manera similar a la matriz de Carnot, es decir En esta matriz, las columnas y filas adyacentes deben designarse mediante números binarios adyacentes de conjuntos de variables.
En una matriz de cinco variables (Tabla 3.7.), las filas corresponden a conjuntos de variables incógnita 1 incógnita 2 incógnita 3, y las columnas son conjuntos de variables. incógnita 4 incógnita 5. Cada celda de la matriz corresponde a un número de cinco dígitos. número binario. Las celdas de la matriz (Tabla 3.7.) contienen los equivalentes decimales de los números binarios correspondientes.
Tabla 3.7.
| incógnita 4 incógnita 5 incógnita 1 incógnita 2 incógnita 3 | ||||
Minimizar FAL utilizando una matriz de cinco variables consiste en combinar celdas con conjuntos de trabajo (incluidas, si es necesario, celdas con conjuntos indiferentes) en contornos y obtener códigos generalizados correspondientes a estos contornos.
La peculiaridad aquí es que en las columnas de una matriz de cinco variables, se pueden combinar cuatro celdas en contornos solamente, o cuatro celdas en la parte superior, o cuatro celdas en la parte inferior, o cuatro celdas en el medio. Por ejemplo, para la última columna de la matriz, los contornos pueden consistir en las celdas 2, 6, 14, 10 o 26, 30, 22, 18 o 14, 10, 26, 30.
Ejemplo 3.6. Utilice una matriz de cinco variables para minimizar la siguiente expresión lógica
Construimos una matriz de cinco variables y llenamos las celdas de los conjuntos de trabajo con unos y las celdas de los conjuntos prohibidos con ceros.
Combinamos celdas con conjuntos de trabajo en contornos, incluidas las celdas necesarias de conjuntos indiferentes. Para cada circuito definimos un código generalizado.
Tabla 3.8.
incógnita 4 incógnita 5
 incógnita 1 incógnita 2 incógnita 3
| ||||
| (1) | (1) | (1) | ||
| (1) | ||||
| (1) | (1) | |||
| (1) | (1) | |||
| (1) | (1) | |||
| (1) | ||||
| (1) | (1) | |||
Obtenemos el DNF mínimo
1. Defina el DNF abreviado.
2. ¿Qué es un DNF sin salida?
3. ¿Cómo se selecciona el DNF mínimo entre los DNF sin salida?
4. ¿Para qué se utiliza la tabla de implicantes y cómo se construye?
5. Explique el método analítico para minimizar el FAL de Quine-McClassky.
6. ¿Cómo se construye la matriz de Carnot para tres y cuatro variables?
7. Minimizar analíticamente las siguientes expresiones booleanas especificadas únicamente por conjuntos de trabajo
8. Utilizando la matriz de Carnaugh, minimice las expresiones lógicas especificadas por los conjuntos de trabajo y prohibidos.
Información relacionada.
Todas las funciones lógicas se especifican como fórmula o como tabla de valores. A veces es necesario determinar forma más simple registrar esta función con un número mínimo de funciones lógicas elementales Y, O, NO para facilitar su uso. Para ello se utilizan todas las operaciones consideradas a partir del No. 4 y los métodos de Quine y Veitch.
El método de Quine le permite encontrar la forma disyuntiva normal más simple de una expresión lógica, es decir, escriba una expresión lógica en forma de disyunción o conjunción, mientras que el signo de inversión puede aparecer solo en un argumento o no aparecer en absoluto. El algoritmo se proporciona en literatura especializada.
Método Veitch (mapas de Karnaugh)
En este método, para representar una función de n variables, se dibuja una tabla especial que contiene 2n celdas. Cada celda corresponde a uno de los conjuntos de n variables. La celda registra el valor aceptado por la función para este conjunto de argumentos. Todas las celdas correspondientes a conjuntos que contienen alguna variable sin el signo de inversión forman un área de 2 n -1 celdas. Esta zona se llama área de una variable dada(por ejemplo, el alcance de la variable x). Las celdas restantes forman la región de esta variable inversa. Los posibles conjuntos de argumentos se distribuyen entre las celdas de tal manera que los límites de las áreas de todas las variables y sus inversiones sean claros, y la pertenencia de cualquier celda a un área particular se identifique visualmente fácilmente.
1) Función de una variable:
2) Función de dos variables:
3) Diagrama de disyunción:
4) Diagrama de conjunción:
5) Por tres argumentos:
6) Por cuatro argumentos:
Puede minimizar una expresión booleana determinada agrupando parado cerca unidades y al mismo tiempo excluir la variable que pasa del estado directo al inverso. Puede combinar no solo vertical y horizontalmente, sino también a lo largo de los bordes, ya que en caso general El mapa de Carnot forma un toroide. Ejemplo:
b) 
Hay dos direcciones para la minimización:
- Ш La forma más corta de notación (el objetivo es minimizar el rango de cada término);
- Ш Obtención de la forma mínima de grabación (el objetivo es obtener el número mínimo de caracteres para escribir la función completa de una vez).
- 1. Método de transformaciones equivalentes
El método de minimizar funciones booleanas mediante transformaciones equivalentes se basa en el uso coherente de las leyes del álgebra booleana. Es aconsejable utilizar el método de transformaciones equivalentes sólo para funciones simples y para el número de variables lógicas no más de 4. En más variables y función compleja aumenta la probabilidad de errores durante la conversión.
2. El método de Quine.
Al minimizar utilizando el método de Quine, se supone que la función lógica a minimizar se proporciona en forma de SDNF. Aquí se utiliza la ley del enlace incompleto. La minimización se lleva a cabo en dos etapas: encontrar implicantes simples, colocar etiquetas y determinar implicantes esenciales.
Los términos no etiquetados se denominan implicantes primos. La expresión lógica resultante no siempre es mínima, por lo que se explora la posibilidad de una mayor simplificación.
Para hacer esto:
- Ш Se compilan tablas, en cuyas filas se escriben los implicantes primarios encontrados, y en las columnas se indican los términos del FAL primario.
- Ш Las celdas de esta tabla están marcadas si el implicante primario es parte de algún término primario.
- Ш El problema de simplificación se reduce a encontrar el número mínimo de implicantes que cubran todas las columnas.
Algoritmo del método Quine (pasos):
- 1. Encontrar los implicantes principales (los términos originales de DNF están escritos en una columna y pegados de arriba a abajo, los implicantes sin etiquetar entran en funciones en este paso).
- 2. Organizar etiquetas de redundancia (se compila una tabla en la que las filas son los implicantes principales, las columnas son los términos originales, si algún término mínimo contiene un implicante principal, entonces colocamos una etiqueta en la intersección de la fila y la columna) .
- 3. Encontrar implicantes esenciales (si solo hay una etiqueta en cualquier columna, entonces el implicante principal de la fila correspondiente es esencial).
- 4. Se tacha la fila que contiene el implicante esencial y las columnas correspondientes (si, como resultado de eliminar las columnas, aparecen filas de implicantes primarios que no contienen etiquetas o contienen etiquetas idénticas en las filas, entonces se tachan dichos implicantes primarios y en este último caso queda uno de menor rango).
- 5. Seleccionar la cobertura mínima (de la tabla obtenida en el paso 3, seleccione un conjunto de implicantes primarios que incluya etiquetas en todas las columnas con al menos una etiqueta en cada una, con varias opciones posibles se da preferencia a la cobertura con el número total mínimo de elementos en los implicantes que forman la cobertura).
- 6. El resultado se escribe como una función.
Sea la función dada:
Para facilitar la presentación, marquemos cada componente de la unidad de la función F SDNF con algún número decimal (arbitrariamente). Realizamos pegado. El constituyente 1 está pegado sólo con el constituyente 2 (por la variable x3) y con el constituyente 3 (por la variable x2) del constituyente 2 con el constituyente 4, etc. Como resultado, obtenemos:
Tenga en cuenta que el resultado del pegado es siempre un producto elemental, que es parte común componentes pegados.
con apariencia de la misma obra elemental. Ya no es posible pegar más. Habiendo realizado absorciones (del DNF resultante eliminamos todos los productos elementales absorbidos), obtenemos un DNF reducido:
Pasemos a siguiente etapa. Para obtener un DNF mínimo, es necesario eliminar todos los implicantes primos innecesarios del DNF reducido. Esto se hace utilizando una matriz implicante especial de Quine. Las filas de dicha matriz están marcadas por implicantes primos. función booleana, es decir, miembros del DNF abreviado, y las columnas son constituyentes de la unidad, es decir, miembros del SDNF de la función booleana.
La matriz implicante tiene la forma ver tabla. 1.1
Tabla 1.1 Matriz implicante
Como ya se señaló, un implicante simple absorbe algún constituyente de una unidad si es su propia parte. La celda correspondiente de la matriz de implicantes en la intersección de la fila (con el implicante simple considerado) y la columna (con el constituyente de la unidad) está marcada con una cruz (Tabla 1). Los DNF mínimos se construyen a partir de la matriz implicante de la siguiente manera:
- 1. Se buscan columnas de la matriz de implicantes que tengan una sola cruz. Los implicantes simples correspondientes a estos cruces se denominan básicos y forman el llamado núcleo de la función booleana. El kernel está necesariamente incluido en el DNF mínimo.
- 2. están siendo considerados varias opciones seleccionar un conjunto de implicantes simples que cubrirán las columnas restantes de la matriz de implicantes con cruces, y seleccionar opciones con el número total mínimo de letras en dicho conjunto de implicantes.
Por lo tanto la función queda así:
3. Método Quine-McCluskey.
El método es el método de Quine formalizado en la etapa de encontrar implicantes simples. La formalización se realiza de la siguiente manera:
- 1. Todos los componentes unitarios del SDNF de la función booleana F se escriben mediante sus números binarios.
- 2. Todos los números se dividen en grupos disjuntos. Signo de la formación del i-ésimo grupo: i unidades en cada número binario son constituyentes de uno.
- 3. El pegado se realiza únicamente entre varios grupos adyacentes. Los números que se pegan están marcados con algún tipo de signo (tachado, asterisco, etc.).
- 4. Se realizan todo tipo de pegados, como en el método Quine. Los números que no están marcados después de pegar son implicantes simples.
Formamos grupos de números binarios. Un signo de la formación del i-ésimo grupo son i unidades en el número binario de la unidad constituyente (Tabla 1.2).
Tabla 1.2 Grupos de números binarios
Peguemos números de grupos vecinos de la mesa. 1.3 Sólo se pueden fusionar números que tengan guiones en las mismas posiciones. Marquemos los números que se están pegando. Introduciremos los resultados del pegado en la tabla. 1.4.
Tabla 1.4 Resultados de vinculación 2
Según la tabla 5. Determinamos el conjunto de implicantes simples - 0--1 y 111-, correspondientes al DNF mínimo. Para restaurar la forma literal de un implicante simple, basta con anotar los productos de aquellas variables que corresponden a los dígitos binarios restantes:
Dividir los componentes en grupos le permite reducir el número de comparaciones por pares al pegar.
4. Método del diagrama de Veitch.
El método le permite obtener rápidamente DNF mínimos de una función booleana f pequeño número variables. El método se basa en especificar funciones booleanas mediante diagramas de algún tipo especial, llamados diagramas de Veitch. Para una función booleana de dos variables, el diagrama de Veitch se parece a (Figura 1).
Fig.1.
Cada celda del diagrama corresponde a un conjunto de variables de función booleana en su tabla de verdad. En (Fig. 1) se muestra esta correspondencia; una celda en el diagrama de Veitch se marca con uno si la función booleana toma un valor unitario en el conjunto correspondiente. Valores nulos Las funciones booleanas no están incluidas en el diagrama de Veitch. Para una función booleana de tres variables, el diagrama de Veitch tiene siguiente vista(Figura 2).
Fig.2.
Al agregarle la misma tabla se obtiene un diagrama para una función de 4 variables (Fig. 3).
Fig.3.
De la misma manera, es decir, agregando otro diagrama de 3 variables al que acabamos de considerar, se puede obtener un diagrama para una función de 5 variables, etc., pero rara vez se utilizan diagramas para funciones con más de 4 variables.
5. Mapas de Carnot.
El método del mapa de Karnaugh es uno de los métodos gráficos minimizando la función. Estos métodos se basan en el uso de características de la percepción visual, ya que con su ayuda se pueden reconocer casi instantáneamente ciertas configuraciones simples.
Construyamos una tabla para el método del mapa de Karnaugh (Tabla 1.6).
Tabla 1.6 Mapas de Carnot
Ahora contemos la totalidad de todos los cruces con etiquetas con un número mínimo de cruces. En nuestro caso, habrá 5 cruces de este tipo: tres de cuatro celdas y dos de dos celdas. Estos cruces corresponden a los siguientes implicantes simples:
para el primero - X 3 X 4;
para el segundo - X 1 X 3;
para el tercero - X 2 X 3;
para el cuarto - X 1 X 2 X 4;
para el quinto - X 1 X 2 X 4;
Un DNF mínimo se vería así:
6. Método coeficientes inciertos.
Este método se puede utilizar para cualquier número de argumentos. Pero como este método es bastante engorroso, se utiliza sólo en los casos en que el número de argumentos no supera los 5-6.
El método de coeficientes indefinidos utiliza las leyes de los conjuntos universales y nulos y las leyes de la repetición. Al principio, todos los coeficientes son inciertos (de ahí el nombre del método).
Construyamos una matriz de coeficientes inciertos para cuatro argumentos. En este caso tendremos un sistema de 16 ecuaciones.
Igualemos todos los coeficientes a 0 en aquellas filas que corresponden a 0 en la columna del vector. Luego igualamos los coeficientes correspondientes en otras filas a 0. Después de estas transformaciones, el sistema tomará la siguiente forma (Fig.4):
Fig.4.
Ahora, en cada línea debe seleccionar el coeficiente del rango mínimo y equipararlo a uno, y los coeficientes restantes a 0. Después de eso, tache líneas idénticas, dejando uno de ellos (también se tachan aquellas líneas para las que todos los coeficientes son iguales a 0).
Anotemos ahora las conjunciones correspondientes a los coeficientes, igual a unidades. Obtendremos el DNF mínimo.
Métodos de búsqueda de mínimos de funciones. La búsqueda de máximos se reduce a la búsqueda de mínimos cambiando el signo de la función. M.f. m es una rama de las matemáticas computacionales que juega un papel importante en aplicaciones como la selección óptima. Opciones en planificación, diseño e investigación de operaciones, tareas de gestión. procesos tecnológicos, control de movimiento objetos complejos etc. m también se utilizan para resolver sistemas de ecuaciones y desigualdades al encontrar el espectro de operadores, al resolver problemas de valores en la frontera, etc.
Los más estudiados son M. f. m - en relación con funciones definidas en todo el espacio euclidiano de dimensiones completas. Considerémoslos sin tocar los problemas de minimización discretos y discretos-continuos, así como los problemas de minimización en presencia de restricciones. Esto último en muchos casos puede reducirse al problema de la minimización incondicional (por ejemplo, utilizando funciones de penalización). No consideraremos métodos para encontrar el mínimo basado en el uso directo. condiciones necesarias extremo, ya que la solución de los sistemas resultantes de ecuaciones no lineales puede considerarse como el problema de minimizar la suma de residuos al cuadrado (o el módulo máximo de residuos). Posibilidad de aplicación y efectividad comparativa de varios M. f. m. está determinado en gran medida por la clase de funciones a las que se aplican. La mayoría de M. f. m permiten encontrar un mínimo local, y solo la información a priori sobre las propiedades de la función (convexidad, unimodalidad) nos permite considerar este mínimo global. Métodos que garantizan la búsqueda de un mínimo global con una precisión dada para un tiempo suficientemente clases generales Las funciones requieren mucha mano de obra. En
En la práctica, para encontrar el mínimo global se utiliza principalmente una combinación del método de Monte Carlo y uno de los métodos de minimización local.
Clase amplia M. f. m. se describe mediante el siguiente esquema computacional. Definamos la función a minimizar en un punto de partida elegido arbitrariamente. Supongamos que tiene derivadas parciales continuas hasta el orden inclusive, la consideraremos como una derivada de orden cero). para recibir aproximaciones sucesivas al mínimo local, se construye una secuencia de puntos de la siguiente forma:
donde denota el vector de derivadas parciales del orden de las funciones computables de sus argumentos. Se llama el orden de las derivadas parciales superiores calculadas para implementar la fórmula (1). orden del método. Básico Un grupo de métodos utilizados en la práctica tiene la particularidad de que la información necesaria para calcular el siguiente valor se expresa a través de un número limitado de parámetros calculados sobre este paso Y pasos previos proceso. El método se llama -paso si el esquema del algoritmo tiene, a partir de algunos, la siguiente estructura: en un paso calculamos los parámetros donde - algunos número natural, y un vector en términos de la siguiente forma:
(Los parámetros iniciales se calculan mediante procedimientos especiales). En los métodos de descenso ampliamente utilizados, el operador se especifica de la siguiente forma:
Dónde numero real, que se llama multiplicador de pasos, el vector determina la dirección de descenso. Entre los métodos de descenso destacan los métodos de descenso monótonos o métodos de relajación. El método es la relajación, si en k Beli es continuamente diferenciable, entonces la relajación del método (3) está asegurada cuando se forma la dirección de descenso ángulo agudo con la dirección del gradiente y es bastante pequeño. La teoría general de los procesos de relajación está más desarrollada para el caso de funciones convexas. como base parámetros que caracterizan el proceso, se consideran los ángulos de relajación entre ellos y la dirección del gradiente), así como los factores de relajación determinados por la igualdad
¿Dónde está el gradiente de la función (para una función cuadrática con el descenso más pronunciado)? Denotemos por el coeficiente reducido. relajación. Necesario y condición suficiente convergencia del proceso de relajación para una función fuertemente convexa:
Entre los métodos de relajación, los más famosos son los métodos de gradiente. Echemos un vistazo más de cerca a los métodos de gradiente de una sola etapa. Esquema general son los siguientes:
Dentro de este esquema se pueden distinguir las siguientes modificaciones:
A) descenso de gradiente con paso constante: matriz identidad;
b) descenso de pendiente más rápido: , donde se determina a partir de la condición mínima
c) Método de Newton-Raphson: , ¿dónde está el hessiano en el punto
d) circuitos intermedios: . Los métodos de gradiente de dos etapas más comunes incluyen métodos de gradiente conjugado; Un ejemplo de un esquema de dos etapas es el método del gradiente conjugado de Fletcher-Reeves:
Métodos a) y b) con suficiente condiciones generales(el primero, para una a suficientemente pequeña) converge a un mínimo local con una velocidad geom. progresión. El método c) en condiciones suficientemente generales converge desde una vecindad suficientemente pequeña del mínimo con una velocidad cuadrática. El esquema intermedio d) es más flexible y permite, con un cierto ajuste de las secuencias, obtener también una tasa de convergencia cuadrática a mayor requisitos débiles al planteamiento inicial.
La desventaja de los métodos c), d) es la necesidad de calcular el hessiano. Los métodos de gradiente conjugado y los llamados algoritmos de métrica variable, que tienen las propiedades de convergencia acelerada para funciones suficientemente suaves en las proximidades de un mínimo, están libres de este inconveniente. Los esquemas de algoritmos de métrica variable son, por naturaleza, una combinación del esquema de gradiente conjugado y el método de Newton-Raphson. Simultáneamente con el movimiento según un esquema como el de gradientes conjugados, se produce una aproximación iterativa de la matriz, que es la inversa de la hessiana en el punto mínimo. Después de cada n pasos del proceso hay un paso según el método de Newton-Raphson, donde en su lugar tiene lugar su aproximación.
Si el gradiente se rompe, los métodos anteriores no se aplican. Es por eso gran valor tener métodos para minimizar funciones convexas (no necesariamente diferenciables); Estos métodos se pueden dividir en 2 grupos: 1) métodos de tipo gradiente y 2) métodos de “plano de corte”. El grupo 1 incluye varias modificaciones del método del gradiente generalizado, así como esquemas con convergencia acelerada basados en estiramiento espacial. en la dirección del gradiente o de la diferencia de dos gradientes sucesivos. Los métodos del segundo grupo incluyen, por ejemplo, el método Kelly. Sea ZP un conjunto convexo (acotado) en el que se define una secuencia de puntos en los que se calcula el gradiente generalizado. Luego se encuentra como solución al problema: encontrar
El método de Kelly converge en el funcional para cualquier inicial. De los métodos de minimización habituales, cabe destacar, en particular, el método del barranco para minimizar funciones con hipersuperficies de nivel muy alargadas; coordinar métodos de búsqueda sistema de variables coordenadas; métodos de búsqueda aleatorios; métodos combinados de descenso rápido y búsqueda aleatoria, cuando la dirección de la función decreciente está determinada por el método de Monte Carlo; métodos de descenso diferencial, métodos de aproximación estocástica, etc. En problemas óptimos. de regulación, los métodos de búsqueda de orden cero son de gran importancia. Los algoritmos de minimización para este caso generalmente se basan en la idea de una aproximación lineal o cuadrática de la función que se minimiza o una aproximación en diferencias de las derivadas parciales correspondientes. Se han propuesto varios métodos para buscar el extremo global. Básico de los cuales: método Monte Carlo, una combinación del método Monte Carlo para determinar el punto de partida con uno de los algoritmos búsqueda local, métodos basados en la construcción de la envoltura inferior de una función dada, métodos de corte secuencial de subconjuntos, métodos de construcción de trayectorias que cubren densamente el dominio de definición de la función en todas partes y minimización a lo largo de estas trayectorias.
para resolver especial clases de problemas multiextremos, se utilizan métodos de programación dinámica.
Hoy en día se crean tiempos óptimos. Algoritmos para minimizar funciones de diferentes clases. Sea una clase de funciones definidas en el cubo y que tienen derivadas parciales hasta el orden s, que satisfacen la condición de Lipschitz con L constante. Cualquier algoritmo de minimización de , utilizando información sobre los valores de f y sus derivadas hasta el orden inclusive en no más de N puntos es equivalente (en el sentido del resultado) a algún algoritmo A para obtener una secuencia de iteraciones (1) y aproximar el valor deseado usando la operación final
¿Dónde hay alguna función computable? Introduzcamos la siguiente notación:
El algoritmo para el cual se logra el óptimo. Las condiciones significan optimización asintótica y optimización de orden del algoritmo, respectivamente. Se puede demostrar que.
Además, la elección de , afecta sólo a la constante en la estimación especificada. En un caso particular tenemos:
donde esta min. red en .
Otro enfoque para la construcción óptima. Los algoritmos de minimización están asociados con la generalización de ideas para soluciones estadísticas secuenciales. El algoritmo de minimización se considera como una secuencia controlada de experimentos, cada uno de los cuales da un resultado particular. Se determina una medida de probabilidad a priori en función del conjunto de resultados. Después de obtener un resultado específico del siguiente experimento, las probabilidades se redistribuyen según la fórmula de Bayes y se selecciona el siguiente experimento o se toma la decisión final. Los algoritmos se diferencian entre sí en la regla mediante la cual se selecciona el siguiente experimento, las reglas para detenerlo y elegir la solución final. La calidad de la solución está determinada por la función de pérdida, que se promedia de acuerdo con el resultado obtenido en en esta etapa distribución de probabilidad. En estos términos se plantea el problema de elegir el óptimo. Algoritmo como construcción de una regla bayesiana secuencial para encontrar soluciones. Esta formulación es interesante porque en su marco es posible tener en cuenta las propiedades estadísticas de la clase de problemas que se resuelven y comparar las pérdidas "promedio" asociadas con el error de la solución con los costos asociados con el refinamiento de la solución. Iluminado.: Lyubich Yu., Maistrovsky G. D. teoría general Procesos de relajación para funcionales convexos. “Avances en las Ciencias Matemáticas”, 1970, vol 25, siglo. 1; Mikhalevich V. S. Algoritmos de optimización secuencial y su aplicación. "Cibernética", 1965, N5 1-2; Ivanov V.V.Acerca de algoritmos optimos minimizando las funciones de algunas clases. "Cibernética", 1972, núm. 4; Salvaje D. Dk. Métodos para buscar el extremo. Por. del ingles M., 1967.
V. V. Ivanov, V. S. Mikhalevich, N. Z. Shor.
8.3. Métodos analíticos para minimizar las funciones de conmutación.
El método de Quine..
El método se basa en la comparación por pares y en la unión, si es posible, de todos los constituyentes (miembros del SDNF). Para ello, se compara cada constituyente con los siguientes, lo que conduce a la obtención de un implicante. Los implicantes resultantes se comparan nuevamente y, si es posible, se pegan entre sí, etc. hasta que los implicantes restantes ya no puedan unirse. Estos son implicantes simples; su disyunción es un DNF abreviado.
Para ordenar, es aconsejable dividir los constituyentes en grupos según el número de variables no invertidas. En este caso, cada constituyente sucesivo, comenzando desde arriba, se compara sólo con los constituyentes del grupo adyacente debajo, con el número de variables no invertidas uno más.
Sea una función de conmutación definida por SDNF:
Dividamos los constituyentes en grupos según el número de variables no invertidas.
El número romano del número de grupo corresponde al número de variables no inversas. Dibujemos líneas que indiquen los componentes que se van a pegar. El resultado del pegado es siempre una conjunción elemental, que es una parte común de las conjunciones originales (en particular, un constituyente).
Los implicantes resultantes también permiten pegarlos, y el resultado es el mismo implicante. 
.
Es imposible seguir pegando, por lo que los implicantes resultantes son simples y el DNF abreviado tiene la forma:
Se completa la primera etapa. En la segunda etapa, es necesario eliminar los implicantes primos innecesarios. Esto se hace utilizando una mesa de implicantes de Quine especial (mesa de cobertura). Las filas de la tabla están marcadas con implicantes simples de la función de conmutación, es decir miembros del DNF abreviado, y las columnas son constituyentes de la unidad, es decir miembros de la función de conmutación SDNF.
Como ya se señaló, un implicante simple absorbe algún constituyente de una unidad si es su propia parte. La celda correspondiente de la tabla de implicantes en la intersección de la fila de un implicante simple dado y las columnas con los constituyentes de la unidad está marcada, por ejemplo, con un signo "+". Los DNF mínimos se construyen utilizando la tabla de implicantes de la siguiente manera:
1) se buscan las columnas de la tabla de implicantes que tienen una sola cruz; los implicantes simples correspondientes a estas cruces se denominan básicos y forman el llamado núcleo de la función de conmutación. El núcleo está necesariamente incluido en el DNF mínimo;
2) se consideran varias opciones para elegir un conjunto de implicantes simples que cubrirán con cruces las columnas restantes de la matriz de implicantes, y se seleccionan opciones con el número total mínimo de letras.
El núcleo de nuestra función (Tabla 35) son los implicantes 
y x 1 x 2 x 3, es decir la función tiene un punto muerto único y un DNF mínimo:
Tabla 35
Tabla de implicantes de Quine
|
Electores 1 (miembros del SDNF) |
|||||||
|
implicantes |
|
|
|
|
|
|
|
|
| |||||||
Se puede ver que el implicante x 2 x 3 x 4 es redundante, ya que cubre constituyentes ya cubiertos por implicantes 
, x 1 x 2 x 3 .
El número de cruces en una línea es una potencia de 2; Además, puedes asegurarte de que sea igual a N=2 n - k, donde k es el número de letras de un implicante simple, n es el número de variables de las que depende la función.
Si el SDNF no se especifica al principio, entonces debe obtenerse utilizando, por ejemplo, métodos que ya conocemos.
Está claro que para tablas de implicantes grandes es difícil identificar visualmente opciones con un número mínimo de letras. Por lo tanto, se utiliza el método de Petrik, que permite obtener todos los DNF sin salida de una tabla de implicantes mediante la construcción de su denominada representación conjuntiva. Para hacer esto, todos los implicantes simples se denotan con letras diferentes (A, B, C en la Tabla 35), y luego, para cada columna, se construye una disyunción de todas las letras que denotan filas de la tabla, cuya intersección con una columna determinada es marcado con una cruz. La representación conjuntiva de la matriz implicante se forma como una conjunción de las disyunciones construidas para todas las columnas. Todas las relaciones del álgebra de Boole de funciones de conmutación se pueden aplicar a la representación conjuntiva de la tabla de implicantes para simplificarla. Después de abrir los paréntesis y realizar todas las absorciones posibles, obtenemos una disyunción de conjunciones, cada una de las cuales contiene todos los implicantes del callejón sin salida DNF.
Esto significa que un DNF sin salida contiene dos implicantes principales ( 
y al mismo tiempo C=x 1 x 2 x 3) y tiene la forma:
Método de Quine-McCluskey.
El método es una formalización del método de Quine, orientado al uso de ordenadores. La formalización consiste en registrar los constituyentes de la unidad (miembros del SDNF) con sus números binarios. Todos los números se dividen en grupos disjuntos según el número de unos en el número binario. Los enlaces se realizan sólo entre grupos adyacentes. La categoría a eliminar se indica con el signo “–” (“guión”). A partir de los implicantes resultantes se forman otros grupos teniendo en cuenta la misma ubicación del guión. Esta designación de implicantes se denomina códigos generalizados. Sea dada una función lógica
111101001000110.
Agrupemos estos constituyentes de una unidad por el número de unidades:
Ya no es posible pegar más. Los DNF mínimos se encuentran luego usando la tabla de implicantes (Tabla 36):
Esto significa que los DNF sin salida contienen tres implicantes principales y tienen la forma:
(dos inversiones);
(tres inversiones).
Tabla 36
Tabla de implicantes de Quine-McCluskey
|
implicantes |
Componentes de unidades |
|||||||
Tenga en cuenta que pegar dos implicantes con un guión sólo es posible si están colocados apropiadamente, por ejemplo:
|
|
|
|
|
Puede elegir cualquiera de los TDNF obtenidos y, teniendo en cuenta el menor número de inversiones, la primera.
Método de Blake-Poretsky.
El método permite obtener un DNF reducido de una función booleana a partir de su DNF arbitrario, y no del SDNF, como en los métodos de Quine y Quine-McCluskey, utilizando la ley de pegado generalizado. El método se basa en la siguiente afirmación: si en un DNF arbitrario de una función booleana se realizan todas las operaciones posibles inversas al pegado generalizado y luego se realizan todas las absorciones, entonces el resultado es un DNF reducido de la función.
Sea la función DNF:
Se puede observar que la ley de pegado generalizado con respecto a la variable x 1 se puede aplicar a la primera y segunda conjunciones; obtenemos:
Lo mismo para la primera y tercera conjunciones:
aquellos. ¡Todo sigue como está!
La segunda y tercera conjunciones admiten un pegado generalizado a lo largo de x2:
Pasemos al DNF:
Luego de aplicar la ley de idempotencia (repetición) y absorción obtenemos:
Los intentos de seguir utilizando la unión y la absorción generalizadas no dan resultados. En consecuencia, se obtiene una función DNF reducida.
Tabla 37
Tabla implicante para ilustrar el método de Blake-Poretsky
|
implicantes |
Conjuntos de funciones y sus significados |
|||||||||
Por lo tanto, los conjuntos de trabajo (unitarios) pueden estar cubiertos por tres implicantes principales, p. 
,
,
. El núcleo incluye implicantes. 
,
. Entonces los DNF de punto muerto tienen la forma:
(mejor en términos del número de inversiones).
