Source: http://docplayer.es/1061419-Razonamiento-con-restricciones-esquema-global-tutorial-iberamia-2002-1-introduccion-definiciones-ejemplos.html
Timestamp: 2017-07-27 02:42:39+00:00

Document:
Razonamiento. con. Restricciones. Esquema Global. Tutorial IBERAMIA Introducción - Definiciones - Ejemplos - PDF
Razonamiento. con. Restricciones. Esquema Global. Tutorial IBERAMIA Introducción - Definiciones - Ejemplos
Download "Razonamiento. con. Restricciones. Esquema Global. Tutorial IBERAMIA 2002. 1. Introducción - Definiciones - Ejemplos"
Emilio Montero Maidana
1 Esquema Global Razonamiento con Restricciones Tutorial IBERAMIA 2002 Javier Larrosa Dep. LSI, UPC, Barcelona Pedro Meseguer IIIA, CSIC, Bellaterra 1. Introducción - Definiciones - Ejemplos 2. Métodos de Resolución - Búsqueda - Inferencia - Métodos híbridos 3. Modelización - Primal / dual - Restricciones globales - Programación con restricciones 4. Restricciones Blandas - Modelos - Algoritmos2 Esquema Satisfacción de Restricciones Introducción Definiciones Ejemplos Metodos de resolución Búsqueda: Generar y testear Backtracking Backjumping Inferencia Consistencia de arcos Consistencia de caminos incompleta K-consistencia Problemas libres de backtracking completa Consistencia adaptativa Definición: CSP o constraint satisfaction problem, definido por una terna (X, D, C ) X = {,,..., X n } variables D = { D 1, D 2,..., D n } dominios C = { C 1, C 2,..., C r } Dada una restricción C i, var(c i ) = {X i1,..., X ik } rel(c i ) D i1 D i2... D ik Solución: restricciones relaciona k variables (restricción k-aria) tuplas de valores permitidos asignación de valores a variables satisfaciendo todas las restricciones Algoritmos híbridos Forward Checking Really Full Lookahead Maintaining Arc Consistency Heurísticas Complejidad: - NP-completo - algoritmos de coste exponencial (caso peor)3 Interés de los CSP Car sequencing problem Relevancia: Problemas reales como CSPs: Car sequencing problem Asignación de recursos (scheduling) Diseño de bloques (BIBDs) Para la IA: Restricciones: formal general de representación del conocimiento Satisfacción de restricciones: razonamiento automático Ejemplos: Especialización:» SAT» razonamiento temporal» razonamiento basado en modelos tipo de dominios: discretos / continuos finitos / infinitos tipo de restricciones: binarias / n-arias Cadena de montaje de coches FAROS ANTINIEBLA X X TECHO SOLAR X X X CLIMATIZADOR X X Area techo solar Capacidad 3/5 Area climatizador Capacidad 2/3 Formulación: variables: n coches a producir dominios: modelos de coche restricciones: capacidad de las áreas Características: CSP no binario, discreto y finito4 Asignación de recursos Job-shop scheduling n jobs, cada uno con m operaciones, m recursos, cada operación necesita un recurso de forma exclusiva durante un tiempo precedencia entre las operaciones de cada job, Se pueden realizar los n jobs en tiempo D? R2 R1 R3 A1 A2 A3 R1 R2 R3 0 B1 B2 B3 D R1 R3 R2 C1 C2 C3 tiempo Formulación: variables: operaciones dominios: tiempos de inicio de cada operacion restricciones: precedencia entre las operaciones de un job exclusividad de cada recurso en el tiempo Características: CSP binario, discreto y finito (acotado por D) CSP binario: Restricciones binarias {,,..., X n } variables { D 1, D 2,..., D n } dominios discretos y finitos { R ij } restricciones binarias var(r ij ) = {X i, X j } rel(r ij ) = {valores permitidos para X i y X j } R ij simétrica Solución: asignación de valores a variables satisfaciendo todas las restricciones. Generalidad: todo problema n-ario se puede formular como un problema binario [Rossi et al, 90] Ejemplos: Coloreado de grafos Satisfacibilidad booleana (SAT) N-reinas, crucigramas, criptoaritmética5 N-reinas Definición: posicionar n reinas en un tablero de ajedrez n n, de forma que no se ataquen. Coloreado de grafos Definición: Dado un grafo, n nodos m colores, asignar un color a cada nodo de forma que no haya dos nodos adyacentes con el mismo color. n = 5 Colores Formulación: 1 reina por fila variables: reinas, X i reina en la fila i-ésima dominios: columnas posibles {1, 2,..., n} restricciones: no colocar dos reinas en la misma columna la misma diagonal rel(r ij )= {(a,b) a b i -j a -b } Características: CSP binario, discreto y finito existe un método de solución constructivo Formulación: variables: nodos dominios: colores posibles restricciones: nodos adyacentes Características: CSP binario, discreto y finito6 Generación de crucigramas Definición: Dada una rejilla y un diccionario, construir un crucigrama legal. C O L O Z Formulación: variables: grupo de casillas para una palabra (slots) dominios: palabras del diccionario con la longitud adecuada restricciones: misma letra en la intersección de dos palabras Características: CSP binario, discreto y finito (dominios grandes) 4 palabras de 1 letra 4 palabras de 3 letras 2 palabras de 5 letras Restricciones temporales Definición: dado un conjunto de sucesos que ocurren en intervalos temporales con ciertas relaciones, encontrar una asignación temporal consistente. [30, 40] [10, 20] [60, ) [60, 70] X 4 [10, 20] [20, 30][40, 50] X 5 Formulación: variables: sucesos dominios: intervalo temporal para cada suceso restricciones: distancia temporal permitida entre sucesos; relaciones temporales antes, después, solapado, etc. Características: CSP binario, contínuo e infinito7 Grafo de restricciones Grafo de restricciones: { X i } nodos { D i } dominios en los nodos { R ij } arcos etiquetados Coloreado de mapas 4-reinas X 4 azul, rojo azul, rojo, verde azul azul, verde azul, rojo, verde azul, rojo azul azul, verde X 4 1,2,3,4 1,2,3,4 1,2,3,4 1,2,3,4 X 4 Introducción Definiciones Ejemplos Esquema Metodos de resolución Búsqueda: Generar y testear Backtracking Backjumping Inferencia Consistencia de arcos Consistencia de caminos K-consistencia Problemas libres de backtracking Consistencia adaptativa Algoritmos híbridos Forward Checking Really Full Lookahead Maintaining Arc Consistency Heurísticas incompleta completa8 Generar y testear Algoritmo: generación y test de todas las asigaciones totales posibles. 1. Generar una asignación total. 2. Comprobar si es solución. Si es, stop, sino ir a 1 Búsqueda con backtracking Estrategia: Construir una solución parcial : asignación parcial que satisface las restricciones de las variables involucradas. Ejemplo: 4-reinas Extender la solución parcial, incluyendo una variable cada vez hasta una solución total.... Eficiencia: es muy poco eficiente genera muchas asignaciones que violan la misma restricción Si no se puede extender backtracking - cronológico: se elimina la última decisión - no cronológico: se elimina una decisión anterior Tipos de variables: pasadas solución parcial, tienen valor asignado futuras solución parcial, no tienen valor asignado actual, variable en curso Tipos de restricciones: C P restricciones entre pasadas C PF restricciones entre pasadas y futuras C F C X restricciones entre futuras restricciones que involucran var X9 Árbol de búsqueda Espacio de estados: representable por un árbol raíz: asignación vacía a cada nivel asociamos una variable sucesores de un nodo: todos los valores de la variable asociada a ese nivel 4 variables / 4 valores Recorrido del árbol de búsqueda Recorrido primero en profundidad: preorden en cada nivel se asigna una nueva variable variable actual variables pasadas (asignadas), P futuras (sin asignar), F pasadas futuras X X asignacion total asignacion parcial visitada nodo actual por visitar Arbol de búsqueda: contiene todos los estados recorrido exhaustivo método completo Si nodo actual (P) inconsistente: subárbol sucesor no contiene soluciones no se visita se poda ventaja con respecto a generar y testear10 Backtracking BT = DFS + consistencia(p) DFS: búsqueda primero en profundidad consistencia(p): Si P es consistente, continua sino, backtracking consistencia(p): es suficiente con comprobar que actual es consistente con variables anteriores BT recursivo funcion bt(x variable): booleano para todo a D(x) hacer x a si test(x,pasadas) pasadas pasadas + {x} si bt(siguiente(x)) retorna CIERTO sino pasadas pasadas - {x} retorna FALSO funcion test(x variable,p conjunto):booleano pasadas para todo y P hacer si (val(x),val(y)) rel(r xy ) retorna FALSO retorna CIERTO futuras nodos inconsistentes nodo actual11 Problemas del backtracking Backtracking cronológico Visión local: la variable actual sólo se compara con las variables pasadas Situación: (1, a) incompatible con (n, _) X 4 a b X 5 X 6 X 7... X 8 X n Arbol de búsqueda: BT: recorrerá el subárbol {,..., X n } (1/m del árbol total) para darse cuenta de que a no esta en la solución. Alternativas: detectar que a es incompatible con D n -- antes de la búsqueda -- al asignar a backtracking no cronológico: X 4 X 5 X BT: enumera exhaustivamente todas las asignaciones parciales consistentes -- saltar directamente de X n a12 Backjumping Backjumping dirigido por conflictos Conjunto conflicto de X j : - var pasadas incompatibles con algun valor de X j X 4 X 5 X 6 X 7 X 8 bloqueo Observación: - cambiar el valor de X 5 no elimina el bloqueo - backtracking sobre una variable anterior: X 4 X 4 X 5 X 6 X 7 X {} {1} {1, 2} {1} {1, 2, 4} conjunto conflicto {1, 2, 3, 4} 1 Proceso : - backjumping (X j ) = max conjunto conflicto(x j ) X 4 X 5 X Backjumping: - salta a una variable responsable del bloqueo - no enumera aquellas asignaciones parciales que no conducen a ninguna solución,,..., X i,..., X j,...,x n - tras backjump de X j a X i, conjunto conflicto (X i ) = conjunto conflicto (X i ) {conjunto conflicto (X j ) - X i } - se transpasan a X i los conflictos de X j con variables anteriores a X i13 Introducción Definiciones Ejemplos Esquema Metodos de resolución Búsqueda: Generar y testear Backtracking Backjumping Inferencia Consistencia de arcos Consistencia de caminos K-consistencia Problemas libres de backtracking Consistencia adaptativa Algoritmos híbridos Forward Checking Really Full Lookahead Maintaining Arc Consistency Heurísticas incompleta completa Propagación de restricciones Restricciones: explícitas: definición del problema implícitas: inducidas por la acción de las explícitas Propagación: hace explícitas las restricciones implícitas R X 12 :(a,b) (b,c) 2 a, b, c a, b, c R 13 : (a,c) (c,b) a, b, c R X 12 :(a,b) (b,c) 2 a, b, c a, b, c R 13 : (a,c) (c,b) a, b, c R 23 : (b,c)14 Microestructura Microestructura a a a a b b b b c c c c a b c a b c valores compatibles valores compatibles no se pueden extender a una solución global15 Reducción de problemas Consistencia de arcos Propagación: P genera un P = P + restricciones implícitas P es equivalente a P, SOL(P) = SOL(P ) P se reduce a P Total: consistencia global sintetiza una única restricción global tuplas permitidas = soluciones coste temporal exponencial Una restricción R ij es arco consistente direccional (de i a j) ssi para todo valor a D i existe b D j tal que (a, b) rel(r ij ) Una restricción R ij es arco consistente si es arco consistente direccional en los dos sentidos Un problema es arco consistente ssi todas sus restricciones lo son. Parcial: consistencia local P es más fácil de resolver que P a b c X k espacio estados P > espacio de estados P si D i = Ø, final, no hay solución X i a a X j coste polinómico preproceso antes de búsqueda con backtracking intercalado con búsqueda con backtracking b c b c16 Filtrado por consistencia de arcos Idea: si para a D i no existe b D j tal que (a, b) rel(r ij ), se puede eliminar a de D i porque a no estará en ninguna solución. Filtrado de dominios por consistencia de arcos: se eliminan los valores responsables de la arco inconsistencia. Coloreado de grafos: azul, rojo azul X 4 azul, rojo, azul, verde verde X azul, rojo 2 PUNTO FIJO azul X 4 azul, rojo, azul, verde verde AC-1: Algoritmo consistencia de arcos funcion revise (i,j variable): booleano; delete FALSO para cada a D i hacer si no hay b D j tq.(a,b) rel(r ij ) D i D i - a delete CIERTO retorna delete procedimiento AC-1 () Q {(i,j) (i,j) arcos(g), i j} /* R ij aporta dos arcos a Q (i,j) y (j,i)*/ repetir cambio FALSO para cada (i,j) Q hacer cambio revise(i,j) o cambio hasta no (cambio) /* variables globales G: grafo de restriccioens {Di}: dominios de las variables */17 AC-3: Algoritmo consistencia de arcos Consistencia de caminos a, b, c,.. X k revise(k,m) X m Un par de valores ((i, a) (j, b)), tal que (a, b) rel(r ij ), es camino consistente ssi para todo X k, i k, j k, existe c D k tal que, X p X q X r revise(k,m) borra b y c de D k Qué arcos hay que revisitar? Aquellos que han dejado de ser arco consistentes por el borrado de b y c. (a, c) rel(r ik ) y (c, b) rel(r kj ) Un par de variables (X i, X j ) es camino consistente ssi todo par de valores (a, b) rel(r ij ) es camino consistente. Un problema P es camino consistente ssi todo par de variables es camino consistente. (k,_): no, si era arco consistente, lo sigue siendo tras el borrado (_,k): si, pueden convertirse en arco inconsistentes por el borrado a b X k procedimiento AC-3 (G) Q {(i,j) (i,j) arcos(g), i j} mientras Q Ø hacer selecciona y borra un arco (k,m) de Q si revise(k,m) entonces Q:=Q {(i,k) (i,k) arcos(g),i k,i m} X i a b a b X j18 N-reinas y consistencia local N-REINAS: para N=4 es arco consistente Representación matricial R ij D i D j ; definición conjuntista X 4 Para cualquier valor de X i existe un valor de X j consistente (cada reina restringe 3 posiciones) Dominios discretos y finitos: - ordenar valores - representación matricial de la restricción N-REINAS: para N=4 es no es camino consistente X 4 No hay valor posible para 4-REINAS r ij, ab = 1 si (a, b) R ij 0 si (a, b) R ij Consistencia de caminos X 4 Soluciones: X 4 1 r 12 =19 Operaciones con restricciones Consistencia local y operadores Intersección de restricciones: Consistencia de arcos: r ii = r ii & r ij r jj r ji R ij r ii X i R ij R ij X j r ii X i r ij X j r jj R ij = R ij R ij r ij, kl = r ij, kl r ij, kl r ij = r ij & r ij - genera restricciones unitarias (filtra dominios) - se alcanza cuando r ii = r ii Composición de restricciones: Consistencia de caminos: r ij = r ij & r ik r kk r kj Rik X k R kj r kk X i R ij X j rik X k r kj r ij rel(r ij )= {(a, b) c_d k, (a, c) rel(r ik,), (c, b) rel(r kj )} X i r ij X j r ij = r ik r kj r ij, pq = t=1,.., m (r ik, pt r kj, tq ) - genera restricciones binarias - se alcanza cuando r ij = r ij20 PC-1: Algoritmo consistencia caminos procedimiento PC-1 () Y n {r ij }; repetir Y 0 Y n ; para k 1 hasta n hacer para i i hasta n hacer para j 1 hasta n hacer Y ij k Y ij k-1 & Y ik k-1 * Y kk k-1 * Y kj k-1 ; hasta Y n =Y 0 ; {r ij } Y n ; /* variables globales r ij : representaciones matriciales de las restricciones */ PC-2: Algoritmo consistencia caminos funcion revise (i,j,k variable) Z Y ij & Y ik * Y kk * Y kj si Z=Y ij retorna FALSO sino Y ij Z retorna CIERTO funcion related_paths (i,k,j variable) S a {(i,j,m) (i m n),m j} {(m,i,j) (1 m j),m i} {(j,i,m) (j<m n)} {(m,j,i) (1 m i)} S b {(p,i,m) (1 p m), (1 m n), (p=i=m), (p=m=k)} si i<j retorna S a sino retorna S b procedimiento PC-2 () Q:={(i,k,j) (i j), (i=k=j)} mientras Q Ø hacer selecciona y borra camino (i,k,j) de Q si revise(i,k,j) Q Q related_paths(i,k,j);21 K-Consistencia K-consistencia: Ejemplo K-Consistencia: - dado un subconjunto de k-1 variables asignadas {,,..., X k-1 } consistente; rojo, azul - para cualquier X k existe d D k tal que {,,..., X k } es consistente. K-Consistencia: generalización 2-consistencia: consistencia de arcos 3-consistencia: consistencia de caminos rojo rojo K= n, propagación total K-consistencia no implica K-consistencia fuerte K-Consistencia fuerte: J-consistente, para 1 J K Algoritmos para K-consistencia fuerte: Freuder 82, Cooper 89 Complejidad: O(exp K) Ejemplo: - Es 3-consistente: para cualquier par de dos variables con valores consistentes, existe un valor consistente para la tercera - No es 2-consistente: arco X2 - X122 Problemas libres de backtracking Orden de variables: {,,..., X n } Anchura de un nodo: # arcos a nodos anteriores Anchura de una ordenación: max i {anchura X i } Anchura de un grafo: min anchura ordenaciones X 4 X 4 anchura = 2 TEOREMA: Dado un orden de variables con anchura K, el problema se puede resolver sin backtracking si el nivel de consistencia fuerte es mayor que K. [Freuder 82] Algoritmos: Mínima anchura de un grafo: O(n 2 ) K-consistencia: O(exp k). Añade arcos extras, aumenta la anchura No añade arcos para anchura 1 Los árboles tienen anchura 1 Estructura de árbol = libre de backtracking, tras consistencia de arcos Consistencia Direccional Consistencia Direccional: - grafo ordenado, {,,.., X n }, - consistencia local siguiendo el orden: - consistencia de arcos direccional: de X i a X j, i < j - consistencia de caminos direccional: (X i, X j ), camino de X i, a X j siguiendo orden TEOREMA: un grafo de anchura 1 y consistencia de arcos direccional: es libre de backtracking. [Dechter y Pearl 88] Algoritmos: DAC: óptimo, O(nm 2 ), [Dechter y Pearl 88] DPC: O(n 3 m 3 ), [Dechter y Pearl 88] Grafos regulares de anchura 2: No cambian su anchura tras DPC Detección: O(n) [Arnborg 85]23 Consistencia Adaptativa Consistencia Adaptativa Consistencia adaptativa: Problema P, variable X, C X : restricciones sobre X - grafo ordenado, {,,.., X n }, - anchura de X i es w i - consistencia direccional w i + 1 en X i (consistencia adaptada a la anchura). IDEA: - Sustituir C X por c - c resume el efecto de C X sobre P - c no menciona X entonces X se puede eliminar eliminación de variable TEOREMA: un grafo ordenado con consistencia adaptativa es libre de backtracking. [Dechter y Pearl 88] PROCESO: problemas P -> P -> P ->. -> P (n-1 variables n n-1 n-2 1 Algoritmo: A-C: [Dechter y Pearl 88] O(n exp(w*+ 1)) W*: anchuraresultante Añade arcos extras, aumenta la anchura Cota superior: [Tarjan y Yannakakis 84] Calculable en O(n + e) SOLUCION: - S (n-1 solución de P (n-1 - S (n-2 solución de P (n-2 a partir de S (n S solución de P a partir de S24 Eliminación de Variable Ejemplo: 4-reinas (x 1 ) Para eliminar var X: Join todas las restricciones C x c x C x x 1 x 2 join x 1 x 2 proyecta x 1 x 2 Sustituir C x por c x x 3 x 4 x 3 x 4 x 3 x 4 Proyectar la variable x fuera c c c Sustituir c por c Si existe c var(c ) = var(c), c c c Para obtener la solución: Variables se procesan en orden inverso x c x 1 x 2 x 3 x x 1 x 2 x 3 x Se asigna a X un valor consistente con variables anteriores, y con restricciones intermedias totalmente asignadas25 Ejemplo: 4-reinas (x 2 ) Ejemplo: 4-reinas (x 3 ) join proyecta join proyecta x 1 x 2 x 1 x 2 x 1 x 2 x 1 x 2 x 1 x 2 x 1 x 2 x 3 x 4 x 3 x 4 x 3 x 4 x 3 x 4 x 3 x 4 x 3 x 4 x 2 x 3 x x 3 x x 3 x26 Ejemplo: Todas las soluciones 4-reinas Ejemplo: Todas las soluciones 4-reinas x 4 x 3 x 2 x 1 x 4 x 3 x 2 x 1 SOLUCION 1: SOLUCION 2: x x x 3 x x 2 x 3 x x 1 x 2 x 3 x x 1 x 2 x 3 x x 3 x x 2 x 3 x x 1 x 2 x 3 x x 1 x 2 x 3 x27 Esquema Algoritmos Híbridos Introducción Definiciones Ejemplos Metodos de resolución Búsqueda: Generar y testear Backtracking Backjumping Inferencia Consistencia de arcos Consistencia de caminos incompleta K-consistencia Problemas libres de backtracking completa Consistencia adaptativa Algoritmos híbridos Forward Checking Really Full Lookahead Maintaining Arc Consistency Heurísticas Combinación: búsqueda + propagación Búsqueda: BT (DFS) Propagación: en cada nodo - propaga el efecto de la asignación actual - bloqueo: rama sin soluciones - objetivo: anticipar la detección de bloqueos - si bloqueo backtracking Compromiso: nodo actual anticipa el bloqueo + evito visitar un número multiplicativo de nodos - coste de la anticipación en cada nodo28 6 reinas 6 reinas Hay solución en los descendientes de este nodo? No hay solución. Ultima variable sin valores factibles. Anticipación: eliminar columnas y diagonales prohibidas eliminar valores de dominios futuros bloqueo dominio vacío29 Esquema de anticipación Forward checking 1. Búsqueda: 1. Variable actual X i D i = {a, b, c} 2. Asignación X i a D i = {a } 2. (Consistencia entre pasadas) FC = BT + AC(C PF ) AC(C PF ) : eliminar en dominios futuros valores incompatibles con las variables pasadas 3. Tras asignar ( reducción de dominio) consistencia local parte / todo el problema nivel de consistencia si algún dominio futuro vacío bloqueo backtracking sino, se continúa la búsqueda Compromiso coste / beneficio coste, beneficio con tamaño parte localmente consistente nivel de consistencia crecimiento desigual compromiso óptimo: depende del problema en general, consistencia de arcos FC = BT + AC(C PF ) BT = DFS + consistencia(p) FC = DFS + consistencia(p) + AC(C PF ) AC(C PF ) consistencia(p) tras AC(C PF ) en dominios de F sólo hay valores consistentes con P cuando se tome una nueva variable de F, esta tendrá todos sus valores consistentes con P FC = DFS + AC(C PF )30 FC: Ejemplo Forward checking FC = DFS + AC(C PF ) P = {,,..., X i } AC(C PF ) = AC(C X1 ) + AC(C X2 ) AC(C Xi ) 4 nodos AC(C PF ) en cada nodo AC(C actual ) acumular resultados a lo largo de la rama actual: AC(C actual ) poda dominos futuros sucesores de actual heredan dominios futuros podados AC(C X1 ) valor asignado valor podado AC(C X2 ) AC(C actual ) valor usado sin éxito31 Forward checking FC = DFS + AC(C actual ) AC(C actual ): efecto lateral poda en dominios futuros backtracking: restaurar valores podados tras la asignación de la variable actual Algoritmo FC funcion FC(i variable): booleano para cada a factibles[i] hacer X i a si i=n solución retorna CIERTO sino si forward(i,a) si FC(i+1) retorna CIERTO restaurar(i) retorna FALSO restaura(x 4,2) funcion forward(i variable,a valor): booleano para toda j=i+1 hasta N hacer vacio CIERTO para cada b factibles[j] hacer si (a,b) R ij vacio FALSO sino eliminar b de factible[j] añadir b a podado[j] si vacio retorna FALSO retorna CIERTO restaura(,5) procedimiento restaura(i variable) para toda j=i+1 hasta N hacer para todo b podado[j] hacer si X i resposable filtrado b eliminar b de podado[j] anadir b a factible[j]32 Really full lookahead RFL: Ejemplo RFL = FC + AC(F) RFL = DFS + AC(C actual ) + AC(C F ) AC(C F ): poda extra en dominios futuros después de AC(C actual ) AC (2,3) RFL / FC: mayor nivel de poda: AC (3,4) coste extra: poda(rfl) poda(fc) AC(C F ) AC (2,3) adecuado para restricciones duras problemas esparsos Traza AC, 1 solo nodo33 Algoritmo RFL funcion RFL(i variable): booleano para cada a factible[i] hacer X i a si i=n retorna CIERTO sino si ac-forward(i,a) si RFL(i+1) retorna CIERTO restaura(i) funcion ac-forward(i variable,a valor): bool retorna forward(i,a) AND AC(F) funcion AC (F conjunto): booleano /* AC3 */ Q {(i,j) i,j F,(i,j) arcos(g),i j} mientras Q Ø hacer selecciona y borra un arco (k,m) de Q si revise(k,m) entonces si factibles[i]=ø retorna FALSO sino Q Q {(i,k) i,k F, (i,k) arcos(g),i k,i m} retorna CIERTO funcion revise (i,j variable): booleano delete FALSO para cada a factibles[i] hacer si no hay b factibles[j] tq.(a,b) rel(r ij ) borra a de factibles[i] delete CIERTO retorna delete C antes C despues Maintaining arc consistency restricciones antes de asignar actual restricciones después de asignar actual MAC = DFS + AC(C antes ) + AC(C despues ) MAC: en cada nodo antes de la asignación, convierte el subproblema actual en arco consistente, AC(C antes ) después de la asignación, como RLF, AC(C despues ) = AC(C actual ) + AC(C F ) MAC = DFS + AC(C antes ) + AC(C actual ) + AC(C F ) /* funcion forward procedimiento restaura como en FC */34 MAC: Ejemplo MAC: árbol de búsqueda = 1 AC( 1) Arbol de búsqueda: binario en cada nivel una variable X i dos opciones: a, a se puede cambiar de variable sin agotar los valores en cada nodo, arco consistencia del subproblema actual X i =a X i a X j =b X j b X k =c X k c X j =d X j d X i =f X i f35 Algoritmo MAC funcion MAC(i variable): booleano mientras factibles[i] Ø hacer a extrae(factibles[i]) X i a /* X i en P */ si i=n retorna CIERTO sino si ac-forward(i,a) si MAC(i+1) retorna CIERTO restaura(i) añadir a a usados[i] X i Ø /* X i en F */ si refutar(i,a) salir bucle para cada a usados[i] hacer restaura_refutar(i,a) anadir a factibles[i] retorna FALSO funcion refutar(i variable,a valor): booleano retorna AC(F) procedimiento restaura_refutar(i variable, a valor) para toda j=i+1 hasta N hacer para todo b podados[j] hacer si refutacion de (i,a) resp. filtrado b eliminar b de podados[j] añadir b a factibles[j] /* funcion ac-forward funcion AC procedimiento restaura Iguales a los de RFL */ Ordenación de variables Ordenación estática de variables: cada nivel del árbol de búsqueda se asocia con una variable X No es necesaria para que el árbol de búsqueda sea exhaustivo. Es necesario que cada nodo se asocie con una variable para la generación de sucesores. X 4 X 4 X... 4 X X Diferentes variables en el mismo nivel: ordenación dinámica de variables36 Heurística: selección de variable Ejemplo: 6 reinas En nodo q qué variable asignar a continuación? 1. Hay solución en descendientes(q) cualquier variable es adecuada 2. No hay solución en descendientes(q) asignar la variable que antes descubre que no hay solución En general, qué situación es más frecuente? Salvo problemas triviales, situación 2 Mayor esfuerzo del algoritmo: salir de subproblemas sin solución Suponemos situación 2: asignar primero aquella variable que, aparentemente, antes nos conduce a un fallo (principio fail-first) Heurística dominios mínimos: asignar primero la variable con menor número de valores factibles 4 nodos para detectar que no hay solución con (1,2) (6,6)37 Ejemplo Heurística: selección de valor En nodo q qué valor asignar a continuación? 1. Hay solución en descendientes(q) un valor que mantenga la resolubilidad del nodo sucesor 2. No hay solución en descendientes(q) cualquier valor es adecuado Suponemos situación 1: asignar primero aquella valor que, aparentemente, antes nos conduce al éxito (principio success-first) Heurística anticipación valores: 6 nodos asignar primero el valor que es consistente con mayor número de valores factibles del resto de variables para detectar que no hay solución con (1,2) (6,6)38 Coste heurísticas Compromiso coste / beneficio: coste: suma de costes de cálculo en cada nodo beneficio en todo el árbol sale a cuenta si coste < beneficio Dominios mínimos y anticipación: Dominios mínimos: exige calcular el número de valores factibles Algoritmos de anticipación: calculan los valores factibles Anticipación obtiene dominios mínimos sin coste adicional Evaluación de las heurísticas: Evaluación empírica Esfuerzo computacional constraint checks / tiempo CPU Resultados empíricos, 20 reinas, 1ª solución BT cc FC cc FC+dom min cc Documentos relacionados
Tema 3: Problemas de Satisfacción de Restricciones Universidad de Granada Tema 3: Satisfacción de Restricciones Contenido Problemas de satisfacción de restricciones Métodos de búsqueda Búsqueda local para Más detalles Programación con Restricciones Constraint Programming
Programación con Restricciones Constraint Programming Introducción basada en Roman Barták: Guide to Constraint Programming http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html Constraint Programming Más detalles Problemas de satisfacción de restricciones.
Problemas de satisfacción de restricciones. In whitch we see how treating states as more than just little black boxes leads to the invention of a range of powerful new search methods and a deeper understanding Más detalles Problemas de Satisfacción de Restricciones
Problemas de Satisfacción de estricciones José Luis uiz eina José Antonio Alonso Jiménez Franciso J. Martín Mateos María José Hidalgo Doblado Dpto. Ciencias de la Computación e Inteligencia Artificial Más detalles Razonamiento con restricciones. Pedro Meseguer IIIA CSIC Bellaterra
Razonamiento con restricciones Pedro Meseguer IIIA CSIC Bellaterra Un poco de historia:" comienzos" mejoras algorítmicas" extensiones" CSP, ejemplos, aplicaciones" Sumario! Algoritmos de resolución: búsqueda Más detalles Tema 5: Problemas de satisfacción de restricciones
Tema 5: Problemas de satisfacción de restricciones José Luis uiz eina José Antonio Alonso Franciso J. Martín Mateos María José Hidalgo Departamento de Ciencias de la Computación e Inteligencia Artificial Más detalles Problemas de satisfacción de restricciones. Javier Ramírez Rodríguez Departamento de Sistemas Universidad Autónoma Metropolitana
Problemas de satisfacción de restricciones Javier Ramírez Rodríguez Departamento de Sistemas Universidad Autónoma Metropolitana La programación con restricciones (PR) ha generado gran expectación entre Más detalles Hoja de Problemas Tema 6 Búsqueda con estados estructurados: Restricciones
Ejercicio 1: 1.1. Si se resuelve un problema de satisfacción de restricciones mediante búsqueda con asignaciones parciales, entonces (a) (b) (c) (d) (e) Un estado siempre asigna un valor a todas las variables Más detalles Algoritmos de planificación basados en restricciones para la sustitución de componentes defectuosos Irene Barba Rodríguez, 48861238S irenebr@us.
Algoritmos de planificación basados en restricciones para la sustitución de componentes defectuosos Irene Barba Rodríguez, 48861238S irenebr@us.es Supervised by Prof. Dr. Carmelo del Valle Sevillano Thesis Más detalles Inteligencia Artificial. Visiones: Árboles de Búsqueda Técnicas Look-Back Técnicas Look-Ahead. Elizabeth Montero Ureta.
Inteligencia Artificial Elizabeth Montero Ureta Departamento de Informática Universidad Técnica Federico Santa María Campus Santiago 1 1er Semestre 2009 1/18 2/18 Visiones: Tiene una solución? Encontrar Más detalles Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial ISSN: 1137-3601 revista@aepia.org
Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial ISSN: 1137-3601 revista@aepia.org Asociación Española para la Inteligencia Artificial España Barber, Federico; Salido, Miguel Más detalles DEPARTAMENTO DE INGENIERÍA EN SISTEMAS Y COMPUTACIÓN OPCIÓN I
1INSTITUTO TECNOLÓGICO DE CIUDAD MADERO DEPARTAMENTO DE INGENIERÍA EN SISTEMAS Y COMPUTACIÓN OPCIÓN I TESIS: Desarrollo de Algoritmos de Retroceso Aplicados a la solución del Problema del Diseño de la Más detalles III. BÚSQUEDA Y RESOLUCIÓN DE PROBLEMAS. III.3.
III. BÚSQUEDA Y RESOLUCIÓN DE PROBLEMAS. III.3. Búsquedas con retroceso. III.3.1. Búsquedas con retroceso a ciegas. III.3.1.1. Procedimientos con retroceso. La búsqueda con retroceso, o backtracking, es Más detalles Apuntes de Matemática Discreta 6. Relaciones
Apuntes de Matemática Discreta 6. Relaciones Francisco José González Gutiérrez Cádiz, Octubre de 2004 Universidad de Cádiz Departamento de Matemáticas ii Lección 6 Relaciones Contenido 6.1 Generalidades..................................... Más detalles Resolución de problemas
Inteligencia en Redes de Comunicaciones Resolución de problemas Julio Villena Román jvillena@it.uc3m.es El problema de resolver problemas La resolución de problemas es uno de los procesos básicos de razonamiento Más detalles El proyecto realizado consiste en un resolutor de sudokus mediante CSP.
Introducción El proyecto realizado consiste en un resolutor de sudokus mediante CSP. El problema del sudoku fue inventado por Howard Garns en 1979 y se volvió muy popular en Japón en 1986. En España ha Más detalles Resolución de Problemas
RAZONAMIENTO BASADO EN MODELOS: RAZONAMIENTO CUALITATIVO RAZONAMIENTO CUALITATIVO BASADO EN RESTRICCIONES 1 CONTENIDOS Introducción al modelado basado en restricciones La variable cualitativa y su representación Más detalles Métodos Heurísticos en Inteligencia Artificial
Métodos Heurísticos en Inteligencia Artificial Javier Ramírez rez-rodríguez Ana Lilia Laureano-Cruces Universidad Autónoma Metropolitana Métodos Heurísticos en Inteligencia Artificial Los problemas de Más detalles Búsqueda Heurística IV
Búsqueda Heurística IV Pedro Meseguer IIIA-CSIC Bellaterra, Spain pedro@iiia.csic.es 2 jugadores Búsqueda para juegos Perfecta información: cada jugador conoce toda la información del contrario no hay Más detalles Matemáticas 2º BTO Aplicadas a las Ciencias Sociales
Matemáticas 2º BTO Aplicadas a las Ciencias Sociales CONVOCATORIA EXTRAORDINARIA DE JUNIO 2014 MÍNIMOS: No son contenidos mínimos los señalados como de ampliación. I. PROBABILIDAD Y ESTADÍSTICA UNIDAD Más detalles Restricciones sobre dominios finitos con Gprolog
Autores: Rubén García Portal Nikolai Smirnov Restricciones sobre dominios finitos con Gprolog Introducción. Este documento explicará brevemente las funciones que se utilizan en Gprolog para resolución Más detalles Representación basada en Restricciones
Representación basada en Restricciones Asunción Gómez-Pérez asun@fi.upm.es Departamento de Inteligencia Artificial Facultad de Informática Universidad Politécnica de Madrid Campus de Montegancedo sn, 28660 Más detalles Apuntes de Grafos. 1. Definiciones
Apuntes de Grafos Un grafo es una entidad matemática introducida por Euler en 736 para representar entidades (vértices) que pueden relacionarse libremente entre sí, mediante el concepto de arista Se puede Más detalles Programación Lineal Entera
Programación Lineal Entera P.M. Mateo y David Lahoz 2 de julio de 2009 En este tema se presenta un tipo de problemas formalmente similares a los problemas de programación lineal, ya que en su descripción Más detalles Capítulo 12: Indexación y asociación
Capítulo 12: Indexación y asociación Conceptos básicos Índices ordenados Archivos de índice de árbol B+ Archivos de índice de árbol B Asociación estática Asociación dinámica Comparación entre indexación Más detalles 1 Agencia de viajes: enunciado
1 AGENCIA DE VIAJES: ENUNCIADO 1 1 Agencia de viajes: enunciado Una agencia de viajes mantiene una base de datos con exactamente N clientes y M destinos turísticos. En una situación real, estos valores Más detalles {} representa al conjunto vacío, es decir, aquel que no contiene elementos. También se representa por.
2. Nociones sobre Teoría de Conjuntos y Lógica Para llevar a cabo nuestro propósito de especificar formalmente los problemas y demostrar rigurosamente la correctitud de nuestro programas, introduciremos Más detalles Estructuras algebraicas
Tema 2 Estructuras algebraicas básicas 2.1. Operación interna Definición 29. Dados tres conjuntos A, B y C, se llama ley de composición en los conjuntos A y B y resultado en el conjunto C, y se denota Más detalles TÉCNICAS DE PLANIFICACIÓN Y CONTROL DE PROYECTOS 1
Técnicas de planificación y control de proyectos Andrés Ramos Universidad Pontificia Comillas http://www.iit.comillas.edu/aramos/ Andres.Ramos@comillas.edu TÉCNICAS DE PLANIFICACIÓN Y CONTROL DE PROYECTOS Más detalles INDICE. XVII Prólogo a la edición en español. XXI 1. Calculo proporcional 1.1. Argumentos y proporciones lógicas
INDICE Prologo XVII Prólogo a la edición en español XXI 1. Calculo proporcional 1.1. Argumentos y proporciones lógicas 1 1.1.1. Introducción 1.1.2. Algunos argumentos lógicos importantes 2 1.1.3. Proposiciones Más detalles Secuenciación de una línea mixed-model mediante un algoritmo exacto Pág. 1. Resumen
Secuenciación de una línea mixed-model mediante un algoritmo exacto Pág. 1 Resumen En una línea de montaje de productos mixtos, aquella que es responsable de la producción de diversas variaciones de un Más detalles Descripción inicial del sistema. Descripción final del sistema. Estado 1 Estado 2 Estado n
Búsqueda en Inteligencia Artificial Fernando Berzal, berzal@acm.org Búsqueda en I.A. Introducción Espacios de búsqueda Agentes de búsqueda Uso de información en el proceso de búsqueda Búsqueda sin información Más detalles Desarrollo de SBC. cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 1 / 41
Desarrollo de SBC Ingeniería de los SBC Desarrollo de SBC El punto más importante del desarrollo de SBC es la extracción del conocimiento Requiere la interacción entre el Ingeniero del Conocimiento y el Más detalles Fundamentos de Investigación de Operaciones Asignación y Vendedor Viajero
Fundamentos de Investigación de Operaciones y Vendedor Viajero 23 de mayo de 2004 Si bien la resolución del problema de transporte mediante tableau parece ser muy expedita, existen ciertos tipos de problemas Más detalles Arboles Binarios de Búsqueda
Arboles Binarios de Búsqueda Algoritmos y Estructuras de Datos Departamento de Electricidad y Electrónica (UPV/EHU) Arboles Binarios de Búsqueda p.1/52 Arboles Binarios Arbol binario: árbol ordenado de Más detalles Sistemas de producción y búsqueda de soluciones. Area de Computación e Inteligencia Artificial 1
Sistemas de producción y búsqueda de soluciones Area de Computación e Inteligencia Artificial 1 Técnicas de búsqueda Resolución de problemas en Inteligencia Artificial. En general, podemos afirmar que Más detalles DEFINICION. Ing. M.Sc. Fulbia Torres Asignatura: Estructuras de Datos Barquisimeto 2006
ARBOLES ESTRUCTURAS DE DATOS 2006 DEFINICION Un árbol (tree) es un conjunto finito de nodos. Es una estructura jerárquica aplicable sobre una colección de elementos u objetos llamados nodos; uno de los Más detalles ÁRBOLES GENERALES Y Y ESTRUCTURAS DE ÍNDICES DEFINICIONES Y REPRESENTACIONES DEFINICIONES Y REPRESENTACIONES. NOMENCLATURA SOBRE ÁRBOLES. DECLARACIÓN Y REPRESENTACIÓN.. CONSTRUCCIÓN.. ÁRBOLES 2-3-4. ÁRBOLES Más detalles Tema 7: Optimización sobre Redes Muchos de los problemas de Investigación Operativa pueden modelizarse y resolverse sobre un grafo: conjunto de
Tema 7: Optimización sobre Redes Muchos de los problemas de Investigación Operativa pueden modelizarse y resolverse sobre un grafo: conjunto de vértices o nodos conectados con arcos y/o aristas. Diseñar Más detalles GRAFOS. Prof. Ing. M.Sc. Fulbia Torres
ESTRUCTURAS DE DATOS 2006 Prof. DEFINICIÓN Un grafo consta de un conjunto de nodos(o vértices) y un conjunto de arcos (o aristas). Cada arco de un grafo se especifica mediante un par de nodos. Denotemos Más detalles Una heurística para la asignación de máquinas a trabajos fijos
VIII Congreso de Ingeniería de Organización Leganés, 9 y 10 de septiembre de 2004 Una heurística para la asignación de máquinas a trabajos fijos José Manuel García Sánchez, Marcos Calle Suárez, Gabriel Más detalles > Cadenas de Markov. Horacio Rojo y Miguel Miranda. @ 71.07 Investigación Operativa
@ 707 Investigación Operativa > Cadenas de Markov Horacio Rojo y Miguel Miranda c 2009 Facultad de Ingeniería, Universidad de Buenos Aires Digitalizado por Virginia Guala $September 2, 2009 Cadenas de Más detalles Estructuras de datos: Árboles binarios de
Estructuras de datos: Árboles binarios de búsqueda, Dep. de Computación - Fac. de Informática Universidad de A Coruña Santiago Jorge santiago.jorge@udc.es Árboles binarios de búsqueda, Table of Contents Más detalles Estructuras de Datos Abstractas en Lenguaje Java
Universidad de Santiago de Chile Facultad de Ingeniería Departamento de Ingeniería Industrial Estructuras de Datos Abstractas en Lenguaje Java Listas Enlazadas, Colas, Pilas y Árboles Binarios Creado por Más detalles Razonamiento Espacial con Relaciones Cardinales Basado en Problemas de Satisfacción de Restricciones y Lógicas Modales
UNIVERSIDAD DE MURCIA Departamento de Ingeniería de la Información y las Comunicaciones Tesis Doctoral Razonamiento Espacial con Relaciones Cardinales Basado en Problemas de Satisfacción de Restricciones Más detalles 3. Consideremos el puzzle-8 descrito en clase y sea el estado objetivo, como de costumbre,
E.T.S.I. INFORMÁTICA 4º CURSO. INTELIGENCIA ARTIFICIAL. UNIVERSIDAD DE MÁLAGA Dpto. Lenguajes y Ciencias de la Computación RELACIÓN DE PROLEMAS. ÚSQUEDAS CON ÁROL.. Un móvil puede situarse en los nodos Más detalles Tema 2. Recursividad. Fundamentos de Programación II. Luís Rodríguez Baena (luis.rodriguez@upsam.net)
Fundamentos de Programación II Tema 2. Recursividad Luís Rodríguez Baena (luis.rodriguez@upsam.net) Universidad Pontificia de Salamanca (campus Madrid) Escuela Superior de Ingeniería y Arquitectura Naturaleza Más detalles Un grafo G es un par (V,E) donde V es un conjunto (llamado conjunto de vértices) y E un subconjunto de VxV (conjunto de aristas).
TEMA 5.- GRAFOS 5.1.- DEFINICIONES BÁSICAS Un grafo G es un par (V,E) donde V es un conjunto (llamado conjunto de vértices) y E un subconjunto de VxV (conjunto de aristas). Gráficamente representaremos Más detalles Algoritmos sobre Grafos
Sexta Sesión 27 de febrero de 2010 Contenido Deniciones 1 Deniciones 2 3 4 Deniciones sobre Grafos Par de una lista de nodos y una lista de enlaces, denidos a su vez como pares del conjunto de nodos. Más detalles 9. MATRICES 189 9.1. DEFINICIÓN Y NOTACIONES... 189 9.2. OPERACIONES CON MATRICES... 190 9.3. MATRICES CUADRADAS... 192 9.3.1.
ÍNDICE 9. MATRICES 189 9.1. DEFINICIÓN Y NOTACIONES....................... 189 9.2. OPERACIONES CON MATRICES..................... 190 9.3. MATRICES CUADRADAS.......................... 192 9.3.1. Matrices Más detalles Estructuras de Datos. Montículos. Montículos. Montículos. Tema 3. Montículos. Definiciones básicas: Definiciones básicas:
Estructuras de Datos Tema. 1. Definiciones básicas 2. Implementación. Operaciones con montículos 4. Definiciones básicas: En un árbol binario completo todos los niveles del árbol (excepto tal vez el último) Más detalles ÁLGEBRA LINEAL E.T.S. DE INGENIERÍA INFORMÁTICA INGENIERÍA TÉCNICA EN INFORMÁTICA DE GESTIÓN. Apuntes de. para la titulación de
E.T.S. DE INGENIERÍA INFORMÁTICA Apuntes de ÁLGEBRA LINEAL para la titulación de INGENIERÍA TÉCNICA EN INFORMÁTICA DE GESTIÓN Fco. Javier Cobos Gavala Amparo Osuna Lucena Rafael Robles Arias Beatriz Silva Más detalles Análisis III. Joaquín M. Ortega Aramburu
Análisis III Joaquín M. Ortega Aramburu Septiembre de 1999 Actualizado en julio de 2001 2 Índice General 1 Continuidad en el espacio euclídeo 5 1.1 El espacio euclídeo R n............................... Más detalles ARBOLES ARBOLES BINARIOS ORDENADOS. REPRESENTACIÓN Y OPERACIONES
ARBOLES ARBOLES BINARIOS ORDENADOS. REPRESENTACIÓN Y OPERACIONES Características ARBOLES - CONCEPTOS Cada elemento del árbol se relaciona con cero o más elementos a quienes llama hijos. Si el árbol no Más detalles Planificación y secuenciamiento de procesos por lotes. Prof. Cesar de Prada ISA-UVA
Planificación secuenciamiento de procesos por lotes Prof. Cesar de Prada ISA-UVA Indice Procesos plantas batch Conceptos básicos de secuenciamiento Formulación de problemas de secuenciamiento Resolución Más detalles Tema 10- Representación Jerárquica: Tema 10- Representación Jerárquica: Árboles Binarios
Tema 10- Representación Jerárquica: Árboles Binarios Tema 10- Representación Jerárquica: Árboles Binarios Germán Moltó Escuela Técnica Superior de Ingeniería Informática Universidad Politécnica de Valencia Más detalles Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 Programación Lineal Entera
Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 11 de septiembre de 2003 1. Introducción Un LP donde se requiere que todas las variables sean enteras se denomina un problema Más detalles Complejidad - Problemas NP-Completos. Algoritmos y Estructuras de Datos III
Complejidad - Problemas NP-Completos Algoritmos y Estructuras de Datos III Teoría de Complejidad Un algoritmo eficiente es un algoritmo de complejidad polinomial. Un problema está bien resuelto si se conocen Más detalles Técnicas para el Manejo de CSPs no Binarios
Técnicas para el Manejo de CSPs no Binarios Miguel A. Salido Dpto. Ciencias de la Computación e Inteligencia Artificial Escuela Politécnica Superior Universidad de Alicante, Spain {masalido}@dccia.ua.es Más detalles Resumen de técnicas para resolver problemas de programación entera. 15.053 Martes, 9 de abril. Enumeración. Un árbol de enumeración
5053 Martes, 9 de abril Ramificación y acotamiento () Entregas: material de clase Resumen de técnicas para resolver problemas de programación entera Técnicas de enumeración Enumeración completa hace una Más detalles Ejercicios de álgebra 1 Cuarto curso (2003/04)
Departamento de Álgebra, Geometría y Toplogía. Universidad de Málaga Ejercicios de álgebra 1 Cuarto curso (2003/04) Relación 1. Ideales primos y maximales. Nilradical y radical de Jacobson Profesor de Más detalles Investigación Operacional I EII 445
Investigación Operacional I EII 445 Programación Lineal Método Simple Gabriel Gutiérrez Jarpa. Propiedades Básicas de Programación Lineal Formato Estándar Un problema de programación lineal es un programa Más detalles INDICE GENERAL... 1 INDICE DE FIGURAS... 3
INDICE GENERAL INDICE GENERAL... 1 INDICE DE FIGURAS... 3 1. Introducción y Discusión Bibliográfica... 4 1.1 Discusión Bibliográfica... 4 1.2 Motivación... 5 1.3 Estructura de la tesis... 6 2. Análisis Más detalles Tema 3: Representación y minimización de
Tema 3: Representación y minimización de funciones lógicas 3.. Teoremas y postulados del álgebra de Boole Definiciones El álgebra de Boole se utiliza para la resolución de problemas de tipo lógico-resolutivo, Más detalles Carrera: IFM - 0423 3-2-8. Participantes. Representantes de la academia de sistemas y computación de los Institutos Tecnológicos.
1.- DATOS DE LA ASIGNATURA Nombre de la asignatura: Carrera: Clave de la asignatura: Horas teoría-horas práctica-créditos Matemáticas para computación Licenciatura en Informática IFM - 0423 3-2-8 2.- HISTORIA Más detalles Dada la dificultad práctica para resolver de forma exacta toda una serie de problemas de
CAPÍTULO 2 Métodos de solución Dada la dificultad práctica para resolver de forma exacta toda una serie de problemas de programación entera, se han desarrollado algoritmos que proporcionan soluciones factibles Más detalles CURSO CERO. Departamento de Matemáticas. Profesor: Raúl Martín Martín Sesiones 18 y 19 de Septiembre
CURSO CERO Departamento de Matemáticas Profesor: Raúl Martín Martín Sesiones 18 y 19 de Septiembre Capítulo 1 La demostración matemática Demostración por inducción El razonamiento por inducción es una Más detalles Matrices equivalentes. El método de Gauss
Matrices equivalentes. El método de Gauss Dada una matriz A cualquiera decimos que B es equivalente a A si podemos transformar A en B mediante una combinación de las siguientes operaciones: Multiplicar Más detalles Capítulo VI MÉTODOS DE SOLUCIÓN PARA JOB SHOP SCHEDULING
Capítulo VI MÉTODOS DE SOLUCIÓN PARA JOB SHOP SCHEDULING 6.1. HEURÍSTICAS CONVENCIONALES El problema de job shop scheduling (JSSP) es un problema muy importante [69]; está entre los problemas de optimización Más detalles Máster Universitario en Ingeniería de Caminos, Canales y Puertos Introducción al Análisis Numérico
Máster Universitario en Ingeniería de Caminos, Canales y Puertos Introducción al Análisis Numérico Departamento de Matemática Aplicada Universidad Granada Introducción El Cálculo o Análisis Numérico es Más detalles 3. Funciones reales de una variable real. Límites. Continuidad 1
3. Funciones reales de una variable real. Límites. Continuidad 1 Una función real de variable real es una aplicación f : D R, donde D es un subconjunto de R denominado dominio de f. La función f hace corresponder Más detalles Cómo rastrear objetos distribuidos. Rajmohan Rajaraman. Universidad de Northeastern
Cómo rastrear objetos distribuidos Rajmohan Rajaraman Universidad de Northeastern 1 El problema del rastreo de datos Un esquema de rastreo de datos. o Encontrar una copia (cerca) del objeto solicitado. Más detalles árbol como un conjunto de nodos y líneas
ÁRBOLES CAPÍTULO 6 ÁRBOLES Desde el punto de vista conceptual, un árbol es un objeto que comienza con una raíz (root) y se extiende en varias ramificaciones o líneas (edges), cada una de las cuales puede Más detalles 4.3 INTERPRETACIÓN ECONÓMICA DE LA DUALIDAD
4.3 INTERPRETACIÓN ECONÓMICA DE LA DUALIDAD El problema de programación lineal se puede considerar como modelo de asignación de recursos, en el que el objetivo es maximizar los ingresos o las utilidades, Más detalles Registro (record): es la unidad básica de acceso y manipulación de la base de datos.
UNIDAD II 1. Modelos de Bases de Datos. Modelo de Red. Representan las entidades en forma de nodos de un grafo y las asociaciones o interrelaciones entre estas, mediante los arcos que unen a dichos nodos. Más detalles TEMA II: ÁLGEBRA DE CONMUTACIÓN
TEMA II: ÁLGEBRA DE CONMUTACIÓN En este capítulo veremos los métodos matemáticos que se disponen para las operaciones relacionadas con los circuitos digitales, así como las funciones más básicas de la Más detalles Combinación de Algoritmos Evolutivos y Técnicas Heurísticas para Problemas de Scheduling
Combinación de Algoritmos Evolutivos y Técnicas Heurísticas para Problemas de Scheduling Ramiro Varela, Javier Blanco, Camino Rodríguez, Jorge Puente y César Alonso Centro de Inteligencia Artificial. Universidad Más detalles MATEMÁTICAS I. Licenciatura de Administración y Dirección de Empresas. Fernando Casas, María Vicenta Ferrer, Pura Vindel. Departament de Matemàtiques
MATEMÁTICAS I Licenciatura de Administración y Dirección de Empresas Fernando Casas, María Vicenta Ferrer, Pura Vindel Departament de Matemàtiques Universitat Jaume I 2 Estas notas constituyen el material Más detalles El Teorema de existencia y unicidad de Picard
Tema 2 El Teorema de existencia y unicidad de Picard 1 Formulación integral del Problema de Cauchy El objetivo del presente Tema, y del siguiente, es analizar el Problema de Cauchy para un SDO de primer Más detalles Matrices. Definiciones básicas de matrices. www.math.com.mx. José de Jesús Angel Angel. jjaa@math.com.mx
Matrices Definiciones básicas de matrices wwwmathcommx José de Jesús Angel Angel jjaa@mathcommx MathCon c 2007-2008 Contenido 1 Matrices 2 11 Matrices cuadradas 3 12 Matriz transpuesta 4 13 Matriz identidad Más detalles Comenzaremos recordando algunas definiciones y propiedades estudiadas en el capítulo anterior.
Capítulo 2 Matrices En el capítulo anterior hemos utilizado matrices para la resolución de sistemas de ecuaciones lineales y hemos visto que, para n, m N, el conjunto de las matrices de n filas y m columnas Más detalles MATEMÁTICA DISCRETA: Conjuntos, combinatoria y grafos. Roberto J. de la Fuente López. Versión 20110923. (corrección de erratas a versión 20100712)
MATEMÁTICA DISCRETA: Conjuntos, combinatoria y grafos Roberto J. de la Fuente López Versión 20110923 (corrección de erratas a versión 20100712) Índice general PRESENTACIÓN... 5 AVISO DE DERECHOS DE AUTOR... Más detalles Proyecto Unico Interpretador de SetCalc
Universidad Simón Bolívar Dpto. de Computación y Tecnología de la Información CI3721 - Traductores e Interpretadores Abril-Julio 2008 Proyecto Unico Interpretador de SetCalc A continuación se describe Más detalles Unidad V: Integración
Unidad V: Integración 5.1 Introducción La integración es un concepto fundamental de las matemáticas avanzadas, especialmente en los campos del cálculo y del análisis matemático. Básicamente, una integral Más detalles Un programa entero de dos variables. 15.053 Jueves, 4 de abril. La región factible. Por qué programación entera? Variables 0-1
15.053 Jueves, 4 de abril Un programa entero de dos variables Introducción a la programación entera Modelos de programación entera Handouts: material de clase maximizar 3x + 4y sujeto a 5x + 8y 24 x, y Más detalles Una cadena sobre Σ es cualquier secuencia de elementos de longitud finita sobre Σ.
Alfabetos, Cadenas y Lenguajes Definición 1 Un Alfabeto es cualquier conjunto finito, no vacío. Ejemplo 1 Sea Σ = {0, 1, 2, 3,..., 9} donde 0 Σ Definición 2 Una cadena sobre Σ es cualquier secuencia de Más detalles 4. MÉTODOS DE CLASIFICACIÓN
4. MÉTODOS DE CLASIFICACIÓN Una forma de sintetizar la información contenida en una tabla multidimensional (por ejemplo una tabla léxica agregada), es mediante la conformación y caracterización de grupos. Más detalles Ejemplos: Sean los conjuntos: A = { aves} B = { peces } C = { anfibios }
La Teoría de Conjuntos es una teoría matemática, que estudia básicamente a un cierto tipo de objetos llamados conjuntos y algunas veces, a otros objetos denominados no conjuntos, así como a los problemas Más detalles Un modelo de integración de técnicas de CLAUSURA y CSP de restricciones temporales: Aplicación a problemas de Scheduling
UNIVERSIDAD DE ALICANTE Departamento de Ciencia de la Computación e Inteligencia Artificial Un modelo de integración de técnicas de CLAUSURA y CSP de restricciones temporales: Aplicación a problemas de Más detalles Álgebras de Boole. Juan Medina Molina. 25 de noviembre de 2003
Álgebras de Boole Juan Medina Molina 25 de noviembre de 2003 Introducción Abordamos en este tema el estudio de las álgebras de Boole. Este tema tiene una aplicación directa a la electrónica digital ya Más detalles 7. Conclusiones. 7.1 Resultados
7. Conclusiones Una de las preguntas iniciales de este proyecto fue : Cuál es la importancia de resolver problemas NP-Completos?. Puede concluirse que el PAV como problema NP- Completo permite comprobar Más detalles Lógica Proposicional IIC2212. IIC2212 Lógica Proposicional 1 / 56
Lógica Proposicional IIC2212 IIC2212 Lógica Proposicional 1 / 56 Inicio de la Lógica Originalmente, la Lógica trataba con argumentos en el lenguaje natural. Ejemplo Es el siguiente argumento válido? Todos Más detalles Búsqueda Heurística para Problemas de Scheduling *
IX Congreso de Ingeniería de Organización Gijón, 8 y 9 de septiembre de 2005 Búsqueda Heurística para Problemas de Scheduling * María Sierra Sánchez 1, Ramiro Varela Arias 2 1 Dpto. de Informática. Campus Más detalles Capítulo 6. ÁRBOLES.
67 Capítulo 6. ÁRBOLES. 6.1 Árboles binarios. Un árbol binario es un conjunto finito de elementos, el cual está vacío o dividido en tres subconjuntos separados: El primer subconjunto contiene un elemento Más detalles 2017 © DocPlayer.es Política de privacidad | Condiciones del servicio | Feedback

References: Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 RESOLUCIÓN 
 RESOLUCIÓN 
 Resolución 
 Resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 Resolución 
 Resolución 
 resolución 
 resolución