jueves, 14 de julio de 2011

Extra-Lenguaje ansi c Monticulos

Montículos
En ocasiones nos interesa tener algunos datos acomodados de modo que siempre sea fácil acceder al dato más grande (o alternativamente, al más pequeño). Esto se podría lograr si mantuvieramos a todos los datos completamente ordenados (como en una lista ordenada o en un árbol binario ordenado) pero en realidad esto no es necesario. A continuación mostraremos una estructura de datos (llamada montículo) basada en un árbol binario que cumple este propósito.
Definición de un montículo
Decimos que un árbol binario satisface la condición de montículo si cada padre es mayor que sus hijos. A diferencia de los árboles binarios ordenados, no hay ninguna condición que relacione a los hijos de un mismo padre (ni mucho menos a los de padres distintos). Finalmente, diremos que un árbol binario es un montículo si satisface la condición de montículo y, además, es un árbol binario completo, es decir, todos los niveles del árbol (excepto tal vez el último) están repletos, y en el último nivel todos los hijos están acumulados del mismo lado (digamos a la izquierda).

Así, de los siguientes árboles binarios, el primero no satisface la condición de montículo, el segundo no es completo y el tercero sí es un montículo.







Tres montículos

Representación de montículos
Como los montículos son árboles binarios completos, una forma conveniente de representar un montículo es mediante un arreglo.

Como los arreglos en C (y en C++, etc.) comienzan en la posición 0, podemos poner allí a la raíz del árbol, luego a sus hijos en las posiciones 1 y 2, a los hijos de 1 en las posiciones 3 y 4, a los hijos de 2 en las posiciones 5 y 6, etc. La regla es, por supuesto, poner a los hijos de K en las posiciones 2K+1 y 2K+2. Observe que esto nos simplifica la tarea de averiguar dónde están los hijos de un padre. Averiguar dónde está el padre de un hijo no es más dificil: el padre de K está en la posición (K-1)/2.

En Pascal a veces es conveniente declarar los arreglos como comenzando en la posición 1, y podemos poner allí a la raíz del árbol, luego a sus hijos en las posiciones 2 y 3, a los hijos de 2 en las posiciones 4 y 5, a los hijos de 3 en las posiciones 6 y 7, etc. La regla es, por supuesto, poner a los hijos de K en las posiciones 2K y 2K+1. Observe que esto nos simplifica la tarea de averiguar dónde están los hijos de un padre. Averiguar dónde está el padre de un hijo no es más dificil: el padre de K está en la posición K div 2.

De cualquiera de estas formas, el montículo de la figura estará representado por el arreglo P M O L I.
Operaciones sobre montículos
Las dos operaciones principales que nos interesan son las de crear un montículo a partir de un vector cualquiera y la de eliminar a la raíz de un montículo sin perder la estructura. A continuación mostramos como crear un montículo a partir del vector O L I M P:







Construcción de un montículo

A cada paso, insertamos un nuevo elemento al final del montículo (indicado con verde). En los primeros tres pasos (al insertar la O, la L y la I) no ocurre nada especial, pues cada hijo resulta menor que su padre. Al insertar la M en el cuarto paso, notamos que esto ya no es cierto, y tenemos que arreglar el montículo. Esto consiste en intercambiar el nuevo elemento con su padre mientras éste último sea mayor. En otras palabras, el nuevo elemento sube en el montículo (indicado con rojo) y sus padres bajan en el montículo (indicado con azul) mientras los padres sean menores. En nuestro caso, la M sólo subió una posición, pues es menor a la O. Finalmente, al insertar la P en el quinto paso, notamos que ésta debe subir dos niveles, en donde se convierte en la nueva raíz del montículo. En términos del vector que representa al montículo, después de cada uno de los pasos éste se ve así: (1) O L I M P, (2) O L I M P, (3) O L I M P, (4) O M I L P y (5) P O I L M.

¿Cuántas operaciones se harían en el peor de los casos para crear un montículo con N elementos? Observe que al insertar el K-ésimo elemento, éste puede subir un máximo de log2 K niveles. Así, el número máximo de veces que tendríamos que intercambiar dos elementos al construir un montículo es log2 1 + log2 2 + ... + log2 N que es menor a N log2 N.

Ahora destruyamos el montículo, eliminando a cada paso a la raíz del montículo:







Eliminando la raíz

A cada paso, eliminamos la raíz del montículo y, como esa posición no debe quedar vacía, la reemplazamos por el último elemento del montículo (indicado con verde). Normalmente, el árbol que queda no es un montículo y hay que arreglarlo nuevamente. En nuestro primer paso, al poner a M como raíz se viola la condición de montículo, pues M no es mayor que O. El arreglo consiste en intercambiar a M con uno de sus hijos. ¿Cuál de los dos? Si la intercambiaramos con I, entonces no habríamos arreglado nada, pues I no es mayor que O ni mayor que M. Luego, lo que tenemos que hacer es intercambiar a M con el mayor de sus hijos, en nuestro caso, con O. En otras palabras, a cada paso la nueva raíz va bajando (indicado con azul) y el mayor de sus hijos va subiendo (indicado con rojo) hasta que la nueva raíz no sea menor que ninguno de sus hijos. En el segundo paso eliminamos a la O, colocamos a L como nueva raíz y notamos que para arreglar el montículo debemos intercambiarla con la M. En el tercer paso eliminamos a la M, colocamos a la I como nueva raíz y notamos que hay que intercambiarla con la L. En el cuarto paso eliminamos a la L y colocamos a la I como nueva raíz.

Si en lugar de eliminar la raíz, simplemente la intercambiamos con el último elemento del montículo y luego la ignoramos, entonces, en términos del vector que representa al montículo, después de cada uno de los pasos éste se ve así: (1) O M I L P, (2) M L I O P, (3) L I M O P y (4) I L M O P. Observemos que el último vector está ordenado ascendentemente.

¿Cuántas operaciones se harían en el peor de los casos para destruir un montículo con N elementos? Observe que al eliminar la K-ésima raíz, la nueva raíz puede bajar un máximo de log2 (N-K-1) niveles. Así, el número máximo de veces que tendríamos que intercambiar dos elementos al destruir un montículo es log2 (N-1) + log2 (N-2) + ... + log2 2 que es menor a N log2 N.
Ordenamiento de montículo
Si comenzamos con un vector de tamaño N, luego creamos un montículo y luego lo destruimos, obtenemos un vector ordenado. A este algoritmo de ordenamiento se le conoce como ordenamiento de montículo. Del análisis expuesto arriba, se ve que el tiempo de ejecución de este algoritmo es de O(N log N) en el peor de los casos, es decir, tan rápido como se podría esperar de un algoritmo de ordenamiento basado en comparaciones.


http://ce.azc.uam.mx/profesores/franz/omi/monticulo.html

Arbol binario altura Extra-Lenguaje ansi c

Los árboles son importantes para conceptualizar algunos algoritmos. Esto se debe a que muchos problemas pueden ser resueltos imaginando como son las posibles respuestas.

Arboles y Arboles binarios son básicamente listas enlazadas a través de apuntadores. En el caso de árboles binarios, estos tienen en cada nodo, potencialmente dos hijos: un hijo izquierdo y un hijo derecho. El nodo hasta el tope del árbol es el nodo raiz.
Cuando un árbol tiene únicamente un nodo, su altura es de uno. Los que tienen un par de hijos tienen altura de dos y, así sucesivamente.
La altura o profundidad de un árbol indica tambien el número de niveles que tiene. Un árbol que tiene solo el nodo raiz, tiene un nivel, los que tienen un para de hijos tendrán dos niveles y, así sucesivamente.
En un árbol binario, el número de nodos en cada nivel, se incrementa con una potencia de dos:

Nivel nodos del nivel total nodos
1 1 1
2 2 3
3 4 8
..
k 2k-1 2k-1


El número máximo de nodos sobre el nivel k es 2exp(k-1). El número máximo de nodos en un árbol binario de profundidad k es 2k-1.
Un árbol binario de profundidad k que tiene exactamente 2k-1 nodos, se llama un árbol binario completo.

Una forma de representar un árbol binario es en forma secuencial, empezando con el nodo raiz y siguiendo de izaquierda a derecha en cada nivel. Un árbol binario con n nodos y de profundidad k es completo si sus nodos corresponden a los nodos que numeran a n en el árbol binario de profundidad k.Como consecuencia, en un árbol completo, pueden ser almacenados en forma compacta en un arreglo ARBOL unidimensional. Es entonces fácil de determinar la localización de cualquier nodo padre o hijo izquierdo o derecho.
Árboles binarios


Los árboles binarios son estructuras matemáticas que organizan un conjunto de elementos. Supondremos en este ejercicio que en un mismo árbol no puede haber elementos repetidos. Cada elemento se almacena en un nodo. Algunos de los nodos pueden estar relacionados, y son estas relaciones las que definen el árbol. Definimos un árbol binario





http://www.taringa.net/posts/apuntes-y-monografias/9249262/Arboles-Binarios.html

Extra Lenguaje ansi c

C es un lenguaje de programación de propósito general asociado, de modo universal, al sistema operativo UNIX. Sin embargo, la popularidad, eficacia y potencia de C se ha producido porque este lenguaje no está prácticamente asociado a ningún sistema operativo, ni a ninguna máquina en especial.
Esta es la razón fundamental por la que C es conocido como el lenguaje de programación de sistemas por excelencia.
Lenguaje de programación C

C es un lenguaje de alto nivel, que permite programar con instrucciones de lenguaje de propósito general.
También C se define como un lenguaje de programación estructurado de propósito general; aunque en su diseño también primó el hecho de fuera especificado como un lenguaje de programación de sistemas, lo que proporciona una enorme cantidad de potencia y flexibilidad.
El estándar ANSI C formaliza construcciones no propuestas en la primera versión del lenguaje C, en especial asignación de estructuras y enumeraciones. Entre otras aportaciones, se definió esencialmente la biblioteca estándar de funciones otra de las grandes aportaciones.
En la actualidad, el lenguaje C sigue siendo uno de los más utilizados en la industria del software, así como en institutos tecnológicos, escuelas de ingeniería y universidades.
Prácticamente todos los fabricantes de sistemas operativos (tomando en cuenta a: UNIX, Linux, MacOS, Solaris, Windows, entre otros.), soportan diferentes tipos de compiladores de lenguaje C.
Ventajas del lenguaje C
El lenguaje C tiene una gran cantidad de ventajas sobre otros lenguajes y constituyen precisamente la razón fundamental de que después de casi dos décadas de uso C siga siendo uno de los lenguajes más populares, utilizados en empresas, organizaciones y fábricas de software de todo el mundo.
C se caracteriza por su velocidad de ejecución. En los primeros días de la informática los problemas de tiempo de ejecución se resolvían escribiendo todo o parte de una aplicación en lenguaje ensamblador (muy al lenguaje de máquina).
Debido a que existen muchos programas escritos en el lenguaje C, se han creado numerosas bibliotecas C para programadores profesionales que soportan gran variedad de aplicaciones.
Características del lenguaje C
Hay numerosas características que diferencian al lenguaje C de otros, y lo hacen eficiente, potente, eficaz, rápido, indispensable para todos los programas. Algunas son:
    ? Una nueva sintaxis para declarar funciones. Una declaración de función puede añadir una descripción de los argumentos de la función. Esta información adicional sirve para que los compiladores detecten más fácilmnete lo errores causados por argumentos que no coinciden.
    ? Asignación de estructuras (registros) y enumeraciones.
    ? Preprocesador más sofisticado.
    ? Una nueva definición de la biblioteca que acompaña a C. Entre otras funciones se incluyen: acceso al sistema operativo (por ejemplo, lectura / escritura de archivos), entrada y salida con formato, asignación dinámica de memoria, manejo de cadenas de caracteres.
    ? Una colección de cabeceras estándar que proporciona acceso uniforme a las declaraciones de funciones y tipos de datos.
    http://www.bloginformatico.com/lenguaje-de-programacion-c.php

miércoles, 13 de julio de 2011

Extra Lenguaje ansi c

Instalando Chromium y Google Chrome en Ubuntu

Después de tanto tiempo sin actualizar hoy lo haré explicando de forma breve como instalar Chormium. Chromium es el proyecto de software libre detrás de Google Chrome.
Antes de todo decir que se puede instalar Google Chrome (la versión oficial) mediante Wine, ya que Google Chrome actualmente solo se encuentra disponible para Windows. Tanto en GNU/Linux como en Mac OS X sigue en desarrollo.

También avisar que Chromium (la versión en desarrollo disponible nativamente para GNU/Linux) es una versión pre-alpha, esto significa que está en una fase muy poco desarrollada, con muchos bugs y muchas funcionalidades sin activar.

En esencia, Chromium es el navegador base del que está construido Chrome y tiene sus mismas características de diseño, pero con un logotipo ligeramente diferente y sin el apoyo comercial y técnico de la compañía Google.

Para instalarlo nativamente en nuestro Ubuntu seguiríamos estos sencillos pasos.

Abriremos la consola (Aplicaciones/Accesorios/Terminal) y escribimos:

sudo gedit /etc/apt/sources.list

Al final del documento pegamos estas líneas

## Chromium (Google Chrome 4 Linux)
deb http://ppa.launchpad.net/chromium-daily/ppa/ubuntu intrepid main
deb-src http://ppa.launchpad.net/chromium-daily/ppa/ubuntu intrepid main
sudo apt-get update (con esto actualizamos los repositorios)
sudo apt-get install chromium-browser (instalaremos Chromium y ya lo tendremos en Aplicaciones/Internet/Chromium Web Browser).
Como he dicho la versión está en desarrollo y solo la recomiendo para echarle un vistazo. Mejor esperar a la versión final para testearlo profundamente.

ACTUALIZACIÓN 29/05/09: Ya ha salido la versión alpha de Chromium, numerosos bugs arreglados, mayor estabilidad aunque sigue con plugins como Flash desactivado. Ésta versión de Chromium ya es mas utilizable que la pre-alpha.

ACTUALIZACIÓN 15/06/09: Está disponible la versión oficial de Google Chrome (alpha, solo para desarrolladores) para descargar, enlaces a continuación:

Dev channel (for 32 bit systems): google-chrome-unstable_current_i386.deb
Dev channel (for 64 bit systems): google-chrome-unstable_current_amd64.deb