Puntos Extra- Algoritmos de ordenamiento

Aqui les dejo algunos tipos de metodos de ordenamiento:
METODO DE ORDENAMIENTO BURBUJA:
La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

Metodo de ordenamiento SHELL:
El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald shell. Su implementación original, requiere O(n²) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(n log² n) en el peor caso. Esto es mejor que las O(n²) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.
El Shell sort es una generalización del ordenamiento por insercion, teniendo en cuenta dos observaciones:

1. El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
2. El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.

El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

INSERCION:
El ordenamiento por inserción es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.
Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

QUICKSORT:
El ordenamiento rápido es un algoritmo creado por el matemático JOHN VOB NEUMAN basado en la técnica de divide y venceras, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
 SELECCION:
El ordenamiento por selección es un algoritmo de ordenamiento que requiere O(n²) operaciones para ordenar una lista de n elementos.
Su funcionamiento es el siguiente:

• Buscar el mínimo elemento de la lista
• Intercambiarlo con el primero
• Buscar el mínimo en el resto de la lista
• Intercambiarlo con el segundo

Y en general:

• Buscar el mínimo elemento entre una posición i y el final de la lista
• Intercambiar el mínimo con el elemento de la posición i

MEZCLA:
Fue desarrollado en 1945 por John Von Neumann.
Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:

1. Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:
2. Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.
3. Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
4. Mezclar  las dos sublistas en una sola lista ordenada.

El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de ejecución:

1. Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.
2. Se necesitan menos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que a partir de dos listas desordenadas. Por ejemplo, sólo será necesario entrelazar cada lista una vez que están ordenadas.

Puntos Extra- Control de versiones de software

En la clase de Lenguaje Ansi C se menciono que en ocasiones llegas a regarla al borrar por accidente tu codigo esto se puede prevenir con el control de versiones, Aqui esta esta ardua investigacion de control de versiones de software:
Una versión, revisión o edición de un producto, es el estado en el que se encuentra dicho producto en un momento dado de su desarrollo o modificación. Se llama control de versiones a la gestión de los diversos cambios que se realizan sobre los elementos de algún producto o una configuración del mismo. Los sistemas de control de versiones facilitan la administración de las distintas versiones de cada producto desarrollado, así como las posibles especializaciones realizadas (por ejemplo, para algún cliente específico).
El control de versiones se realiza principalmente en la industria informática para controlar las distintas versiones del codigo fuente. Sin embargo, los mismos conceptos son aplicables a otros ámbitos como documentos, imágenes, sitios web, etcétera.
Aunque un sistema de control de versiones puede realizarse de forma manual, es muy aconsejable disponer de herramientas que faciliten esta gestión (CVS, Subversion, Sourcesafe, Clearcase, Darcs, Bazaar, plasti, SCM, GIT, MERCURIAL, etc.).

Características
Un sistema de control de versiones debe proporcionar:

• Mecanismo de almacenamiento de los elementos que deba gestionar (ej. archivos de texto, imágenes, documentación...)
• Posibilidad de realizar cambios sobre los elementos almacenados (ej. modificaciones parciales, añadir, borrar, renombrar o mover elementos)
• Registro histórico de las acciones realizadas con cada elemento o conjunto de elementos (normalmente pudiendo volver o extraer un estado anterior del producto)

Aunque no es estrictamente necesario, suele ser muy útil la generación de informes con los cambios introducidos entre dos versiones, informes de estado, marcado con nombre identificativo de la versión de un conjunto de ficheros, etcétera.

Puntos Extra- Cola Circular

En medio de la clase de Lenguaje Ansi-C  se menciono una pila circular, por lo cual investige y descubri 3 tipos de pilas:
PILA SIMPLE
PILA CIRCULAR
PILA DOBLE

En cualquiera de estos tres tipos de pilas se llevan a cabo las acciones PUSH y POP
PUSH-Sirve para  para ingresar valores y agregarlos a la estructura pila dejando el ultimo valor que ingreso arriba con el apuntador externo "top".
POP-Este sirve para eliminar el ultimo valor ingresado a la pila.

Pero ahora si sin rodeos, ¿que es una cola circular?
Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden cosultarse, añadirse y eliminarse unicamente desde la cabeza del anillo que es una posición distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

Puntos Extra- Hashing Tables

Las tablas de dispersión o hashing tables (en inglés) es una técnica que se utiliza para implementar inserciones, eliminaciones y búsquedas en un tiempo medio constante.

La estructura de datos central de esta técnica es la tabla de hashing (

Planteamiento inicial

La estructura de datos ideal para la tabla de dispersión es un arreglo de tamaño fijo que contiene las claves (elementos de la tabla). Una clave suele ser una cadena de caracteres (o de números) con un valor asociado Si el tamaño de la tabla es MAX_T, la tabla se declara entre 0 y MAX_T-1. A cada clave se le hará corresponder un número entre 0 y MAX_T-1 y se colocará en la celda correspondiente.

La relación entre la llave y la posición en la tabla es lo que se llama función de dispersión.

Función Hash (o de Dispersión)

Es la correspondencia entre la clave y un índice del arreglo. Por lo general, cuando las claves son números enteros la función de dispersión toma la forma:

h(x) = clave MOD MAX_T

El tamaño de la tabla debe ser primo. De esta forma, y si las claves son números aleatorios, esta función suele distribuir las claves uniformemente. Si tuviéramos la tabla de la figura anterior (MAX_T =10), y todas las claves terminaran en cero, la dispersión con esta función no nos valdría.

Cuando las claves son cadenas de caracteres lo usual es sumar los valores ASCII de los caracteres de la cadena.

A continuación se declaran los tipos apropiados para la tabla de dispersión y el índice, que es el que devuelve la función de dispersión.

TYPE

INDICE = 0 .. MAX_T - 1;

TablaDisp= ARRAY INDICE OF ...

Una implementación sencilla de la función de dispersión sería la siguiente:

FUNCTION hashing (llave: TipoCadena): INDICE;

VAR

aux, j: integer;

BEGIN

aux := ord (llave[1]);

FOR j:=2 TO Length (llave) DO

aux := aux + ord (llave[j]);

hashing := aux MOD MAX_T;

END;

El problema de esta función es que, si la tabla es grande, no hace una distribución uniforme de las claves. Pongamos un ejemplo: tenemos una tabla con un tamaño MAX_T= 10007 (primo) y las claves tienen una longitud máxima de ocho caracteres; como ord devuelve un número entero de valor máximo 127, la función de dispersión sólo tendrá valores entre 0 y 1016 (127*8). Luego la distribución no es equitativa

A continuaciòn vamos a tratar el tema de las colisiones. Esto ocurre cuando dos elementos distintos toman el mismo valor. Para solucionar las colisiones veremos dos métodos: la dispersión abierta y la dispersión cerrada.

 tabla de dispersión.)

Tablas de Dispersión

(Hashing Tables)

Puntos Extra- ARBOLES Y GRAFOS

Los árboles y los grafos se refiere a estructuras de datos que permiten organizar y mantener información en un computador. Esta forma se inspira una forma de organizar información con lápiz y papel usando nodos y flechas entre los nodos (a esas flechas también se les llama arcos, a los nodos también se les llama vértices). Los grafos y árboles en papel son apropiados por ejemplo para capturar sólo una parte de la información de objetos, situaciones y otros tipos de información.

En un computador además de permitir organizar información, resultan estructuras útiles para resolver ciertos tipos de problema por ejemplo se pueden utilizar se pueden utilizar arboles AVL para mantener ordenada informacion de forma eficaz.

Para jugar, entender y emplear mejor grafos y árboles e.g Euler ha propuesto definiciones; a partir de estas definiciones y con ayuda de razonamientos lógicos ha demostrado propiedades.

Un ejemplo de arbol es el arbol binario el cual es una estructura de datos donde cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los arboles bianrios de busqueda, los monticulos binarios y codificacion de huffman.
Métodos para almacenar árboles binarios
Los árboles binarios pueden ser construidos a partir de lenguajes de programacion de varias formas. En un lenguaje con registros y referencias , los árboles binarios son construidos típicamente con una estructura de nodos y punteros en la cual se almacenan datos, cada uno de estos nodos tiene una referencia o puntero a un nodo izquierdo y a un nodo derecho denominados hijos. En ocasiones, también contiene un puntero a un único nodo. Si un nodo tiene menos de dos hijos, algunos de los punteros de los hijos pueden ser definidos como nulos para indicar que no dispone de dicho nodo. En la figura adjunta se puede observar la estructura de dicha implementación.

Los árboles binarios también pueden ser almacenados como una estructura de datos implicita en vectores, y si el árbol es un árbol binario completo, este método no desaprovecha el espacio en memoria. Tomaremos como notación la siguiente: si un nodo tiene un índice i, sus hijos se encuentran en índices 2i + 1 y 2i + 2, mientras que sus padres (si los tiene) se encuentra en el índice (partiendo de que la raíz tenga índice cero). Este método tiene como ventajas el tener almacenados los datos de forma más compacta y por tener una forma más rápida y eficiente de localizar los datos en particular durante un preoden transversal. Sin embargo, desperdicia mucho espacio en memoria.

 

Cabe mencionar los tipos de arboles binarios:

Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.

Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.

Un árbol binario perfecto o completo es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).

  

Puntos Extra

ENSAYO SOBRE LA APLICABILIDAD DE ANSI-C

Bueno, ya que en la primera tarea me fue mal,tratare de ganarme algunos puntos extra con esta investigacion.

Lenguaje Ansi-c es el lenguaje de programacion mas usado en el mundo, fue diseñado con el sistema operativo UNIX.

Lenguaje Ansi-C, se utiliza mucho en el campo industrial, asi como en la robotica, cibernetica, sistemas de informacion, en los campos cientificos de la informatica, fisica, quimica, matematicas, tambien en aplicaciones multimedia como escenas 3D en desarollos de animaciones, y la verdad sin exagerar es que muchas vidas dependen de la prgramacion asi como las simulaciones de vuelo (la cual es la mas delicada ya que se usan demasiados recursos de software y hardware para hacer una simulacion real de una aeronave.

C es el lenguaje comun para programar sistemas embebidos. Una caracteristica donde C demuestra comodidad de uso particularmente valiosa en sistemas embebidos es la manipulacion de bits

Tarea 5 Lenguaje Ansi-C

Aqui les dejo este programa en el cual tiene doble uso ya que se pueden utilizar pilas o colas
cualquier duda pregunten, (si preguntan salimos ganando todos , me dan puntos a mi y resuelven su duda :D)

include <stdio.h>
int main () {
int a[4];
int b;
int s;

printf ("dame los valores del arreglo");
for (i=0; i<=4; i++)
scanf ("%d", a[i])
do {
    printf ("como quieres los datos como pilas o como colas")
    scanf ("%d", s)
    if (s==1)
    for(i=4; i>=0; i--)
    printf ("a[i]");
   
    if (s==2)
    for(i=0; i<=4; i++)
     printf ("a[i]");
     else
     s=0
     } while (s!=0);
    
     printf("que numero deseas borrar")
     scanf("%d", b)
     for(i=0; i<=4; i++)
     if (b== a[i])
     a[i]= Null
     if (s==1)
    for(i=4; i>=0; i--)
    printf ("a[i]");
   
    if (s==2)
    for(i=0; i<=4; i++)
     printf ("a[i]");
     getche ();
     return 0;
     }