ARBOLES

Grafo conexo que no contiene ningún ciclo, existiendo siempre entre dos vértices una cadena.

Igualmente se denominan así a un procedimiento frecuente mente utilizado para tratar problemas de enumeración y probabilidad.

Elementos de un árbol

·         Raíz: Vértice del que sale uno o más arcos pero no entran.

·         Brote: Vértice en el que termina uno o más arcos, pero del que no sale ninguno.

·         Nodo raíz: Es cuando salen más arcos de los que entran.

·         Nodo eslabón simple: Es el que entra en arcos y salen de otro.

Arboles binarios

/Propiedades

a)      El grafo es conexo

a)      El grafo no tiene ciclos

b)      Si v es el número de vértices; v-1 será el número de aristas

c)       Si se agrega una lista entre 2 vértices no adyacentes se forma un ciclo.

d)      Si suprimimos una arista cualquiera, el grafo deja de ser conexo

e)      Para  cada par de vértices hay una sola cadena que los conecta.

El cumplimiento de 2 cualesquiera de estas propiedades define un árbol. Con frecuencia se usa un árbol raíz para especificar relaciones jerárquicas. Cuando se usa un árbol de esta manera si un vértice A esta en un nivel uno menos que el nivel de vértice B y A y B son adyacentes, entonces A esta “justo arriba” de B o B es subordinado. Un ejemplo de este tipo de árbol que es el organigrama administrativo de la organización de una Universidad hipotética mente.

GRAFICAS PLANAS

Tres ciudades C1, C2, C3 deberán conectarse en forma directa mediante autopistas con cada una de otras 3 ciudades C4, C5, C6. 

¿Puede diseñarse un sistema de manera que las autopistas no se crucen, la figura anterior ilustra un sistema d las autopistas?

Una gráfica es plana si se puede dibujar en el plano sin que sus aristas se crucen. Al diseñar circuitos impresos es deseable tener el menor número de cruces posibles; así, el diseñador de circuitos impresos se enfrenta con el problema de graficas planas. Si una gráfica plana conexa se  dibuja en el plano, este se divide en regiones contiguas llamadas caras. Una cara se caracteriza por el ciclo que forma su frontera. Por ejemplo en la siguiente grafica la cara A tiene como límite el ciclo (5, 2, 3, 4,5) el límite de la cara C es el ciclo (1, 2, 5,1). La cara exterior se considera limitada por ciclo (1, 2, 3, 4, 6,1). La grafica de la figura es igual a 4 caras, e igual a 8 aristas y 6 vértices, obsérvese que F, E y V satisfacen la siguiente ecuación.

Diagramas de flujo

El diagrama de flujo es la forma más tradicional para representar gráficamente los detalles algorítmicos de un proceso. El diagrama de flujo utiliza una serie de símbolos gráficos con un significado especial.

Bases para desarrollar diagramas de flujo

·         Todo diagrama debe tener un inicio y un fin

·         Del inicio solo puede salir un proceso

·         El fin solo puede terminar un proceso

·         Todas las figuras deben estar unidas

CONSTRUCCIÓN DE TABLAS LÓGICAS PARA LA SOLUCIÓN DE PROBLEMAS

En esta clase de problemas se maneja la variable lógica, esta tiene 2 caracteristicas 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 fals.

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 cualitativos.

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

A travez 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, asi como la inclusión o exclusión de posibilidades “se trata de logra la consientisacion 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

1.       Leer el problema

2.       Identificar las variables y la pregunta del problema

3.       Elaborar la tabla

4.       Leer el problema paso a paso, anotar o proteger la información

5.       Inferir otras relaciones apartir de la información mutuamente excluyente

6.       Releer el problema para relacionar datos postergados

7.       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 observa cuando determinamos la relación entre 2 variables que es correcta y verdadera. esta relación excluye de las otras variables la posibilidad que se establezca una relación con ellas y también sea verdadera, p/e: "Si decimos que Pablo trabaja como vendedor de libros y que a Lucia le gusta la lectura y queremos determinar que compro lucia a Pablo en 3 variables ¿Que son, libros, pan o ropa?, encontraremos la relación entre lectura y libros, entonces se excluye otra posibilidad de que haya otra variable y que también sea cierta".

INFORMACIÓN INCOMPLETA

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

Es muy fácil expresar "A este problema le hacen falta datos" o "pide esto y no tiene la información" y en ocasiones los alumnos dan por hecho que el problema esta mal redactado o incompleto pero no es así. Solo se tiene que ser mas observador y poner en practica nuestro pensamiento deductivo-inductivo, así como actuar de manera sistematica para descubrir los datos faltantes.

GRAFO

Es una estructura que posee elementos de una sola estructura, relacionados por vínculos 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 sí, por segmentos o flechas. Los diagrama de flujo y los árboles son casos particulares de grafos.

DIRECCION: En ciertos gráficos se inserta la dirección de las líneas con una flecha, originándose hacia los grafos no orientados.

Los gráficos en los que las líneas no tienen dirección se le denominan gráficos no orientados.

ARISTA: línea que conecta dos puntos en un grafo no orientado

ARCO: línea con dirección que conecta con 2 puntos en un grafo orientado.

GRADO DE UN VERTICE

a)      El grado de un vértice es el número de aristas que se encuentran en ese vértice

b)      Un circuito es una trayectoria que inicia y termina en el mismo vértice

c)       Una gráfica es conexa si cualquiera de sus vértices se pueden unir con una trayectoria, si una gráfica no es conexa se le denominara DISCONEXA, a los pedazos de una gráfica se le denominara componentes

TEORIA DE GRAFOS

Circuitos de Euler y circuitos de Hamilton sean un G un grafo sin vértice aislados un circuito que contiene todas las aristas de G recibe el nombre de circuito euleniano.

Un circuito euleriano es una trayectoria que empieza y termina en el mismo vértice y recorre cada arista exactamente una vez.

TEOREMA: Son grafos

G contiene un circuito euleriano si y solo si

·         G es conexo

·         Cada vértice de G es de grado par

RECURSIVIDAD

Los bucles son unos de los pilares fundamentales de la programación, sin embargo, esto es posible construir programas sin utilizarlos. Algunos lenguajes no tienen alguna construcción explicita de bucles a diferencia del for, while, etc; si no que utilizan una técnica de programación conocida como recursividad.

Esta resulta ser una técnica muy poderosa para la solución de determinados problemas.

La recursividad significa aplicar una función como parte de la definición de esa misma función, la clave  de funcionamiento es que obligatoriamente debe de existir una condición terminal con el objeto de que la función se divulgue hacia una resolución no recursiva en algún punto, de lo contrario la función entra en un bucle infinito y nunca finaliza.

La matemática factorial se define como el producto de todos los números hasta el argumento inducido. El factorial de 1 es 1, si suponemos un poco nos daremos cuenta que tenemos otra manera de expresar esta función. El factorial de n es igual a n veces el factorial de n-1, por lo tanto…

1!=1

2!= 1*2=2

3!= 1*2*3=6

N!= 1*2*3*….(N-2)*(N-1)*N….

ORDENADAS Y NO ORDENADAS

Comenzaremos con un recorrido por la combinatoria elemental contando diversas maneras se puede seleccionar un cierto número de elementos de un conjunto, para contar este número es preciso fijar los criterios de una selección a otra, aquí tendremos en cuenta 2 tipos de criterio, ele orden de los elementos y el número de veces que puede aparecer cada uno.

Si identifico 2 selecciones: Cuando tienen elementos diferentes o bien, cuando los elementos aparecen en un orden diferente hablaremos de permutaciones .En cambio si no distinguimos 2 selecciones que solo difieren en la ordenación de sus elementos, entonces hablaremos de combinaciones. Por otra parte, si cada elemento puede aparecer muchas veces, hablaremos de selecciones sin repetición, mientras que si no hay restricciones hablaremos de selecciones sin repetición. 

Podemos formar 16 permutación con repetición de 2 elementos

Puede repetirse 2 de los elementos pero solo una vez sin importar el orden

12 Permutaciones, sin repetición  de 2 elementos

No pueden repetirse los elementos y no importa el orden de los elementos

10 Combinaciones, con repetición de 2 elementos

6 Combinaciones, sin repetición de 2 elementos

No se repiten los elementos

FORMULAS 

Permutacion c/repetición: nPr=nʳ

      Permutacion s/repetición: nPr= n!/ (n-r)!

Combinaciones s/repetición: nCr=n!/r!(-n-r)!

Combinación c/repetición: n(r-(n+r-1)!/r!(n-1)!

PROPIEDADES DE LA ADICIÓN

·         Propiedad conmutativa: El orden de los factores no alteran la suma o el total, p/e: 5+4=9  4+5=9

·         Propiedad Asociativa: La forma de agrupar más de 2 sumandos no altera la suma o total, p/e: (8+7)+6=21   8+(7+6)=21

·         Propiedad de elemento neutro: A cualquier número que se le adicione un 0 el resultado es el mismo, p/e: 9+0=9   0+9=9

PROPIEDAD DISTRIBUTIVA

La propiedad distributiva de la multiplicación respecto a la suma o la resta es aquella por la que de dos o más números de una suma (o resta), multiplicada por otro número, es igual a la suma (o resta) de la multiplicación de cada término de la suma (o la resta) por el número.

a · (b + c) = a · b + a · c

2 · (3 + 5) = 2 · 3 + 2 · 5

2 · 8 = 6 + 10

16 = 16

SISTEMAS NUMERICOS

Un sistema numérico es un conjunto de símbolos y reglas que se utilizan para representar datos numéricos o cantidades. Se caracterizan por su base que indican el numero de símbolos distinto que utiliza y ademas es el coeficiente que determina cual es el valor de cada símbolo dependiendo de la posición que ocupe. Estas cantidades se caracterizan por tener dígitos enteros y fraccionarios. 

Sistema decimal 

Este sistema se maneja cotidianamente y esta formado por diez símbolos {0,1,2,3,4,5,6,7,8,9} por lo tanto la base del sistema es de diez (10).

Sistema binario

Es el sistema que se utiliza internamente en el hardware de las computadoras actuales, se basa en la representación de cantidades utilizando los dígitos 1 y 0, por lo tanto su base es 2 (numero de dígitos del sistema).Cada dígito de este sistema se denomina bit. 

Sistema octal

Este sistema utiliza ocho símbolos o dígitos para representar cantidades y cifras numéricas, los dígitos son: {0,1,2,3,4,5,6,7}; la base de este es ocho (8) este es un sistema que se puede convertir directamente a binario. 

Sistema hexadecimal 

Este sistema utiliza 16 dígitos y letras para representar cantidades y cifras numéricas, los símbolos son {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}, la base de este sistema es dieciséis (16). 

Conversiones 

Sistema decimal- Sistema binario

Consiste en dividir la cifra decimal entre 2, hasta que la cifra ya no sea divisible. Al final se unen todos los residuos comenzando por el final y uniendo también el ultimo cociente 

EJEMPLO:

.

Sistema binario - Sistema octal

Se pueden convertir muy fácilmente del sistema binario al octal, gracias a que cada grupo de 3 bits binarios corresponden exactamente a un dígito en octal, los binarios se agrupan entonces de tres en tres.

Sistema hexadecimal- Sistema binario
Esta conversión se realiza a partir de una tabla colocando los números en binario correspondientes al numero hexadecimal. 

Sistema decimal- Sistema Octal

Esta conversión consiste en dividir la cantidad decimal entre 8, hasta que la cifra ya no sea divisible. El resultado se coloca de derecha a izquierda comenzando por el ultimo cociente, seguido de los residuos. 

Sistema decimal- Sistema hexadecimal

Esta conversión consiste en dividir la cantidad decimal entre 16, y colocar los residuos de derecha a izquierda colocando los numero y las letras correspondientes de acuerdo a la tabla mostrada en la parte de arriba. 

COMPLEMENTO A1/A2

Calculo del opuesto en complemento A1, el compuesto de un numero en complemento A1 es su complemento A1.

Complemento A2

El complemento A2 de un numero binario se obtiene tomando el complemento A1 y sumándole 1 al bit menos significativo.

Regla de la suma binaria

0+0=0

1+0=1

0+1=1

1+1=0 y se lleva un acarreo.

CONJUNTOS

Un conjunto es un grupo de elementos u objetos especificados en tal forma que se puede afirmar con certeza si cualquier objeto dado pertenece o no a la agrupación. Para denotar a los conjuntos se usan letras mayúsculas, cuando un elemento X1 pertenece a un conjunto A se expresa de forma simbólica como X1 E A. En caso de que un elemento no pertenezca a este mismo conjunto se utiliza la notación X1 E A.

Existen cuatro formas de enunciar a los conjuntos.

1.- Por extensión o numeración: Los elementos  son encerrados entre llaves y separados por comas.

Ejemplo: {X1, X2, X3....... Xn}

2.- Por comprensión: Los elementos se determinan a través de una condición que se establece entre llaves. En este caso se emplea el símbolo "Tal que".

Ejemplo: {X| P(x)} = { X1, X2, X3.....Xn}

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

4.- 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", expresando por extensión, comprensión y por diagrama de Venn.

Si cada elemento de un conjunto A es también un elemento del conjunto B, se dice que A es un subconjunto de B la notación es A ⊂ B, que significa que A esta incluido en B y se lee: A es subconjunto de B. Si no todos los elementos de un conjunto A son elementos del conjunto B, se dice que A no es un subconjunto de B, su notación es:

 A  B, lo cual significa que A no es un subconjunto de B.

Conjunto Finito

Es aquel cuyos elementos pueden ser contados.

Ejemplo: 

J={X|X es el numero de días del mes de noviembre}

K={X|X²  = 4}

L={X|X es la cantidad de autos en el df}

Conjunto infinito

Es aquel cuyos elementos no pueden ser cuantificados.

Ejemplo:

N={1,3,5,7,9....}

M={2,4,6,8,10....}

E={X|X es la cantidad de puntos en una linea}

Conjuntos iguales

Dos conjuntos son iguales si tienen exactamente los mismos elementos y se denota con el símbolo =.

Ejemplo:

R={1,2,3,4,5,6,7}

S={Es un dígito}

Desigualdad de conjuntos

Dos conjuntos son desiguales si por lo menos difieren en un elemento, es decir, si no tienen exactamente los mismos elementos y se denota con el símbolo: ≠.

Ejemplo:

D={X|X²=9}

D≠ E

Conjuntos equivalentes

Dos conjuntos son equivalentes si tienen la misma cantidad de elementos, es decir, si posee la misma cardinalidad y se denota por el símbolo:     ͌

Ejemplo:

D={X|X Son las estaciones del año}           D    ͌   E         n (D)=4

E={X|X Es un punto cardinal}                                            n (E)=4

Operaciones con conjuntos

La unión de los conjuntos A y B, es el conjunto de todos los elementos de A con todos los elementos de B sin repetir ninguno y se denota como: A ∪ B. 

Esto es : A ∪ B = {X|X ∈ A o X ∈ B}.

Intersección 

La intersección de dos conjuntos A y B, es el conjunto de los elementos de A que también pertenecen a B que se denota como A ∩ B.

Esto es: A ∩ B = {X|X ∈ o X∈ B}.

Conjuntos Ajenos

Dos conjuntos son ajenos cuando su intersección es el conjunto vació, es decir, que no tienen nada en común. 

Esto es: 

A ∩  E= {}

A ∩  E= Æ

Complemento

Es el complemento del conjunto A con respecto al conjunto universal, es el conjunto de todos los elementos de U que no están en A y se denota como A'.

Esto es: A'={X∈ U| X ∉  A}.

Diferencia de conjuntos

La diferencia de conjuntos A y B  (es ese orden) es el conjunto de los elementos que pertenecen a A y no pertenecen a B y se denota como A-B 

Esto es: A-B ={X|X ∈ A y X ∉ B}.