Trabajos

ACTIVIDAD VOLUNTARIA BÚSQUEDA EN AMPLITUD

Corrección

La solución que proponen nuestros compañeros Christian y Miguel Ángel, es correcta aunque como mejora explicativa se podría añadir el numero de iteracion y los nodos adyacentes de forma textual.

Trabajo

A continuación, indicamos el link con la solución de la actividad Enlace

ACTIVIDAD VOLUNTARIA DEL TEMA DE ÁRBOLES

BINARIOS ORDENADOS EQUILIBRADOS

Corrección ABOE

Como podemos ver en el siguiente link la actividad de borrado realizada por nuestros compañeros Rafael Jesús Leal Abad y Cristian López Fernández, es correcta y es un ejemplo típico de borrado en arboles binarios equilibrados, aunque se echa en falta detallar la altura y señalar los nodos a los cuales se les va ha realizar la rotación. Por lo demás, las operaciones de borrado y rotación son correctas.

Trabajo ABOE

1. Inserta, en el orden especificado, los siguientes enteros en un ABOE

aplicando las rotaciones pertinentes cuando corresponda: 11, 8, 18, 15, 13,

20, 7, 6, 10, 12 y 21.

Ficheros: Tipos de Organización

Organización apilada

Ventajas:

•      Su organización es muy simple y es fácil de implementar.
•      Corto tiempo de inserción de registros
•      Aprovecha muy bien el espacio (sobre todo con registros no estructurados).
•      Se utiliza en sistemas automáticos de adquisición de datos, donde lo importante es recoger los datos más que procesarlos en algún modo.
•      Es adecuada para lecturas no ordenadas.
•      La organización de apilo se utiliza cuando se desean almacenar datos sin tener en cuenta el orden.
•      Esta organización se utiliza para complementar la implementación de otras organizaciones de ficheros.

Inconvenientes:

•      Puede ocurrir redundancia de información, debido a que no se controla.
•      Dificultad a la hora de llevar a cabo las reorganizaciones, debido a sus altos costes de mantenimiento.
•      No implementa ninguna facilidad a la hora de acceder a los datos.

Organización secuencial

Ventajas:

•      Su organización es simple y es fácil de implementar.
•      Soluciona algunas deficiencias de la anterior implementación, como:

o   Acceso más fácil a los datos a través de la clave

o   Búsqueda de un registro

Inconvenientes:

•      No permite la ordenación o búsqueda por campos que no sean clave.
•      Dificultad a la hora de realizar la inserción.
•      La ordenación se pierde si se abusa mucho de la zona de derrama con lo que es obligatorio la realización de constantes reorganizaciones.

Organización encadenada

Ventajas:

•      Permite la ordenación de los registros por diversos campos.
•      Permite la representación de relaciones complejas

Inconvenientes:

•      Perdida de información si fallan los punteros
•      Los punteros físicos dependen del dispositivo.
•      Los punteros relativos dependen de la posición del registro dentro del fichero.
•      Difícil de implementar y ante cualquier cambio requiere de reorganizaciones con lo que provoca un elevadísimo coste en mantenimiento.

Organización secuencial indexada

Ventajas:

•       Permite un acceso directo y secuencial usando la clave más eficiente que en la organización secuencial por el uso del índice y por tener la zona de derrama ordenada mediante una cadena.
•       Permite un recorrido ordenado de los registros por medio de la clave más eficiente que en la secuencial, ya que la zona de derrama está ordenada mediante el uso de un fichero de apilo encadenado.

Inconvenientes:

•      Ocupa mucho más espacio por la utilización de los índices.
•      Requiere continuas y costosas reorganizaciones.
•      Existencia de la zona de derrama.
•      Imposibilidad de accesos rápidos por otros atributos que no sean la clave.
•      Poca eficiencia en el recorrido ordenado por otros atributos que no sean la clave.

Organización indexada

Ventajas:

•      Eficiencia en el acceso a la información en base a un predicado en el que puedan intervenir un    número no predefinido de atributos.
•      Rapidez en accesos exactos, genéricos u ordenados.
•      No requiriere reorganizaciones frecuentes.
•      Flexibilidad en la estructuras que simplifiquen los procesos de inserción, actualización, borrado, etc.
•      Eliminación de la zona de derrama

Inconvenientes:

•      Ocupa mucho más espacio por la utilización de los índices.         
•      Mantenimiento costoso

Organización hashing

Ventajas:

•       Se pueden usar los valores naturales de las claves, puesto que se traducen internamente a direcciones.
•       En este tipo de organizaciones cualquier operación es eficiente siempre que se realice basándose en el campo clave por el que se calcula la función hash. En caso contrario, la eficiencia es la misma que la de los archivos de apilo.
•       Se consigue la independencia lógica y física.

Inconvenientes:

• Mantenimiento costoso para llevar a cabo el tratamiento de los desbordes.
• Requiere un gran tiempo de procesamiento para la aplicación de la función hash.

Implementación Pila

A continuación, expongo el código para la Implementación de una pila usando celdas enlazadas, para mas facilidad pongo la descarga del código al final.

#ifndef _PILA_HPP_

#define _PILA_HPP_

// Facilita la entrada y salida 

#include <iostream>

using namespace std;

namespace ed {

template<class G>

struct Nodopila{

G inf; //!< Campo informativo de la pila

Nodopila *siguiente; //!< Puntero al siguiente nodo de la pila

};

//!  Definición de la clase Pila

template<class G>

class Pila

{

  

   //! \name Atributos privados de la clase pila

   private: 

      int       _n;       //!< Número de puntos de la pila 

Nodopila <G> *_cabeza; //!< Cabeza de la pila

Nodopila <G> *_cola;   //!< Cola de la pila 

Nodopila <G> *_cursor; //!< Puntero al elemento actual de la pila

   //! \name Funciones o métodos públicos de la clase Pila

   public:

//! \name Constructor de la clase Pila

/*! 

\brief Constructor que crea una Pila vacia

\pre Ninguna

\post La pila toma los siguientes valores por defecto

_n = 0;

_cabeza = NULL;

_cola   = NULL;

_cursor = NULL;

*/

inline Pila()

          {

   _n = 0;

   _cabeza = NULL;

   _cola   = NULL;

   _cursor = NULL;

 }

 

 

//! \name Constructor de copia de la clase Pila

/*! 

\brief Constructor que crea una Pila vacia

\pre Ninguna

*/

inline Pila( Pila const &p)

          {

   if (p.estaVacia() == true)

   {

_n = 0;

_cabeza = NULL;

_cola   = NULL;

_cursor = NULL;

   }

   else{

Nodopila <G> *auxiliar;

G x;

auxiliar = p._cabeza;

_cabeza = NULL; 

_cursor = NULL;

_n = 0;

do

{

     x = auxiliar->inf;

     _cursor = NULL; 

     

     Nodopila <G> *nodo = NULL;

     nodo = new Nodopila <G>;

     

     if (_cabeza == NULL)

     {

_cabeza=nodo;

_cabeza->inf=x;

_cursor=nodo;

_cola=nodo;

_n++;

     }

     else

     {

nodo->siguiente=_cola->siguiente;

_cola->siguiente=nodo;

nodo->inf=x;

   

_cursor=_cabeza;

_cola=nodo;

_n++;

     } 

     auxiliar = auxiliar->siguiente;

}while (auxiliar != NULL);

   }

 }

 

~Pila()

{

   if (not estaVacia())

   {

     while (_cabeza != NULL)

{

_cursor = _cabeza;

_cabeza = _cabeza->siguiente;

delete _cursor;

}

_n = 0;

_cola = _cursor = NULL;

   }

}

 

//! \name Funciones de acceso de la clase Pila

/*! 

\brief Devuelve la cantidad de elementos de la pila

\return Devuelve el atributo _n

\pre Ninguna

\post Ninguna

*/

int tamanyo ()

{

   return _n;

}

/*! 

\brief Comprueba si una pila está vacía 

\return void

*/

bool estaVacia () const

{

if (_n == 0)

return true;

else

return false;

}

/*! 

\brief Inserta al principio de la pila datos de tipo generico

\return void

*/

void apilar(G const&p)

{

 Nodopila <G> *nodo = new Nodopila <G>;

 Nodopila <G> *aux = new Nodopila <G>;

 aux=_cabeza;

   

   if (_cabeza==NULL)

   {

     _cabeza=nodo;

     _cabeza->inf=p;

     _cursor=nodo;

     _n++;

   }

   else

   {

   _cabeza=nodo;

   _cabeza->inf=p;

   _cabeza->siguiente=aux;

   

   

   _cursor=nodo;

   _n++;

   }  

}

/*! 

\brief Quita el elemento situado en la cima de la pila

\return void

*/

void desapilar()

{

   if (not estaVacia())

   {

 Nodopila <G> *nodo = new Nodopila <G>;

 Nodopila <G> *principio = new Nodopila <G>;

 int cont = 0;

 nodo = _cursor;

 principio = _cabeza;

 if(_cursor==_cabeza)

 {

   _cursor=_cursor->siguiente;

   _cabeza=_cursor;

   

   delete nodo;

   _n--;  

 }

 else

 {

   while (principio != NULL and cont==0)

   {

     if(principio->siguiente == _cursor)

{

 

  if(_cursor->siguiente != NULL)

 {

   _cursor=_cursor->siguiente;

   principio->siguiente = _cursor;

 }

 else{

   _cursor=_cabeza;

   principio->siguiente = NULL;

 }

 

 cont=1;

}

     

     principio = principio->siguiente;

   } 

 

   delete nodo;

   _n--;

  }

}

}

/*! 

\brief Devuelve el elemtento de la cima de la pila

\return G (tipo generico)

*/

G cima()

{

 return _cursor->inf;

}

Pila &operator=(const Pila &p) throw()

{

 

   if (not estaVacia())

   {

     while (_cabeza != NULL)

{

_cursor = _cabeza;

_cabeza = _cabeza->siguiente;

delete _cursor;

}

_n = 0;

_cola = _cursor = NULL;

   }

   

   if (p.estaVacia() == true)

{

   _n = 0;

   _cabeza = NULL;

   _cola   = NULL;

   _cursor = NULL;

}

else{

   

   Nodopila <G> *auxiliar;

   G x;

   

   auxiliar = p._cabeza;

   _cabeza = NULL; 

   _cursor = NULL;

   _n = 0;

   do

   {

 x = auxiliar->inf;

 _cursor = NULL; 

 

 Nodopila <G> *nodo = NULL;

 nodo = new Nodopila <G>;

 

 if (_cabeza == NULL)

 {

   _cabeza=nodo;

   _cabeza->inf=x;

   _cursor=nodo;

   _cola=nodo;

   _n++;

 }

 else

 {

   nodo->siguiente=_cola->siguiente;

   _cola->siguiente=nodo;

   

   nodo->inf=x;

   _cursor=_cabeza;

   _cola=nodo;

   _n++;

 } 

   

 auxiliar = auxiliar->siguiente;

   }while (auxiliar != NULL);

}

 return *this;

}

}; // Fin de la definición de la clase Pila

} // \brief Fin de namespace ed.

#endif 

Descarga del Código

Registro de los bloques libres

Un aspecto a tener en cuenta es como almacenar los bloques que quedan disponibles en el disco.

Se utilizan por lo general dos métodos:

• La lista de bloques libres como lista ligada.
• Un mapa de bits.

Lista ligada de bloques de disco:

• Cada bloque contiene tantos números de bloques libres como pueda.
• El ultimo valor de cada bloque indica la dirección del siguiente bloque de la lista
• Los bloques libres se utilizan para contener a la lista de bloques libres.

   Ø  Ventajas

·       Este sistema funciona muy bien si se mantiene en memoria el primer bloque de la lista.

·       No hay que buscar los bloques libres.

   Ø  Inconvenientes

·       Si el disco está muy lleno este sistema ocupa mucho espacio.

Mapa de bits:

• Un disco con “n” bloques necesita un mapa de bits con “n” bits.
• Los bloques libres se representa con “1” y los asignados con “0” (o viceversa).
• Generalmente este método es preferible cuando existe espacio suficiente en la memoria principal para contener completo el mapa de bits.

   Ø   Ventajas

·       Ocupa poco espacio.

·       En discos llenos puede ser mucho menos operativo que la lista de bloques

   Ø  Inconvenientes

·       Requiere buscar los bloques libres.

Los dos métodos aquí indicados tienen el problema de la seguridad. Si un bloque del mapa de bits, o de la lista ligada de bloques de disco, es borrado, supone la pérdida del registro del espacio libre. Esto se suele solucionar mediante diversas utilidades que a través de las cadenas de asignación de los ficheros logran recuperar el registro del espacio libre. Este proceso es lento, pero no presenta ningún problema adicional al sistema operativo.

Problema lectores-escritores con prioridad de escritores.

Programa la solución al problema de lectores / escritores con prioridad de escritores.
• NOTA: esta vez necesitamos contabilizar localmente tanto el número de lectores como el número de escritores en el sistema. Recuerda que aunque no tengan la prioridad, si un lector estaba ya en el sistema los escritores han de bloquearse.


Solución en Pseudocódigo:

#define TRUE 1

semáforo mutex_r; // Controla exclusión mutua para el nº de lectores                    

semáforo mutex_w; // Controla exclusión mutua para el nº de escritores                   

semáforo lectores; //Controla entrada de lectores

semáforo escritores; //Controla entrada de escritores

int nw = 0; //Contabiliza nº de escritores

int nr = 0; //Contabiliza nº de lectores

main(){

IniciarSemaforo (mutex_r, 1);

IniciarSemaforo (mutex_w, 1);

IniciarSemaforo (lectores, 1);

IniciarSemaforo (escritores, 1);

}

void Lector ()

{

extern SEMAFORO mutex_r, lectores, escritores;

extern int nr;

   while (TRUE)

   {

      wait(lectores);

        wait (mutex_r);

          nr++;

          if(nr == 1)

             wait(escritores);

         signal(mutex_r);

      signal(lectores);

      LeerDatos (); //Seccion Critica

      wait (mutex_r);

        nr--;

        if (nr == 0)

          signal (escritores);

      signal (mutex_r);

   }

}

void Escritor ()

{

extern SEMAFORO mutex_w, lectores, escritores;

extern int nw;

   while (TRUE)

   {

      wait (mutex_w);

        nw++;

        if(nw == 1)

          wait(lectores);

      signal(mutex_w);

      wait(escritores);

        EscribirDatos (); //Seccion Critica

      signal (escritores);

      wait(mutex_w);

        nw--;

        if(nw == 0)

          signal(lectores);

      signal(mutex_w)

   }

}

Historia de los ordenadores a partir de 1996


Los ordenadores a partir del año 1996 surgieron a raiz de la 4ª generacion de ordenadores, la cual merece la pena explicar:

• 4ª generacion(1971- actualidad)

La denominada Cuarta Generación es el producto de la microminiaturización de los circuitos electrónicos. El tamaño reducido del microprocesador de chips hizo posible la creación de las computadoras personales (PC). Hoy en día las tecnologías LSI (Integración a gran escala) y VLSI (integración a muy gran escala) permiten que cientos de miles de componentes electrónicos se almacenen en un chip. Usando VLSI, un fabricante puede hacer que una computadora pequeña rivalice con una computadora de la primera generación que ocupaba un cuarto completo. Hicieron su gran debut las microcomputadoras.

El en 1998 Intel da a conocer su microprocesador Pentium II. Las características principales de las computadoras personales son su diseño para uso individual y el uso de un microprocesador. Sin embargo, aunque en principio están pensadas para uso singular, es muy común la conexión entre ellos para formar una red de computadoras. En términos de potencia existe una gran variedad. Prácticamente ha desaparecido la distinción ente computadoras personales y estaciones de trabajo. Modelos de computadoras personales de alta calidad, tanto PCs como Macintosh, ofrecen la misma potencia calculadora y capacidad gráfica como las estaciones de trabajo de baja calidad, de SUN Microsystems, Hewlett-Packard y DEC.

   

En el ambito hardware,  los ordenadores se van haciendo más pequeños, rapidos, baratos y se vuelve algo al alcanze de casi todo el mundo. Respecto al software requieren hardware mas avanzado (RAM, Disco duro, Procesador, ect..), son mas faciles de utilizar, mejoran el diseño y son mas baratos.

Los componentes esenciales de una computadora hoy día 2006, son los mismos que se utilizaban hacen 25 años. Lo que ha cambiado es la escala de integración, la capacidad de los periféricos y el tamaño y capacidades del software. 

• Los ordenadores en la actualidad

Hay gran diversidad de ordenadores, no sólo de marcas diferentes sino de potencias y características, además de finalidades distintas. A continuación, citamos algunos de los dispositivos que han evolucionado a partir de los ordenadores:

Superordenadores: Pueden ser utilizados simultáneamente por muchos usuarios, en cálculos científicos o de simulación. Su coste es por lo general es de decenas de millones de euros y su velocidad es enorme.

Mainframes o grandes ordenadores: Son equipos dedicados a gestión, por lo que admiten gran cantidad de trabajos simultáneos, como por ejemplo controlar una red de terminales en las sucursales de una empresa, o una red de cajeros automáticos de un banco.

Superminiordenadores: Son equipos en principio dedicados a tareas departamentales dentro de una empresa. Su capacidad principal es la de soportar gran cantidad de terminales, pues están orientados a la gestión. Dado su bajo precio en comparación con los grandes ordenadores, están cogiendo cuota de mercado frente a ellos.

Miniordenadores: Son equipos que admiten unas cuantas terminales. Están orientados a la gestión. Actualmente son poco competitivos frente a los microordenadores de gama alta.

Estaciones de trabajo ("Workstations"): Son equipos monousuario, dotados de gran capacidad de cálculo y con enormes prestaciones gráficas. Se utilizan principalmente en la investigación científica y en aplicaciones técnicas, como por ejemplo la simulación. Su precio está bajando y actualmente son competitivas con los microordenadores de gama alta. Estos equipos no sirven para aplicaciones de gestión.

Ordenadores personales o microordenadores: Son equipos ampliamente difundidos, de precio reducido y de prestaciones suficientes no sólo para el nivel personal, sino para pequeñas empresas. Actualmente se están conectando entre sí, formando grandes redes lo cual los hace adecuados para entornos más exigentes, sustituyendo en muchos casos a los miniordenadores. Actualmente están alcanzando gran difusión los portátiles ("notebooks") por su trasportabilidad. El tipo más reciente son los conocidos como Netbooks, de reducidas dimensiones y funcionalidades limitadas, están diseñadas para uso como terminales de internet.

Tablet PC

El tablet PC está integrado también en el mercado de los ordenadores portátiles, desde comienzos de 2002 convive con nosotros ese nuevo concepto de versatilidad móvil, es un ordenador pizarra, a medio camino entre un ordenador portátil y un PDA, en el que se puede escribir a través de una pantalla táctil. Un usuario puede utilizar un "lápiz" para trabajar con el ordenador sin necesidad de teclado o ratón.

Consolas de juego: A esta categoría pertenecen equipos, ampliamente difundidos en la actualidad, con prestaciones orientadas principalmente al entretenimiento doméstico. La más conocidas son: la PlayStation 3 de Sony, que tiene el procesador de gráficos más potente del mercado y conectividad Wifi, también sirve para reproducir películas en alta definición de discos Blu-ray; la Wii de Nintendo presenta como novedad un mando revolucionario (interpreta la intensidad que se da al movimiento y detecta las rotaciones en el espacio tridimensional) y la XBox de Microsoft.

Sistemas empotrados: son los sistemas informáticos más habituales, del orden del 90% de la producción de microprocesadores va dirigida a sistemas empotrados (a veces denominados incrustados). Aunque no los vemos, están en dispositivos de la vida cotidiana, como teléfonos móviles celulares, electrodomésticos, coches, sistemas de control, equipos de música, y muchos más productos. Estos sistemas suelen llevar el "software" en circuitos electrónicos denominados "firmware".

PDA: "Personal Digital Assistant" o Ayudante personal digital es un dispositivo de pequeño tamaño que combina un ordenador, teléfono/fax, Internet y conexiones de red, y los más modernos incorporan sistema de posicionamiento global (GPS). La mayoría de PDAs empezaron a usarse con una especie de bolígrafo en lugar de teclado, por lo que incorporaban reconocimiento de escritura a mano. Hoy en día los PDA pueden tener teclado y/o reconocimiento de escritura.

Smartphone: Smartphone (teléfono inteligente) es la denominación de teléfonos móviles celulares con características similares a las de un ordenador personal. Casi todos los teléfonos inteligentes son móviles que soportan completamente un cliente de correo electrónico con la funcionalidad completa de un organizador personal. Una característica importante de casi todos los teléfonos inteligentes es que permiten la instalación de programas para incrementar el procesamiento de datos y la conectividad.