Arboles y S.O. de una computadora

ARBOLES

Grafo conexo que no contiene ningún ciclo,  existiendo siempre entre dos vértices una cadena .Igualmente se denomina así a un procedimiento frecuentemente utilizado para tratar problemas de enumeración y probabilidad.
Elementos de un árbol.

Raíz: Vértice del que salen uno o más arcos pero no entran
Brote: Vértice en el que termina uno o más arcos, pero del que no salen ninguno
Nodo ó raíz: Es cuando salen más arcos de los que entran
Nodo brote: Es cuando entran más arcos de los que salen
Nodo eslabón: Nodo del que salen y entran  igual cantidad de arcos
Nodo eslabón simple: Es el que entra en un arco y sale en otro


Propiedades de los arboles

A)   El grafo es conexo

B)   El grafo no tiene ciclos

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

D)   Si se agrega una arista entre dos vértices no adyacentes se forma un ciclo

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

F)   Para cada par de vértices hay una sola cadena que los conecte

El cumplimiento de dos cuales quiera de estas propiedades define a un árbol.

La figura muestra resultados  de las semifinales y finales de la competencia de tenis clásico en Wimbledom, que incluyo cuatro de los mejore jugadores de la historia de tenis.
En Wimbledom, cuando un jugador pierde sale del torneo.
Los ganadores siguen jugando hasta que queda una persona: EL campeón

SISTEMAS OPERATIVOS DE UNA COMPUTADORA


Los sistemas operativos de las computadoras modernas organizan las carpetas y los archivos usando una estructura de árbol .Una parte contiene otras carpetas de archivos .La figura muestra el explorador de Windows  con el despliegue de carpetas a  la izquierda a los archivos a la derecha a una computadora en particular .La figura ilustra la misma estructura de un árbol con raíz , la raíz desktop .Abajo de desktop esta maketo  mi computer esta tres medios floppy (A:), micro ( C:) y otras que no se muestran . Abajo de ´plug insertada, están los archivos AFF: 1132 .apl.aform.js y otros, que aparecen a la derecha de la figura .

Gráficas planas

GRAFICAS PLANAS

Tres ciudades C1,C2 y C3 deberían conectarse en forma directa mediante autopistas cada una de estas tres ciudades C1 y C6. Pueden diseñarse este sistema de carreteras de qué manera que las autopistas no se cruzan.

Una gráfica es una 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 encuentra con el problema de graficas planas.
Si una gráfica Plana conexa  se dibuja, esto se divide en regiones contiguas llamadas cara. Una cara se caracteriza por el ciclo que forma su frontera .Por Ejemplo, en la siguiente grafica la Cara A la Cara C es el ciclo  .La  cara D se considera limitada por el ciclo, La grafica por la que F EV satisface la ecuación F =E-V+2

Isomorfismo

ISOMORFISMO

Las siguientes instrucciones se dan a dos personas que no pueden ver el papel de la otra: Dibuje y etiquete 5 vertices con las sig. letras: A, B, C, D y E; conecte A con B, B con C, C con D, D con E, A con E.

B

                                                 A                                              C

                                                 E                                           D

Las graficas se aprecian en las sig figuras, sin duda estas figuras definen la misma grafica aun cuando parescan diferentes; se dice que estas graficas son isomorfas.

La grafica G1 y G2 son isomorfas si existe una función F uno a uno y sobre de los vértices G1 a los vértices G2 y aristas de G2, de manera que una arista E es incidente en V y donde G2.

Si y solo si donde la arista G(B) es incidente en F(V) y F(W) en G2. El par de funciones de F y G reciben el nombre de isomorfismo de G1 y G2.

                                  A                                                                A

                                                               

                X1                             X2                 C                                                D

         E                                                    B

X5                                         X3

                 D            X4               E                          E                                 B

                                      

Problema de los puentes de Königsberg

PROBLEMA DE LOS PUENTES DE KÖNIGSBERG


El 1er artículo referente a las teorías de graficas fue de Leonhard Euler  en 1936; el artículo recitaba una teoría general que incluía una solución a lo que ahora se llama el problema de los puentes de Königsberg.
Dos islas en el rio Pregel en Königsberg (ahora Kaliningrado, Rusia) estaban conectadas entre sí y con las orillas de rio por puentes, como se aprecia en la sig. Figura. El problema es comenzar en cualquier lugar de A, B, C o D; cruzar cada puente exactamente una vez; luego regresar al lugar de inicio.
La configuración de los puentes se puede moderar como una gráfica, como se ve en la sig. Figura; los vértices representan los lugares y las aristas representan los puentes. El problema de los puentes de Königsberg ahora se reduce a encontrar un ciclo en la gráfica de la figura que incluya todas las aristas y todos los vértices. En honor a Euler, en un ciclo una gráfica que incluye todas las aristas G se llama ciclo Euler

Construcción de las tablas lógicas para la solución de problemas

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

En esta clase de problemas se maneja otro tipo de variables. La variable lógica, esta tiene dos características fundamentales.

1.    La primera expresa una  presencia o ausencia de una relación  cierta entre dos variables y por tanto  solo pueden tomar los valores de verdadero y falso.

2.    La segunda, que son mutuamente excluyentes, es decir, que una vez que se evade una relación   cierta entre dos valores, de dos variables, no puede ocurrir otra relación verdadera  entre los valores  de ese mismo par de variables.

Esta estrategia se utiliza  para resolver problemas de dos variables cualitativas, sobre los cuales pueden definirse una variable lógica, con base a la verdad o falsedad de las relaciones entre las variables cualitativas.

Establecimiento de la existencia  y 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, por ejemplo, se crea la deducción, la intuición, la comparación, las inferencias, así como la exclusión de posibilidades, “se trata del lugar concientización de las estrategias mediante el análisis  y la verbalización de los procedimientos utilizados para llevar acabo"

Pasos de 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 y postergar la información

5.    Inferir a partir de la relación que se tiene de los datos y de la relación mutuamente excluyente

6.    Releer el problema para relacionar los datos postergados

7.    Verificar la congruencia del razonamiento que se siguió

Relaciones mutuamente congruentes

Una característica importante  de las tablas lógicas es la relación mutuamente siguiente, estas se observa cuando  determinamos la relación  entre dos 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 que también que sea verdadero.

Por ejemplo. Si decimos que Pablo trabaja como vendedor de libros y a  que Lucia le gusta la lectura queremos determinar que compro Lucia  a Pablo en tres variables, que son libros, pan o ropa. Encontramos la relación entre lectura y libros, entonces excluye toda posibilidad de que hay otra variable y que también sea cierto. 

Información incompleta

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

Es muy fácil expresar "a este problema  le hacen falta datos” o  "no se puede resolver" o "y de esto no tiene la información" y en ocasiones los alumnos dan por hecho que el problema está mal redactado o que está incompleto, pero no es así. Solo hay que ser más observador y poner en práctica nuestro pensamiento inductivo-deductivo, así como de manera sistemática  para descubrir los datos faltantes.

Diagrama de flujo

PARTES DEL DIAGRAMA DE FLUJO

Circuito de Euler y Circuito de amilton

CIRCUITO DE EULER Y CIRCUITO DE HAMILTON

Sea G un Grafo  sin vértices aislados  un circuito que tienen todas las aristas  de G recibe el nombre de circuito euleriano  un circuito euleriano es una trayectoria que empieza y termina en el mismo vértice y recorre cada arista exactamente una vez
Ej.


Teorema
Si G es un Grafo  g contiene un circuito Euleriano si y solo si

-       G es conexo

-       Cada vértice de G es de grado por

Entonces si G (un grafo) tiene un vértice  de grado no puede tener  circuito (x-x) no se repite arista  tampoco tiene grado  impar porque no se puede salir y entrar  en N par de veces.

Aristas  E-D: Grado      E=1 una entrada  y/o salida

    D=3 entrada  y/o salida

-        Trayectoria  de Euler debe comenzar  en una vértice de grado  impar y terminar en otro

TEOREMA DE EULER

Si una gráfica tiene más de dos vértices de grado sin par, entonces no puede tener una trayectoria de Euler.

Si una gráfica convexa  tiene exactamente 2 vértices de grado par, entonces tiene por lo menos una trayectoria de Euler. Cualquier circuito de Euler debe de iniciar en uno de los vértices de grados par y terminar en el otro.

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

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

c)    Una gráfica  es conexa cualquiera  de sus vértices  se puede unir por una trayectoria .Si una gráfica no es conexa se le denomina es discoteca, a los pedazos de una gráfica se les llamara componentes.

Grafo

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 en líneas.

El diagrama representativo de un grafo es una figura constituida por puntos unidos en si, por segmentos o flechas de diagramas de flujo y otros árboles son casi particulares de grafos.

Arista

Vértices extremos vértices de un grafo no orientado

Vértice

Vértice  de un grafo orientado

En ciertos gráficos se implica la dirección de las líneas como una flecha originándose  hacia los grafos no orientados

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

ARISTA

Línea que conecta dos puntos en un grafo  no orientado

Arco

Línea con dirección que conecta dos puntos en un grafo orientado

Binomio

BINOMIO

a² + 2 · a · b + b²

(a + b)² = a² + 2ab + b²
(x – y)² = x² -2xy + y²
(2x+2y)² = 4x² +8xy + y²
(3a – 2b)² = 9a² -12ab +b²
(5w+z)² = 25w² + 10wz + z²
(6m-7n)² = 36m² – 84mn + 49n²
(4b + 9c)² = 16b² + 72bc + 81c²
(7x – 2y)² = 49x² -28xy +4y²
(8z + 3w)² = 64z² + 48zw +9w²

Binomio al cubo

(a + b)³ = a³ + 3a²b+3ab²+b³

Permutaciones y Combinaciones

PERMUTACIONES Y COMBINACIONES
Selecciones ordenadas y no ordenadas

Comenzaremos con un recorrido por la combinatoria elemental contando de cuantas maneras diferentes se pueden seleccionar un cierto número de elementos de un conjunto. Para contar este número es preciso fijar los criterios que diferencian la sección de otra. Aquí tendremos en cuenta dos tipos de criterio: el orden de cada uno 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 de permutaciones. En cambio si no distinguimos dos selecciones que solo diferencia en la ordenación de sus elementos, entonces hablaremos de combinaciones. Por otra parte, si cada elemento puede aparecer como mucho una vez hablaremos de selecciones sin repetición, mientras que no hay esta restricción hablaremos de selecciones con repetición.

Permutaciones  con /repetición

 

Permutaciones sin/repetición




Combinaciones /sin repetición

Principios de conteo

PRINCIPIOS DE CONTEO

Propiedades de la multiplicación

·         Propiedad comunicativa

Cuando se multiplican 2 números el producto es el mismo sin importar el orden de los multiplicando.

Ej. 4*2 = 2*4 ó 6*5=5*6

·         Propiedad asociativa

Cuando se multiplican 3 o más números, el producto es el mismo sin importar como se agrupan los factores.

Ej. (2*3)+4 = 2*(3*4)

·         Propiedad de elemento neutro

El producto de cualquier número multiplicado por 1 es el mismo número.

Ej. 5*1 = 5

·         Propiedad distributiva

La suma de 2 números por un tercero es igual a la suma de cada sumando por el 3er número.

Ej. 4*(6+3) = (4*6)(4*3)

             36 = 24+12

               36 = 36

Propiedades de la adición.

Conmutativa

El orden  de los sumandos no altera la suma o el total, por ejemplo:

5+4=9 ó 4+5=9

Asociativa

La forma de agrupar más de 2 sumandos  no altera la suma o total, ejemplo:

(8+7)+6=21    ó     8+(7+6)=21

Elemento neutro

A cualquier número que se le adicione un cero, el resultado es el mismo, ejemplo:

9+0=9     ó     0+9=9

Ejercicios

1.    3a+2a=      5a²

2.    -5b-7b=      -12b²

3.    -a-9a=        -10a

4.    3a+5a=      8a^x-2

5.    -4a-7a=      -11a^m+1

6.    –m-3m-6m-5m=   -15m

Propiedad distributiva

a)    (3x²+8)(3-z)= 9x²-3x²z+24-8z

b)    (x²+y²)(a²-86)= x²a²-86x²+y²a²-86y²

c)    (a²b³-m⁵)(1-3x+x²)= 1a²b³-3xa²b³+a²b³x²-1m⁵-3m⁵-3m⁵x+m⁵x²