miércoles, 2 de diciembre de 2015

PERMTACION Y COMBINACIONES




Combinatoria elemental: Contando de cuantas maneras diferentes se puede seleccionar elementos de un conjunto. Para contar este número es preciso fijar los criterios de una selección a otra. Aquí tendremos en cuenta dos tipos de criterios el orden de los elementos y el número de veces que puede aparecer cada uno si distinguimos dos selecciones; cuando tienen elementos diferentes o bien cuando los elementos aparecen en un orden diferente, hablaremos de Permutaciones. En cambio sino distinguimos dos selecciones que solo difieren la ordenación de sus elementos entonces hablaremos de Combinaciones.
Si cada elemento puede aparecer por mucho una vez, hablaremos de selecciones sin repetición, mientras que si no hay esta restricción hablaremos de selecciones con repetición.
Fórmulas para permutaciones:
Con repetición   n P r = nr
Sin repetición:   n P r = n! / (n - r)!
Formulas para combinaciones:
Con repetición:    n C r = (n + r – 1)! / r! (n – 1)!
Sin repetición:        n C r = n! / r! (n – r)!

EJEMPLO:
De un grupo de 12 alumnos van a realizar un trabajo de los cuales a tres personas se les van a designar un puesto a cada una de ellas el jefe, subjefe y auxiliar.
n P r = n! / (n - r)!
n= 12                n P r = 12! / (12 - 3)! = 12! / 9!
r= 3                    =479001600 / 362880 = 1320 permutaciones

De cuantas formas pueden mezclarse los 7 colores del arcoíris tomándolos de tres en tres.
n C r = n! / r! (n – r)!
n = 7                n C r = 7! / 3! (7 – 3)! = 7! / 3! (4)!
r= 3                         = 35 combinaciones


GRAFOS


Grafos 

Es una estructura que posee elementos de una sola estructura relacionados con títulos de una misma base a estos elementos les llamaremos puntos y líneas.
El diagrama representativo de un grafo es una figura constituida por puntos unidos entre si, por segmentos o flechas.


Dirección: es ciertos grafos se indica la dirección de las líneas con una flecha. Los grafos en los que las líneas no tienen dirección se les denominan grafos no orientados.
Arista: líneas que conectan dos puntos en un grafo no orientado.
Arco: línea con dirección que conecta dos puntos en un grafo orientado.





Teoría de grafos:
Circuitos de Euler
Sea G un grafo sin vértices aislados un circuito que contiene todas las aristas de G recibe el nombre de circuito euleniano.










Teorema
Sea G un grafo, G contiene un circuito euleriano si solo si
·       G es conexo
·       Cada vértice de G es de grado par

    









                                        
Grado del vértices.
·       El grado de un vértice es el número de aristas que se encuentran en ese mismo vértice
·       Un circuito es una trayectoria que inicia y termina en el mismo vértice
·       Una gráfica es conexa si cualquiera de sus vértices se puede unir con una trayectoria.
·       Si una gráfica no es conexa se le denomina disconexa.


EJEMPLO:
·       A=2
·       B=2
·       C=3
·       D=3
·       E=1
·       F=3
·       G=2
·       H=2
·       I =2











CIRCUITO DE HAMILTON

Un ciclo hamiltoniano es un ciclo simple que contiene todos los vértices de G.
Empieza y termina en el mismo vértice y pasa por cada vértice una sola vez







CONJUNTOS

CONJUNTO

Un conjunto de elementos u objetos especificados de tal forma que se puede afirmar con certeza sin cualquier objeto dado pertenece o no a la agrupación.

Para denotar a los conjuntos se usan letras mayúsculas cuando un elemento X1permite a un conjunto A y se expresa de forma simbólica como  X,EA. En caso de que el elemento no pertenezca a este mismo conjunto se utiliza la notación X,EA .

Existen 4 formas de enunciar a lo conjuntos:
  • Por extensión o en numeración: son los elementos encerrados entre llaves y separados por comas. Ejemplo
A=  {X1,X2,X3,...X6}
  • Comprensión: Los elementos se determinan atravez de la condición que se establece entre llaves. En este caso se emplea el símbolo | . Ejemplo

A= { X | P(X)} = {X1,X2,X3,4....X6}

  • Diagramas de V: Son regiones cerradas que sirven para visualizar el contenido de un conjunto o las relaciones entre conjuntos.

  • Por descripción verbal : Es un enunciado que describe la característica que es común para los elementos. Ejemplo
Dada la descripción verbal. "El conjunto de las letras vocales" D.V

Ejemplo de las cuatro formas de enunciar un conjunto. 
  • A={ a,e,i,o,u}
  • A={X | P (A)} = { a.e.i.o.u}

  • " El conjunto de las letras vocales" 
CONJUNTOS AJENOS

Si dos conjuntos son ajenos cuando su intersección es el conjunto vacío, es decir que no tiene nada en común.
el complemento al conjunto A con respecto al conjunto universal es el conjunto A´, esto es

A´{ X E U | X E A }

EJEMPLO :

U={ mango, kiwi, ciruela, pera, naranja, cereza, manzana, sandia, durazno, platano, melon, platano}

A= { mango, ciruela, uva, naranja, manzana, sandia}

A´= { kiwi,pera, cereza, durazno, limon, melon, platano}

Este ejemplo se puede notar como :

n (A)+n(A´=n(U)

Dos conjuntos son equivalentes, si tienen la misma cabalidad y se denota por el símbolo ~  EJEMPLO:
D{ x | x son la estaciones del año }
E{ x|x es un punto cardinal }

D~E  n (D)=      n = (E)=

OPERACIONES CON CONJUNTOS

La union de los conjuntos A y B, es el conjunto de todos los elementos de A con  todo los elementos de B  sin repetir ninguno y se denota como AUB esto es

AUB{  X|X € A o X€B}

EJEMPLO:


A{mango.ciruela,uva,naranja,manzana,sandia}
B{durazno,melon,uva,naranja,sandia,platano}
AUB{mango,ciruela,uva,naranja,manzana,sandia,durazno,melon,platano}

Intersección:La intersección de los conjuntos A y B, es el conjunto de los elementos de A que también permiten a A Π B esto es:  A Π B- {x|x €A o x€B}


A{mango,ciruela,uva,naranja,manzana,sandia}
B{durazno,melon,uva,naranja,sandia,platano
AΠ B {uva,naranja,sandia}



CONJUNTO VACIÓ O NULO

En el conjunto vació o nulo es aquél que no posee elementos, se denota símbolos como ø, {}, el conjunto vacío siempre forma parte del otro, así que es un conjunto de cualquier conjunto.
EJEMPLO:

ø={ x|x son dinosaurios que viven en la actualidad}
{}= { son los hombres mas jóvenes de 300 años}
ø={x|x son números positivos menores que cero }

CONJUNTO UNIVERSAL

Es aquel  que contiene a todos los elementos bajo concideración se denota con una letra U y gráficamente se le presenta con un    .

EJEMPLO:

 U ={ x|x son los días de la semana}={lunes,martes,miércoles,jueves,viernes,sábado,domingo}
A={x|x son los días de la semana inglesa}={lunes,martes,miércoles,jueves,viernes}
B={x|x son los días de fin de semana}={sábado,domingo}

CONJUNTO FINITO

Es aquel que los elementos pueden son contados.

EJEMPLO.

J={x|x es el numero de días del mes de noviembre}
K={x|x2=4

CONJUNTO INFINITO

Es aquel cuyo elementos no pueden ser cualificados.

EJEMPLO:

N={1,3,5,7,9,...15,17}
M={2,4,6,8,...12,14}
E={x|x es la cantidad de puntos en una linea}


CONJUNTO IGUALES

Los conjuntos iguales tienen exactamente los mismo elementos se denota con el símbolo = .
EJEMPLO:

R={1,2,3,4,5,6,7..10,11}
S={x|x es un digito}

DESIGUALDAD DE CONJUNTOS

Los conjuntos son desiguales si por lo menos difieren de un elemento, es decir si no tiene exactamente los mismos elementos se denota ≠

EJEMPLO:

D={x|x2=9}
E{-2,2}
D≠E

APLICACIÓN AL ANALISIS DE ALGORITMOS

Diagrama de Flujo

Un diagrama de flujo es una representación gráfica de un proceso. Cada paso del proceso es representado por un símbolo diferente que contiene una breve descripción de la etapa de proceso. 

Los símbolos gráficos del flujo del proceso están unidos entre sí con flechas que indican la dirección de flujo del proceso.

 El diagrama de flujo ofrece una descripción visual de las actividades implicadas en un proceso mostrando la relación secuencial ente ellas, facilitando la rápida comprensión de cada actividad y su relación con las demás, el flujo de la información y los materiales, las ramas en el proceso, la existencia de bucles repetitivos, el número de pasos del proceso, las operaciones de interdepartamentales… Facilita también la selección de indicadores de proceso

 

CONSTRUCCIONDE TABLAS LÓGICAS PARA LA RESOLUCION DE PROBLEMAS

CONSTRUCCION DE TABLAS LOGICAS PARA LA RESOLUCION DE PROBLEMAS

En esta clase de problemas se maneja la variable lógica, esta tiene 2 características fundamentales.
La primera expresa una presencia o ausencia de una relación cierta entre 2 variables y por tanto solo pueden tomar los valores de verdadero y falso.
La segunda, que son mutuamente excluyentes, es decir que una vez que se da una relación cierta entre las dos variables, no pueden ocurrir otra relación verdadera entre los valores de ese mismo para de variables.
Esta estrategia se utiliza para resolver problemas de 2 variables cualitativos, sobre las cuales pueden definirse una variable lógica con base a la veracidad de falsedad de las relaciones entre las variables cualitativas.

Establecimiento de la existencia o no de una relación entre variables

A través de varios procesos de pensamiento se establece la relación o no entre las variables, p/e: se emplea la deducción, inducción, comparación, las inferencias, así como la inclusión o exclusión de posibilidades “se trata de logra la concientización de las estrategia mediante el análisis y verbalismo de los procedimientos utilizados para llevar acabo los procedimientos.
Pasos para la estrategia para resolver problemas de tablas lógicas

           Leer el problema
           Identificar las variables y la pregunta del problema
           Elaborar la tabla
           Leer el problema paso a paso, anotar o proteger la información
           Inferir otras relaciones a partir de la información mutuamente excluyente
           Releer el problema para relacionar datos postergados
           Verificar la congruencia del razonamiento que se sigue


Relaciones mutuamente excluyentes

Una característica importante de las tablas lógicas es la relación mutuamente excluyente, esta se obserba cuando determinan las relación entre variables que se conecta y verdadera esta relación excluye de las otras variables la posibilidad de que establesca una relación con ella y que también sea verdadero

Ejemplo:
Si decimos que Pablo trabaja como vendedor de libros y que a Lucia  le gusta la lectura y queremos determinar que compro  Lucia y Pablo entre variables, que son libros , pan o ropa, encontraremos la relación que entre la lectura y libros, entonces se excluye toda la posibilidad de que haya otra variable y que también sea cierta .

Informacion completa

Cuando  hablamos de información incompleta en un problema nos referimos a que elemento del texto no se encuentra todos los elementos o variables para poder resolver el problema , esto no implica que el problema no tenga una solución, simplemente hay que emplear la mente lógica para deducir que elemento o varables me hacen falta y extraerlos apartir de la información que si tengo.

Ejemplo :

Luis, Pedro y Juan tiene jugos diferentes en el receso los jugos son de : piña, melón y mora . Luis no tomo jugo de piña tampoco de mora, Pedro no tomo jugo de mora. ¿De que sabor tomo  Juan su jugo?