Dr. Gonzalo HernándezFI-2 Enumeración1 Fundamentos Informática II Enumeración Combinatoria Dr. Ing. Gonzalo Hernández Oliva Universidad Técnica Federico

Dr. Gonzalo Hernández FI-2 Enumeración 1

Fundamentos Informática II

Enumeración

Combinatoria

Dr. Ing. Gonzalo Hernández Oliva

Universidad Técnica Federico Santa MaríaDepartamento de Informática


Enumeración:1) Motivación2) Reglas de Suma y Producto3) Permutaciones

4) Combinaciones: Teorema del Binomio Combinaciones con Repeticiones

5) Principio Inclusión y Exclusión5) Conceptos de Probabilidad

6) Aplicación: Complejidad Computacional Problemas P y NP


Repartición de Naranjas:(Ecuaciones Lineales Enteras)

De cuántas formas posibles se pueden

repartir 12 naranjas de manera que

Gabriel (G) reciba al menos 4 y María

(M) y Francisco (F) reciban al menos 2.

1) Motivación 1Enumeración :


Buscamos la cantidad total de soluciones de la ecuación:

x1 + x2 + x3 = 12

4 ≤ x1 ≤ 8

2 ≤ x2 ≤ 6

2 ≤ x3 ≤ 6

Enumeración :

(Ecuaciones Lineales Enteras)1) Motivación 1: Repartición de Naranjas

Donde: xk : cantidad de

naranjas dela persona k


1) Motivación 1: Repartición de Naranjas

Enumeración :

G

M

F

4 4 4 4 4 5 5 5 5 6 6 6 7 7 8

2 3 4 5 6 2 3 4 5 2 3 4 3 2 2

6 5 4 3 2 5 4 3 2 4 3 2 2 3 2

Cantidad Total de Formas de Repartir: 15

(Ecuaciones Lineales Enteras)


Problema NP: Problema SAT

Enumerar (Hacer una lista) todos los

valores de verdad de una proposición

lógica.

Algoritmo Backtracking

1) Motivación 2:

Enumeración :


Problema NP: (Problema SAT)

Enumerar (Hacer una lista) todos los posibles subconjuntos de un conjunto con cardinalidad finita.

Algoritmo Backtracking

1) Motivación 3:

Enumeración :


Modelo NN:

bi

w1i

wni

. . .

01

01

01

xi(t)

xxii(t) (t) == i=1,...,ni=1,...,n1 wwij ij xxjj(t-1)(t-1) - - bbi i

n

j=1

Enumeración : 1) Motivación 4


xi(t) =

i=1,...,n

1 wij xj(t-1) - bi

n

j=1

W = Matriz de

Conectividadb = Vector de Umbrales

wij

xi(0) {0,1}

i

j

Modelo NN: Enumeración : 1) Motivación 4


Complejidad NN: SDD

Régimen Estacionario y Transiente Visualización de la Evolución

Matriz de Conectividad

Simétrica

WNo - Simétrica

Comportamiento Dinámico Simple

Comportamiento Dinámico Complejo



Complejidad NN: Simetría

Enumerar NN construidas en base a valores

de W y b seleccionados de un conjunto de

cardinalidad finito:

wij ε Q = {1, 2 , … , q} bi ε P = {1, 2 , … , p}

Enumerar NN simétricas

Enumerar NN no - simétricas



Enumeración :

Problema NP en Grafos: TSP

1) Motivación 5:

Backtracking


Enumeración :

Problema NP en Grafos: Coloración1) Motivación 6:

Backtracking


Enumeración :

Problema NP en Grafos: Bisección1) Motivación 7:

Backtracking

Tarea 1Tarea 1


Enumeración:

Regla de la Suma: Consideremos dos procedimientos que pueden ser realizados en forma independiente. Si existen n formas de realizar el primer procedimiento y existen m formas de realizar el segundo entonces ambos procedimientos se realizan en (n+m) formas.

2) Reglas de Suma y Producto:


Enumeración:

Regla del Producto: Sea un procedimiento que puede ser dividido en 2 etapas. Si existen n formas de realizar la primera etapa y para cada una de estas formas existen m formas de realizar la segunda etapa entonces el procedimiento se realiza en (nm) formas

2) Reglas de Suma y Producto:


Enumeración:

Al salir de la tienda, Camila y Fernanda vieron cómo dos personas huían de una joyería, en la cual sonaba la alarma. María está segura que el último dígito de la patente del auto en que huyeron los asaltantes era un 5 ó un 6, y el segundo era un 3, mientras Fernanda afirma que la primera letra era una O o una D, y que el primer dígito era un 1 ó un 7. ¿Cuántas patentes cumplen estas restricciones, suponiendo tres letras y cuatro dígitos ?

2) Reglas de Suma y Producto: Ej.


Enumeración:

3 Ciudades A, B y C están conectadas cómo se muestra en la figura:


AB

C


Enumeración:

Suponiendo que los caminos permiten viajar en ambos sentidos:

¿ De cuántas formas se puede viajar de la ciudad A a la ciudad C ?

¿ Cuántas formas es posible de realizar el viaje A B A ?

¿ Cuántas formas existen de realizar un viaje donde la ciudad inicial y final es la misma ? Examinar todos los casos.



Enumeración:

Un alfabeto de 30 símbolos es utilizado

para la creación de mensajes en un

lenguaje de comunicación:

¿ Cuántos mensajes distintos formados

por palabras de 15 símbolos pueden ser

transmitidos si cada símbolo puede ser

repetido ?



¿ Cuántos mensajes distintos formado por

palabras de 20 símbolos pueden ser transmitidos

si cada símbolo no puede ser repetido ?

¿ Cuántos mensajes distintos formado por

palabras de 25 símbolos pueden ser transmitidos

si 10 de los 30 símbolos pueden aparecer sólo en

el primer, segundo y último carácter del mensaje

y los restantes 20 símbolos pueden aparecer en

cualquier posición del mensaje, permitiendo

repeticiones ?

Enumeración:2) Reglas de Suma y Producto: Ej.


¿ Cómo varían las respuestas a las

preguntas anteriores si: Cada mensaje está formado por palabras de

largo n y existen p posibles símbolos ?

Cada mensaje está formado por palabras de

largo n, existen p posibles símbolos y el

lenguaje está compuesto por paquetes de

largo q dónde q divide a n ?

Enumeración:



Enumeración:

Dada una colección de n objetos distintos cualquier combinación (lineal) de ellos se denomina una permutación (se considera el orden). En general si existen n objetos distintos, denotados por a1 , ... , an y si 1 r n entonces el número de permutaciones de tamaño r de estos objetos está dado por :

(n)(n-1)(n-2) (n-r+1) = n! / (n-r)!

3) Permutaciones:


Enumeración:

En general si existen de n objetos con n1

objetos del primer tipo, n2 del segundo tipo,

... , nr del r-ésimo tipo, donde:

n1 + n2 + … + nr = n

entonces el número de arreglos lineales de estos objetos está dado por:

n! / (n1! n2! n3! , ... nr!)

3) Permutaciones:


Enumeración:

Consideraciones esenciales: Objetos Distinguibles i.e. Distintos Se considera el Orden ↔ Importa el Orden

(El orden genera arreglos s)

Ejemplos: Patentes, Mensajes Arreglos Lineales Puede existir Repetición (Sustitución)

3) Permutaciones:


Enumeración:

Arreglos No Lineales:

3) Permutaciones:

S1S1

S2S2

S3S3

S4S4

S5S5

S6S6

Formas Equivalentes de sentar personas:

Shift - Iguales


Enumeración:

Cuántas palabras de 5 letras hay para

las letras a, b, c, d, e, e, e. Cuántas palabras de 5 letras hay para las

letras anteriores si la palabra debe empezar

y terminar con una letra e.

Cuántas palabras de 5 letras hay para las

letras anteriores si la palabra no puede

tener letras “e” consecutivas.

3) Permutaciones: Ej.


Enumeración :

Problemas NP en Grafos: TSP

3) Permutaciones: Ej.

Backtracking


Enumeración:

Si consideramos n objetos distintos , cada selección o combinación de r de ellos, sin considerar el orden, corresponde a r! permutaciones de tamaño 1 r n de ellos. Por lo tanto el número de combinaciones de tamaño r de una colección de n objetos es :

= C(n,r) = P(n,r) / r! = n! / r! (n-r)!

4) Combinaciones:

nr


Enumeración:

Consideraciones esenciales:

Objetos Indistinguibles (O distintos por tipo) Puede existir Repetición o Sustitución

NO se considera el orden ↔ El Orden NO

importa

Ejemplo: Cartas, Producto Polinomios,

Selección Bolas de una Bolsa

4) Combinaciones:


Enumeración:

Sean x e y variables reales y n un entero positivo. Entonces :

4) Combinaciones: Teorema del Binomio

( x + y ) n = r=1

nnr

xr y(n-r)

Coeficientes Binomiales


Enumeración:

El número de combinaciones de n

objetos tomando 1 r n al mismo

tiempo está dado por C(n+r-1,r)

4) Combinaciones con Repetición:


Enumeración:

El número de selecciones, con

repetición , de tamaño 1 r n de

una colección de n objetos

El número de soluciones enteras de

la ecuación :

x1 + x2 + x3 + ... + xn = r

4) Combinaciones con Repetición:


Enumeración:

Una caja tiene esferas numeradas de 1 a n. Se escogen 2 esferas al azar. De cuantas formas es posible obtener números:

Consecutivos Pares o Impares

En los casos que las esferas se escogen con o sin sustitución.

4) Combinaciones: Ej.


Enumeración:

De cuántas formas posibles se puede obtener de un mazo de 52 cartas:

1 par 2 pares 3 cartas Un full 4 cartas Una escala real

4) Combinaciones: Ej.


Enumeración :

Problemas NP en Grafos: Graph Bisection

4) Combinaciones:

Min Cut

Backtracking


Probabilidad : Grado de

certidumbre

Probabilidad y Juegos de Azar

Probabilidad y Frecuencia

Relativa

Probabilidad Subjetiva

(Personal)

5) Probabilidad Conceptos Básicos Probabilidad:5) Probabilidad Conceptos Básicos Probabilidad:

Enumeración:


5) ProbabilidadConceptos Básicos Probabilidad:5) ProbabilidadConceptos Básicos Probabilidad:

Experimento aleatorio : - Ejemplo Espacio Muestral : - Ejemplo Espacio Muestral : Discreto , Continuo Evento o Suceso ε Partes() Sucesos Elementales - Sucesos Base, Seguros (P(A)=1), Imposibles (P(A)=0)

Enumeración:


5) ProbabilidadModelo Probabilístico:

Asociado a una Distribución de Probabilidad, es decir, una función que asigna a cada sub-conjunto razonable de su probabilidad.

Sea 2 = Partes() colección de eventos razonables de (-álgebra)

Enumeración:


Definición ProbabilidadNoción Intuitiva:P(A) = Resultados Favorables al Evento A

Resultados Posibles

Noción Frecuentista:Sea N: número total de veces que se realiza un experimento y NA: número total de veces que ocurre A

P(A) =NN

lim AN

Enumeración: 5) Probabilidad


Probabilidad Axiomática

Axioma 1: P(A) 0

Axioma 2: P() = 1

Axioma 3: Suponiendo que

A1, A2,..... son eventos

mutuamente

excluyentes : P(Ai) = P(Ai)


i i


Propiedades Probabilidad1) P(AC) = 1 - P(A)2) P(A) 13) Si A B P(A) P(B)4) P() = 05) P(A B) = P(A) + P(B) - P(A

B)

6) P( Ai) P(Ai)

7) P(A B) = P(A)P(B) A,B Independ.


i i


Probabilidad Condicional

Sean A, B dos sucesos tal que P(B) > 0.La probabilidad de A condicionada a la ocurrencia de B se denota por P(A/B) :

P(A/B) = P(A B)

P(B)



Probabilidad Condicional

Propiedades:

P(A/B) 0

P( /B) = 1

P( Ai /B) = P(Ai/B)



Ejercicio: Sean A,B sucesos de un mismo

modelo de probabilidad (, , P) tales que:

P(B)=0,4 P(AB)=0,7 P(A/B)=0,75

Determinar:

P(AC) ; P(A-B) ; P(ACBC) ; P(A/BC)



SoluciónP(AC) = 1 - P(A)P(AB) = P(A) + P(B) - P(AB)P(AB) = P(A/B) P(B) = 0,75 * 0,4 = 0,3P(A) = 0,7 - 0,4 + 0,3 = 0,6P(AC) = 0,4P(A-B) = P(ABC) = P(A) - P(AB) = 0,3P(ACBC) = P(AC) + P(BC) - P(ACBC)P(ACBC) = P(BC) - P(ABC) = 0,6 - 0,3 = 0,3Luego P(ACBC) = 0,4 + 0,6 - 0,3 = 0,7P(A/BC) = P(ABC)/P(BC)



Probabilidad Total

Sean B1 , B2 ,...., Bn eventos

mutuamente excluyentes, es decir :

P( ) = 1

Entonces

P(A) =

n

iiB

1

n

iii BPBAP

1

)()/(



Probabilidad Total

Consecuencia - Regla de Bayes:

P(B/A) = P(A/B) P(B)

P(A)



Un procesador para computadores puede provenir de cualquiera de tres fabricantes con probabilidades: p1 = 0,25 p2 = 0,50 p3 = 0,25

Las probabilidades de que un procesador funcione correctamente durante 10.000 horas es 0,1; 0,2 y 0,4 respectivamente para los 3 fabricantes.

Ejercicio:Enumeración: 5) Probabilidad


a)Calcular la probabilidad de que un procesador elegido al azar funcione durante 10.000 horas.

b)Si el procesador funcionó correctamente durante el período de 10.000 horas ¿cuál es la probabilidad de que haya provenido del 3er fabricante?

Ejercicio:Enumeración: 5) Probabilidad


Solucióni) P(C) =

= 0,1*0,25 + 0,2*0,5 + 0,4*0,25 = 0,225.

ii) P(F3/C) = P(C/F3) P(F3)

P(C) = 0,4 * 0,25 = 0.4

0,225

3

1

)()/(i

ii FPFCP


_


Ejemplos Probabilidad


Una moneda se lanza 2ⁿ veces. Determinar la probabilidad de que haya

un número igual de caras y sellos. Determinar la probabilidad que ocurran

un número par (impar) de caras Determinar la probabilidad de que se

tengan n caras consecutivas.


Ejemplos ProbabilidadEnumeración: 5) Probabilidad

Se distribuyen al azar 4 objetos distintos

1,2,3,4 entre 4 lugares señalados con los

números 1,2,3,4. ¿Cuál es la probabilidad de

que un objeto ocupe el lugar numerado con

su mismo número? De una urna que contiene a bolas blancas y b

bolas negras se sacan todas ellas. ¿Cuál es

la probabilidad de que parezcan al final las b

bolas negras?


Enumeración: 6) Complejidad Computacional Problema → Algoritmo → Programa

Definición de Algoritmo

Propiedades de los Algoritmos

Programa y su tiempo de ejecución

Cálculo del tiempo de ejecución de

programas

Problemas P y NP


• Un algoritmo es un procedimiento (secuencia de instrucciones) que dada cualquier instancia de un problema produce el resultado esperado.

Ejemplos: Insertion, Bubble, Merge- Sort

Dada una secuencia de números a1 …an

encontrar una permutación tal que:

a’1 ≤ a’2 ≤ ….. ≤ a’n

Enumeración: 6) Complejidad Computacional


Algoritmos “razonables” no necesariamente son correctos. La correctitud debe ser demostrada cuidadosamente.

Los algoritmos deben ser estudiados independientemente del computador en que serán implementados.

La notación O y el análisis de peor caso son herramientas que permiten determinar su eficiencia.



Correctitud: Solución del Problema

Eficiencia: Rapidez de Solución

Fácil Implementación: Recursos

Es posible conseguir las 3

anteriores simultáneamente ???




Correctitud: Algoritmos “Clásicos” : Correcto o Exacto Heurísticas : Inexactas pero … ¿ Cuánto ?

Dado un algoritmo lo primero es determinar si es correcto o no. En algunos casos es “obvio”, mientras que en otros casos es necesaria una demostración rigurosa.

Q: ¿ Cómo demostrar que un algoritmo no es correcto ?

A: Mediante demostración o contrajemplos




Correctitud: TSP Problem

Dado un conjunto de n puntos en el plano

determinar el tour de distancia mínima

que pasa una única vez por cada uno

Solución Nº 1: Nearest Neighbor TSPSolución Nº 2: 2 - Swap TSPSolución Nº 3: Optimal TSP




Eficiencia: Velocidad del AlgoritmoPara alcanzar mejores desempeños es necesario construir algoritmos más veloces, no comprar máquinas más poderosas. Para un tamaño de problema suficientemente grande, la velocidad del algoritmo será mas relevante que la velocidad del hardware.

Q: ¿ Cómo determinar la velocidad de un algoritmo ?




Eficiencia: Velocidad del Algoritmo

A: El Modelo RAM y El Análisis Asintótico del Peor Caso

El Modelo de Computación RAM (Random Access Machine) permite determinar el tiempo de ejecución de un algoritmo. Para ello considera un computador con las siguientes características:




El Modelo RAM : Cada operación simple: (ops. aritméticas, ops.

booleanas, comparaciones, acceso a memoria, etc) operaciones que toman una unidad de tiempo.

Los Ciclos y Subrutinas no son consideradas operaciones simples, sino composición de ellas.

Con ello se determina el número de operaciones elementales o simples de un algoritmo que luego se convierte a tiempo según la especificación del computador




Ejemplos: Cálculo Operaciones Según Modelo RAM Cálculo Promedio y Desviación Estándar Evaluar un polinomio de grado n en un real x Evaluar una función booleana Ordenar n números según insertion sort Intersección de 2 conjuntos Ordenar n palabras de p letras Buscar una palabra de p letras en una lista de

palabras con n p letras




El Análisis Asintótico del Peor Caso:

Al utilizar el modelo RAM es posible determinar

el tiempo de ejecución para una instancia del

problema. Sin embargo es necesario conocer

como se comporta el algoritmo en todas las

instancias. Para ello utilizamos las nociones de

mejor, promedio y peor caso.




Complejidad del Peor Caso: Es la función que define el número máximo de operaciones simples que realiza el algoritmo

Complejidad del Mejor Caso:Es la función que define el número mínimo de operaciones simples que realiza el algoritmo

Complejidad Caso Promedio:Es la función que define el número mínimo de operaciones simples que realiza el algoritmo

!Propiedades de los Algoritmos



Complejidad del Peor, Promedio y Mejor Caso: Ejemplos Cálculo del Máx o Mín de n números Producto de Matrices Algoritmo de Gauss Satisfabilidad Interpolación Polinomial y Mínimos Cuadrados Problema TSP Euclideano Problema de la Bisección del Grafo Problema de la Coloración del Grafo




Interpolación Polinomial

xi

yi p(x)

Dados n puntos (xi , yi )Encontrar un polinomio de grado (n - 1) tal que:

p( xi ) = yi para i = 1,...,n



Métodos de Mínimos Cuadrados

xi

yi

Dados n puntos (xi , yi )Encontrar la recta que mejor los “representa”:

Min [yi - ( a xi + b)]2

a,b

n

i=1

y = ax + b



Universo de Problemas

Problemas Sin

Solución

Problemas Con

Solución

Problemas NP

Problemas P



Problema

Clase P

Clase NP

Solución Exacta en Tiempo Real

Solución Aproximada en Tiempo Real

Algoritmo

ComplejidadExiste un algoritmno

que lo resuelve en tiempo polinomial

No Existe un algoritmno que lo resuelve en tiempo polinomial



Enumeración: 6) Problemas P

Problemas “Tratables” Problemas P Calculables en ≤ O(n4) Problemas P lo son para diferentes

modelos de calculabilidad (RAM, Máquina de Turing, Red Neuronal, Autómata, Programa)

Composición de Problemas P es P

Clase de Complejidad P


Enumeración: 6) Problemas NP

Problemas “Intratables” o Complejos No existe a la fecha algoritmo correcto

que los resuelva en tiempo polinomial En la práctica sólo solución

aproximada Problemas NP Calculables O(2n) Clase NP Clase P ???

Clase de Complejidad NP



Métodos Solución Problemas NP Búsqueda Combinatorial y Mejorada

Heurísticas y Metaheurísticas: Local & Greedy Heuristics Simulated Annealing Redes Neuronales Algoritmos Genéticos


Búsqueda Combinatorial

Solución por enumeración A=(a1,a2,…,an) Aplicable a problemas pequeños n 50 Enumeración de Permutaciones, Subsets, etc. Backtraking: En cada etapa se tiene una

solución parcial Ak = (a1,a2,…,ak) y se determina

el set de candidatos para Sk+1 . Si es solución

se anota, sino se sigue. Si Sk+1 = se

reemplaza ak (backtrack)



Búsqueda Combinatorial: Backtracking

Backtrack(A) {Compute S1 the set of candidate first elements of solution A ;k = 1 ;while ( k > 0 ) {

while ( Sk ) // advance // { ak = the next element from Sk

if ( A =(a1,…, ak) is a solution report it ; k = k + 1 ; compute Sk the set of candidate k-th elements of solution

A; k = k - 1 // backtrack // ; } } }

Enumeración: Problemas NP


Enumeración: Bibliografía

Discrete and Combinatorial Mathematics, R.P. Grimaldi

The Algorithm Design Manual, S. Skiena http://www.cs.sunysb.edu/~algorith/

Libros de Matemática Discreta y Combinatorial

Documents

Dr. Gonzalo HernándezFI-2 Enumeración1 Fundamentos Informática II Enumeración Combinatoria Dr. Ing. Gonzalo Hernández Oliva Universidad Técnica Federico