Asignacion Implicita

Capítulo 12

¿Cuándo ocurre una asignación implícita?

Cuando se declara un objeto y se le inicializan con los valores almacenados en otro objeto de la misma clase por medio de un método constructor.

Si se tiene la siguiente declaración de objetos de la clase Ejemplo: 

Ejemplo Objeto1(Objeto2); o Ejemplo Objeto1=Objeto2;

Se puede observar que ocurre una asignación en forma implícita del Objeto2 al Objeto1. Cuando se invoca una función libre o un método y se le envía un objeto como argumento (por valor) se genera una copia local del argumento que se recibe, se dice que el parámetro formal de la función se le asigna en forma implícita, el valor del argumento de la llamada. Cuando una función genera como salida un objeto, se genera otro pero temporal en el que se regresa el resultado de la función o método.

Constructor Copy Constructor

Un caso similar al de la asignación explicita  ocurre con los constructores de objetos que poseen atributos dinámicos. Es necesario definir un constructor especial (Copy Constructor) cuaya labor será inicializar el nuevo objeto, asignándole el contenido del objeto (de la misma clase) que recibe como parámetro.

¿Cómo funcione el Copy Constructor?

El concepto, y la forma en que trabaja, es básicamente igual a la del operador de asignación. La diferencia esta en que, al ser un método constructor, se aplica directamente sobre el objeto en creación, sin generar ninguna salida.

¿Qué implicaciones a nivel de memoria existen al utilizar una función que regresa una referencia?

Cuando se usa una referencia en el tipo de resultado de la función, el compilador no genera una réplica del objeto por regresar como resultado de la función.

Apuntador this

Cada vez que un método se ejecuta, en forma implícita existe una referencia (apuntador) al objeto sobre el que se aplica dicho método. La referencia se llama this y es un apuntador que almacena la dirección del objeto sobre el que se aplica el método. Este apuntador lo define internamente el compilador y, generalmente, se maneja en forma implícita.

class Ejemplo

{ private:

   Int atributo;

  public:

    Void Escribe() {cout << atributo; }

}:

 ¿Qué es una referencia?

Una referencia es un alias de una variable u objeto. Ya se han utilizado referencias al definir parámetros por referencia en una función. Estos parámetros, en forma conceptual, se vuelven un alias de las variables enviadas como argumento durante la ejecución de la función correspondiente.

El concepto de referencia puede ser utilizado para indicar que una función regresara como resultado una referencia a una variable u objeto. La sintaxis para indicar que la función regresara una referencia, es colocar al final del tipo de dato de la función un &.

Árbol Heap

¿Ques es un arbol heap?
basicamente, un heap es un arbol binario casi completo. Se le considera casi completo ya que se lleno en todos sus niveles,exepto, problamente, el ultimo que se va completando izquierda a derecha. la diferencia entre el arbol binario y heap es que en el segundo cada nodo tiene un valor menor o igual(o bien mayor o igual) que el valot asociado cada io de us hijos, lo que se conoce como condicio del heap.


¿Como diseñar el TDA que corresponde al arbol heap?


en el  diseño del TDA para un heap se debe considerar que los elemntos que se almacenaron deben poseer la propiedad de ordenamiento, es decir, tener una relacion de mayor que y menor que.


Elemento: los elementos de un arbol heap son nodos. cada uno contiene un datos(simple o estructura tipoinfo) unico en el arbol.
Estructura: un arbol heap posee una estructura jerarquica(a expecion del arbol vacio). cada nodo contine un elemento de un conjunto ordenado valores; los nodos forman un arbol binario completo, de tal formaque cada padre contiene un elemento de mayor prioridad que sus dos hijos(la prioridad se establece con relacion a los valores almacenado, es decir, a menor valor, mayor prioridad, o a  mayor, menor prioridad). La relacion de la prioridad se puede establecer como mayor o mayor-igual.



En un montículo de prioridad, el mayor elemento (o el menor, dependiendo de la relación de orden escogida) está siempre en el nodo raíz. Por esta razón, los montículos son útiles para implementar colas de prioridad. Una ventaja que poseen los montículos es que, por ser árboles completos, se pueden implementar usando arreglos, lo cual simplifica su codificación y libera al programador del uso de punteros.


¿Como genera un arbol heap a partir de un arreglo de elemento?

Esta operación parte de un elemento y lo inserta en un montículo aplicando su criterio de ordenación.Si suponemos que el monticulo está estructurado de forma que la raíz es mayor que sus hijos, comparamos el elemento a insertar (incluido en la primera posición libre) con su padre.Si el hijo es menor que el padre,entonces el elemento es insertado correctamente, si ocurre lo contrario sustituimos el hijo por el padre.

¿Y si la nueva raíz sigue siendo más grande que su nuevo padre?. Volvemos a hacer otra vez dicho paso hasta que el montículo quede totalmente ordenado. En la imagen adjunta vemos el ejemplo de cómo realmente se inserta un elemento en un montículo. Aplicamos la condición de que cada padre sea mayor que sus hijos, y siguiendo dicha regla el elemento a insertar es el 12. Es mayor que su padre, siguiendo el método de ordenación, sustituimos el elemento por su padre que es 9 y así quedaría el montículo ordenado.

Ahora veremos la implementación en varios lenguajes de programación del algoritmo de inserción de un elemento en un montículo.

¿Como se utilza  una estructura Heap en una cola priorizada?


Si se considera que cada uno de los elementos en un heao tiene asociada una prioridad que depende de su valor(a menor valor, mayor prioridad), entoeces el elemento de mayor prioridad siempre estará en la raíz del árbol y los elementos que le siguen en estas caracteristicas estarán cerca de el.


Cuando se desee insertar un nuevo elemento en la cola priorizada, lo mas sencillo sera agregarlo como la ultima hoja del árbol, es decir, en la primera posición es libre del ultimo nivel.

Apuntadores y Memoria Dinámica

Que es un apuntador?

Un apuntadora se define como un tipo de dato capaz de almacenar una dirección de memoria. se considera como referencia indirecta a un elemento.

Los apuntadores pueden ser un tipo de dato especial dentro del lenguaje de programación en cuyo caso, guardaran direcciones de memoria real; o bine, el programador puede simular el funcionamiento de un apuntador, por ejemplo, cuando una variable de tipo entero guarda la posición (subindice) de un dato en un arreglo.

Que es la memoria Dinámica?

Muchos lenguajes de programación permiten manejar dos tipos de almacenamiento de datos en la memoria principal: el almacenamiento estático (automático) y el almacenamiento dinámico.

La memoria estática es la que se maneja tradicionalmente. Sus principales características son:

• 
  
• Se define explicitamente al declrar una variable, ya sea global o local.
• El compilador genera automáticamente el espacio de memoeria.
• Se mantiene fija durante toda la vida de la variable (independientemente de que se utilice o no).

La memoria dinámica permite crear y destruir espacios de memoria, según indicaciones explicitas del programador durante la ejecución del programa. Sus principales características son:

• Utiliza una parte de la memoria principal denominada heap.
• Apoya el uso eficiente de la memoria durante la ejecución.
• Requiere apuntadores que almacenan direcciones de memoria real, dado que estas se asignan dinamicamente.

Representación de un estructura de Datos

Que es la representación de un estructura de datos?

Basiamente, puede entenderse como el punto de conexion entre la especificacion logica de un TDA (Tipo de Dato Abstracto) y su implementacion en un lenguaje de programacion particular. Dentro del proceso de abstraccion de datos, la representacion de un estructura corresponde al inciio del segundo nivel de abstraccion, es decir, el nivel fisico. Esta etapa construye un esquema de como se almacenaran los elementos de la estructura de datos en la memoria, de tal forma que se logre su optimo aprovechamiento.

Que tipos de representaciones existen para una estructura de datos?

Independientemente de las facilidades de implementacion que ofrezcan los lenguajes de programación, una estructura de datos (TDA) puede representarse de dos formas.

por posiciones (almacenamiento contiguo).

por ligas (almacenamiento disperso)

Como funciona la representación de una estructura de datos por posiciones?

En este tipo de representación, el lugar físico donde se almacena un elemento, determina automáticamente su posición relativa en la estructura de datos. Básicamente, se puede pensar en ella como un espacio de almacenamiento contiguo donde cada lugar sirve para almacenar un elemento, de tal forma que si un elemento esta almacenado en el lugar K, tendra la k-esima posición dentro de la estructura y, obviamente, el elemento K + 1 estará ubicado exactamente después del K y se almacenara en el lugar K + 1 del espacio de almacenamiento. esta representación en el próximo gráfico.

Como funciona la representación de una estructura de datos por ligas?

En este tipo de representación la ubicación fisica de un elemento no determina la posición relativa que tiene dentro de la estructura de datos. El almacenamiento en este tipo de representación se realiza en forma dispersa, es decir, dos elementos contiguos en la estructura de datos no necesariamente deben estar almacenados físicamente en posiciones contiguas dentro del espacio de almacenamiento, como se muestra en la siguiente figura.

Conjuntos


el conjunto es una estructura fundamental en las matemáticas  que se emplea para agrupar conjuntos. Los objetos de un conjunto se denominan elemento o miembro del conjunto. Estos elementos se toman de un conjunto universal U, que contiene todos los posibles elementos del conjunto. El numero de elementos contenidos en un conjunto S se conoce como el cardinal de S, denotado por |1|. Por ejemplo, el conjunto de números primos positivos menores que 20 puede expresarse como
                                                                                                          S={2, 3, 5, 7, 11, 13, 17 ,19}
Otra forma de representar un conjunto es utilizar notación de constructor de conjunto, tiene la forma
                                                                                                        S={x|x es un numero primo positivo<20}
Usamos esta notación, un elemento se dice que es miembro del conjunto S si tiene una de las propiedades asociadas con x. De este modo, otra forma de representar el conjunto de números primos positivos menores que es 20.


La pertenencia a conjunto se denota por a ∈ A que establece  que a es miembro del conjunto A. El cojunto espcial que no tiene elemento se le denomina conjunto vacio y se denota ∅. se dice que  es un subconjunto de B, escrito como A ⊆ B, que nos dice que cada elemento de A es elemento de B. si Ay B son conjuntos, entonces la union de ellos, se denota  A∪B, es aquellos elementos que esta A o en B, o en ambos. L interseccion de A y B, se denota por  A∩B, es el conjunto que contiene aquellos elementos  que  estan en A y en B. la diferencia A y B, denota por A~B, es el conjunto que contiene aquellos  que estan en A pero no en B, 


 si nos referimos a a una coleccion de n elementos de esta forma como una n-tuppla ordenada.Contretamente, uno n-tupla ordenadas. las 2-tuplas se conoce como pares ordenados.


El producto cartesiano de dos conjuntos A y B, denotado por A*B, es el conjunto de todos los pares ordenado (a,b) tales a∈A y b ∈B


Numeración


Las siguientes reglas básicas de numeración subyacen toda la combinatoria:


REGLA DE LA SUMA. el numero de formas de escoger único elemento de dos conjunto disjuntos viene dado por la suma por la suma de los cardinales de los conjuntos.


REGLA DEL PRODUCTO. el numero de forma de escoger un elemento de un conjunto y segundo elemento de otros conjuntos viene dado por el producto de los cardinales de los conjuntos

En combinatoria, la regla del producto es una regla de recuento básica. (véase regla de la suma). Enunciada de manera simple, es la idea de que si algo puede hacerse de a formas y otra cosa puede hacerse de b formas, entonces hay a · b formas de hacer ambas cosas. Así, elegir un elemento de {A, B, C} y otro de {X, Y} es elegir un elemento de {AX, AY, BX, BY, CX, CY}. En este ejemplo la regla dice: multiplicando 3 por 2 se obtiene 6.

Los conjuntos {A, B, C} y {X, Y} en este ejemplo son conjuntos disjuntos, pero eso no es necesario. El número de formas de elegir un miembro de {A, B, C}, y después elegir otro, o sea, elegir un par ordenado de elementos elegidos de {A, B, C}, es 3 × 3 = 9.

En la teoría de conjuntos, este principio de multiplicación se toma a veces como la definición del producto de cardinales. Así,

donde X es el producto cartesiano. Estos conjuntos no tienen por qué ser finitos, ni tampoco es necesario que haya un número finito de factores en el producto (véase número cardinal)

Un ejemplo clásico de esta regla en computación, es la ejecución de dos ciclos for anidados.

Teoría de probabilidad elemental

La teoría nos permite calcular la probabilidad de sucesos concretos si asumimos  que estos sucesos están  gobernados por un conjunto de axiomas apropiado. Primero definimos el espacio de probabilidad, que es el conjunto U cuyos elementos se denominan sucesos elementales. Especificar distribucion de probabilidad Pr() que asigne una probabilidad a cada uno de estos sucesos específicos x⊆U se denota por Pr(x). Para nuestros propósitos, la distribución de probabilidad mas importante es la distribución uniforma discreta. EN esta distribución cualquier suceso elemental x∈ U es equiprobabilidad (i.e., Pr(x)= 1/|U|)

SI algún suceso esta compuesto de sucesos elementales independientes (i.e. la probabilidad de un suceso elemental no depende de si algún otro suceso se ha producido), entonces la probabilidad del suceso viene dada por  el producto de los suceso elementales que incluye. La variable aleatoria  es una función definida sobre los sucesos de un espacio de probabilidad.


GRAFOS

Grafo

Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que , tal que . Para simplificar, notaremos la arista (a,b) como ab.

En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.

Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad

Grafos simples 

Un grafo es simple si a lo sumo sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.

Un grafo que no es simple se denomina GRAFO COMPLEJO.. Un grafo simple está formado por dos conjuntos:

• Un conjunto V de puntos llamados vértices o nodos.

• Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados.

De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, Grafos conexos [editar]

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

• No dirigidos: son aquellos en los cuales los lados no están orientados (No son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).

• Dirigidos: son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <Vi ,Vj>!=<Vj ,Vi>. En grafos dirigidos, para cada lado <A,B>, A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino, se conoce como cabeza del lado.

Que a su vez se subdivide 

• Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.

Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular

• Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto

Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es

• Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota .

• Un grafo bipartito regular: se denota donde m, n es el grado de cada conjunto disjunto de vértices.

• Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.

• Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

ARBOLES

Un Árbol Binario es un conjunto de finito de Elementos, de nombre Nodos de forma que:

El Árbol Binario es Vació si no tiene ningún elemento en el.

El Árbol Binario contiene un Nodo Raíz y los dos que parten de él, llamados Nodo Izquierdo y Nodo Derecho.

Los Árboles tiene 3 Recorridos Diferentes los cuales son:

Pre-Orden

In-Orden

Post-Orden

Pre-Orden

Definición:

El Recorrido “Pre-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en la Raíz, después viaje a través del Nodo Izquierdo y después a través del Nodo Derecho.

Detalle:

Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y viajara a través de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elemento correspondiente.

Arboles de Busqueda

Capitulo 9

¿Por qué es importante el balanceo en un árbol de búsqueda?

La manera en que los elementos estén distribuidos en un árbol de búsqueda determinara su altura y, en consecuencia, la cantidad de comparaciones a realizar al buscar un elemento. Lo ideal sería que el árbol tuviera sus elementos distribuidos en forma equilibrada o balanceada, consiguiendo así la mayor eficiencia que ofrece la búsqueda binaria.

¿Cuál es el número máximo de comparaciones que se realizan en el peor caso de búsqueda en un ABB?

La cantidad máxima de comparaciones al realizar una búsqueda en un ABB está determinada por la altura del árbol.Si un BB degenera en una lista, se tiene un árbol cuya altura es igual a la cantidad de nodos en el árbol.

¿Qué es un árbol balanceado?

Se considera que un árbol esta balanceado cuando todos sus niveles, excepto el ultimo, están integrados a la máxima capacidad de nodos.

¿Qué es un árbol AVL?

Un árbol AVL es un árbol binario de búsqueda que trata de mantenerse lo más balanceado posible, conforme se realizan operaciones de inserción y eliminación. Fueron propuestos en 1962 por los matemáticos rusos Adelson-Velskii y Landis.

En estos se debe cumplir el hecho de que para cualquier nodo del árbol, la diferencia entre las alturas de sus subárboles no exceda una unidad.

Busqueda de Informacion

Capitulo 7

¿Por qué es importante la búsqueda de información?

Uno de los propósitos de la computadora es que sirva de medio para el almacenamiento de grandes volúmenes de información, lo que implica la existencia de mecanismos para accesar eficientemente a esta última.

¿Cómo realizar eficientemente una búsqueda?

Un requisito importante para que el proceso de búsqueda se realice en forma eficiente es que la información este ordenada, por lo que se plantea una representación y un método de acceso para que la información se almacene ordenadamente y se facilite la búsqueda.

Para ordenar la información es necesario realizar el ordenamiento según uno o varios de los campos que conforman cada registro de información. Este campo se llama Llave.

¿Qué opciones de representación en memoria existen para una estructura de datos para la búsqueda de información?

Si se desea utilizar una estructura temporal y limitada, para obtener accesos rápidos, se deberá pensar en la memoria principal. Si se desea utilizar una estructura permanente e ilimitada para almacenar grandes volúmenes de información, se deberá pensar en la memoria secundaria.

En memoria estática se puede utilizar un arreglo que guarde la información en forma ordenada. Esta representación se conoce con el nombre de tabla.

En memoria dinámica se puede utilizar una lista encadenada que guarde ordenadamente la información. Esta representación se llama lista ordenada.

¿Cómo se puede implementar el proceso de búsqueda en una estructura lineal?

Búsqueda secuencial: es el algoritmo más obvio y el que tiene una implantación intuitiva. Consiste en comparar a partir de del primer elemento de la estructura, secuencialmente hasta que el elemento buscado se encuentra, o un elemento mayor al buscado.

Búsqueda binaria: consiste en dividir sucesivamente la estructura en mitades, descartando del proceso de búsqueda la mitad en que no se puede encontrar el elemento que se busca. El proceso parte la estructura en mitades cada vez más pequeñas, lo que asegura que se encuentre el elemento.

Programación Orientada a Objetos

La programación orientada a objetos o POO, es un paradigma de programación que usa objetos y sus interacciones, para diseñar aplicaciones y programas informáticos. Está basado en varias técnicas, incluyendo herencia, abstracción, polimorfismo y encapsulamiento. Los conceptos de la programación orientada a objetos tienen origen en Simula 67.

La programación orientada a objetos es una forma de programar que trata de encontrar una solución a estos problemas. Introduce nuevos conceptos, que superan y amplían conceptos antiguos ya conocidos. Entre ellos destacan los siguientes:

Clase: definiciones de las propiedades y comportamiento de un tipo de objeto concreto.

Polimorfismo: comportamientos diferentes, asociados a objetos distintos, pueden compartir el mismo nombre, al llamarlos por ese nombre se utilizará el comportamiento correspondiente al objeto que se esté usando. O dicho de otro modo, las referencias y las colecciones de objetos pueden contener objetos de diferentes tipos, y la invocación de un comportamiento en una referencia producirá el comportamiento correcto para el tipo real del objeto referenciado. Cuando esto ocurre en "tiempo de ejecución", esta última característica se llama asignación tardía o asignación dinámica. Algunos lenguajes proporcionan medios más estáticos (en "tiempo de compilación") de polimorfismo, tales como las plantillas y la sobrecarga de operadores de C++.

Herencia: las clases no están aisladas, sino que se relacionan entre sí, formando una jerarquía de clasificación. Los objetos heredan las propiedades y el comportamiento de todas las clases a las que pertenecen. La herencia organiza y facilita el polimorfismo y el encapsulamiento permitiendo a los objetos ser definidos y creados como tipos especializados de objetos preexistentes. Estos pueden compartir (y extender) su comportamiento sin tener que volver a implementarlo. Esto suele hacerse habitualmente agrupando los objetos en clases y estas en árboles o enrejados que reflejan un comportamiento común. Cuando un objeto hereda de más de una clase se dice que hay herencia múltiple.

Abstracción: denota las características esenciales de un objeto, donde se capturan sus comportamientos.Cada objeto en el sistema sirve como modelo de un "agente" abstracto que puede realizar trabajo, informar y cambiar su estado, y "comunicarse" con otros objetos en el sistema sin revelar cómo se implementan estas características. Los procesos, las funciones o los métodos pueden también ser abstraídos y cuando lo están, una variedad de técnicas son requeridas para ampliar una abstracción.El proceso de abstracción permite seleccionar las características relevantes dentro de un conjunto e identificar comportamientos comunes para definir nuevos tipos de entidades en el mundo real. La abstracción es clave en el proceso de análisis y diseño orientado a objetos, ya que mediante ella podemos llegar a armar un conjunto de clases que permitan modelar la realidad o el problema que se quiere atacar.

Encapsulamiento: Significa reunir a todos los elementos que pueden considerarse pertenecientes a una misma entidad, al mismo nivel de abstracción. Esto permite aumentar la cohesión de los componentes del sistema. Algunos autores confunden este concepto con el principio de ocultación, principalmente porque se suelen emplear conjuntamente.

ESTRUCTURA DE DATOS LINEALES PARA BUSQUEDA DE INFORMACION

¿Como realizar eficientemente una busqueda?

para ordenar la informacion es necesaria el ordenamiento segun uno (varios) de los campos  que conforman cada registro de informacion. El campo que determina el ordenamiento d se denomina llave, ya que distingue de manera  únicamente registro.

 La llave puede ser simple, si  se forma  con un solo campo(como ka matricula de un alumno en la universidad)

 o  compuesta, se forma por varios campos (nombre, apellido y dirección de una persona), por lo que la estructura  de datos para la búsqueda  de información no se guardara información repetida.

¿Que opciones de representacion en memoria  existen para una estructura de datos para la busqueda de infomracion?

Si se deasa  utilizar una estructura temporal y ilimitado, para obtner accesis rapidos, se debera pensar en memoria principales.

si se desea utilizar una estructura permanente e ilimitada para almacenar grades volumenes de informacion, se deberia utilizar la memoria  secundaria.

Posibles representaciones lineales en memoria principales en la memoria  estatica se puede utilizar un arrelge  que guarde la informacion en forma ordenada. esta representacion , tipicamente, se conoce con el nombre de tabla.

En memoria dinamica se puede utilizar  una lista encadenadas  que  guarde ordenadamente la informacion.  Esta  representacion, generalment se llama lista Ordenadas.

¿como se pueden implementar el proceso de búsqueda en una estructura lineal?

 La busqueda secuencial:

• Los algoritmos de búsqueda lineal y binaria son 2 de los algoritmos más usados para encontrar elementos en una estructura de datos.La búsqueda lineal probablemente es sencilla de implementar e intuitiva. Básicamente consiste en buscar de manera secuencial un elemento, es decir, preguntar si el elemento buscado es igual al primero, segundo, tercero y así sucesivamente hasta encontrar el deseado. Entonces este algoritmo tiene una complejidad de O(n).

La búsqueda binaria:

• Si la tabla de números está ordenada, por ejemplo, en orden creciente, es posible utilizar para la búsqueda un algoritmo más eficiente que se basa en un concepto muy utilizado en la programación: dividir para vencer.
  Si está ordenada la tabla y miramos el número situado en la mitad para ver si es mayor o menor que el número buscado (o con suerte igual), sabremos si la búsqueda ha de proceder en la subtabla con la mitad de tamaño que está antes o después de la mitad. Si se repite recursivamente el algoritmo al final o bien encontraremos el número sobre una tabla de un sólo elemento o estaremos seguros de que no se encuentra allí.
  
  
  
  
  
  

STRINGS

¿Que es un string y por que es importante su análisis?

Las palabras string hace referencia a una cadena de caracteres. Su estudio cobra importancia cuando se toma en consideración que la mayor parte de la información que se maneja actualmente en casi cualquier área del conocimiento, puede verse como una secuencia de caracteres. El nombre de una persona, el contenido de un libro, la información  presentada en un texto puede ser vistas como una cadena de caracteres o string. Esto nos lleva a pensar que un string debe definirse como una estructura de datos y por ello es conveniente que se diseñe inicialmente un TDA.

¿ De que firma concptualizar un string como un TDA?

Se puede diseñar muchas TDA que definan un string considerando que  operaciones se tomaran como basicas para el funcionamiento de dicha estructura y cual sera el conjunto de caracteres que se acepptaran como parte de el.

Una posible definición para el TDA de un sting seria la siguiente:

• ESTRUCTURA;   dado como un string se considera una cadena se puede pensar que se  establece una ralacion lineal entre elementos, suponiendo que los string pueden almacenar entre 0 y 80 elementos, entonces su dominio sera el conjunto de todas las cadenas que se puede forma con combinaciones de los elementos y que cumplen con la regla de longitud.

¿Como se puede representar el TDA del String?

Hay diversas posibilidades para representar una cadena de caracteres. se puede almacenar en la memoria  contigua, como seria el caso de un arreglo; también podria utilizarse almacenamiento no contiguo, como kas listas encadenadas.

¿Cuales son las formas mas comunes de representación con almacenamiento contiguo?

Forma 1: uso de un carácter centinela

Los caracteres con forman el string se almacena en arreglos de carácter especial(que forman parte del conjunto de elementos del string) colocado al final de los caracteres que estas almacenados en el. En este tipo de representación se debe considerar que el centinela es un carácter que ocupara  un espacio; por lo tanto, debe tomar en cuenta al calcular la longitud que tendrá el string.

Forma 2: almacenamiento de la longitud actual de un string

En este tipo de representación, también los caracteres se almacenan en un arreglo de extensión predefinida. En este modelo la longitud actual del string se almacena en la primera posición del arreglo(generalmente la posición 0), que nos forman parte del string, aunque comparte la misma definición de datos.

¿Cuales son las formas mas comunes de representación con almacenamiento no contiguo?

Forma 1; lista encadenada de nodos con un carácter por nodo

En este modelo se genera una lista encadenada donde cada uno de los nodos almacena únicamente a uno de los caracteres del string y la dirección donde se encuentra el siguiente nodo de la lista.

Forma 2: lista encadenada de nodos con N caracteres por nodo

en este tipo de representación se genera una lista  encadenada donde cada uno de los nodos almacenan  N caracteres del string (N>1) y la dirección donde se encuentra el siguiente nodo de la lista.

¿Como viajan los datos por el Bus?

El Bus es el conjunto de líneas (cables) de hardware utilizados para la transmisión de datos entre los componentes de un sistema informático. Un bus es en esencia una ruta compartida que conecta diferentes partes del sistema como el procesador, la controladora de unidad de disco, la memoria y los puertos de entrada, salida, permitiéndoles transmitir información.

El bus, por lo general supervisado por el microprocesador, se especializa en el transporte de diferentes tipos de información.

En el bus se encuentran dos pistas separadas, el bus de datos y el bus de direcciones. La CPU escribe la dirección de la posición deseada de la memoria en el bus de direcciones accediendo a la memoria, teniendo cada una de las líneas carácter binario.

Es decir solo pueden representar 0 o 1 y de esta manera forman conjuntamente el número de la posición dentro de la memoria (es decir: la dirección).

Cuanto más líneas haya disponibles, mayor es la dirección máxima y mayor es la memoria a la cual puede dirigirse de esta forma. En el bus de direcciones original habían ya 20 direcciones, ya que con 20 bits se puede dirigir a una memoria de 1 MB y esto era exactamente lo que correspondía a la CPU.

Esto que en le teoría parece tan fácil es bastante mas complicado en la práctica, ya que aparte de los bus de datos y de direcciones existen también casi dos docenas más de líneas de señal en la comunicación entre la CPU y la memoria, a las cuales también se acude.

Todas las tarjetas del bus escuchan, y se tendrá que encontrar en primer lugar una tarjeta que mediante el envío de una señal adecuada indique a la CPU que es responsable de la dirección que se ha introducido. Las demás tarjetas se despreocupan del resto de la comunicación y quedan a la espera del próximo ciclo de transporte de datos que quizás les incumba a ellas.

PROCESADOR	Bus de direcciones	Bus de datos
8086	20	16
8088	20	8
80186	20	16
80188	20	8
80286	24	16
80386 SX	32	16
80386 DX	32	32
80486 DX	32	32
80486 SX	32	32
PENTIUM	32	64
PENTIUM PRO	32	64

Este mismo concepto es también la razón por la cual al utilizar tarjetas de ampliación en un PC surgen problemas una y otra vez, si hay dos tarjetas que reclaman para ellas el mismo campo de dirección o campos de dirección que se solapan entre ellos.

Los datos en si no se mandan al bus de direcciones sino al bus de datos. El bus XT tenía solo 8 bits con lo cual sólo podía transportar 1 byte a la vez. Si la CPU quería depositar el contenido de un registro de 16 bits o por valor de 16 bits, tenía que desdoblarlos en dos bytes y efectuar la transferencia de datos uno detrás de otro.

De todas maneras para los fabricantes de tarjetas de ampliación, cuyos productos deben atenderse a este protocolo, es de una importancia básica la regulación del tiempo de las señales del bus, para poder trabajar de forma inmejorable con el PC.

Pero precisamente este protocolo no ha sido nunca publicado por lBM con lo que se obliga a los fabricantes a medir las señales con la ayuda de tarjetas ya existentes e imitarlas. Por lo tanto no es de extrañar que se pusieran en juego tolerancias que dejaron algunas tarjetas totalmente eliminada.