ESTRUCTURA DE DATOS
Árboles Splay
Son árboles Binarios de Búsqueda Equilibrados, que mantienen el balance sin
necesidad de añadir
propiedades (campos adicionales) a los nodos para verificar las condiciones de
equilibrio. Utilizan
'operaciones splay', que como se verá a continuación se
basan exclusivamente en rotaciones.
Operaciones Básicas: Splay
La idea del
esplayado (splay) de un nodo consiste en llevar el nodo a la raíz a través de
rotaciones.
Supongamos que deseamos hacer splay sobre un nodo X de un árbol; existen 3
casos posibles
Rotación Zig: El padre de X es la raíz, es el caso más sencillo, se realiza una
rotación simple a la izquierda
o derecha, según sea el caso:
rotacion zig
Rotación Zig-Zig: El padre de X no es la raíz y X y PADRE(X) son ambos hijos
izquierdos (o ambos hijos
derechos). Se realiza en dos pasos: primero se rota PADRE(X)
hasta llevarlo a la raíz, y luego se rota X.
rotacion zig-zig
200914939
UNIVERSIDAD DE SAN CARLOS DE GUATEMALA
DICIEMBRE 2013
ESTRUCTURA DE DATOS
Rotación Zig-Zag: El padre de X no es la raíz y X es hijo izquierdo (derecho) y
PADRE(X) es hijo derecho
(izquierdo). Se realiza en dos pasos: primero se rota X hasta llevarlo a la
posición de su padre, y luego
hasta llevarlo a la raíz.
rotacion zig-zag
Para completar el splay de un nodo X, se
realizan repetidamente los casos anteriores, hasta llevarlo a la
raíz.
OperacionesBásicas: Inserción
Se inserta como
en un ABB y luego se aplica splay al nodo insertado.
arbol insertar(tipoclave valor, arbol t)
Operaciones Básicas: Eliminación
Se busca el nodo a eliminar y se hace splay sobre el. Luego, estando en la
raíz, con hijos left y right, se
elimina de la siguiente manera: se busca el mayor nodo del subárbol izquierdo y
se hace splay sobre
este. como
hijo derecho de este se transforma el subárbol derecho (right).
arbol borrar(tipoclave valor, arbol t)
else t=p->left;
LiberaNodo(p);
return(t);
}
USOS
ï‚·
ï‚·
ï‚·
ï‚·
ï‚·
Simulaciones en 3D, principalmente juegos, dibujan de forma eficiente los
escenarios.
Tablas de enrutamiento que utilizan los
routers para calcular la ruta más corta al momento de
transmitir información de un punto a otro.
En aplicaciones de inteligencia artificial para la búsqueda
de caminos. Por ejemplo, programas
que contienen información sobre una ciudad y calculan cómo llegar de una
dirección a otra
usan algoritmos de búsqueda que pueden utilizar árboles binarios.
Los compiladores crean árboles de sintaxis, que pueden ser
árboles binarios.
En algoritmos de compresión, como el utilizado en el formato
jpeg.
SERVIDORES
En informática, un servidor es un tipo de software que
realiza ciertas tareas en nombre de los usuarios.
El término servidor ahora también se utiliza para referirse al ordenador físico
en el cual funciona ese
software, una máquina cuyo propósito es proveer datos de modo que otras
máquinas puedan utilizar
esos datos.
Los archivos para cada sitio de Internet se almacenan y se
ejecutan en el servidor. Hay muchos
servidores en Internet y muchos tipos de servidores, pero comparten la función
común de proporcionar
el acceso a los archivos y servicios.
Un servidor sirve información a los ordenadores que se
conecten a él. Cuandolos usuarios se conectan a
un servidor pueden acceder a programas, archivos y
otra información del
servidor.
En la web, un servidor web es un ordenador que usa el
protocolo http para enviar páginas web al
ordenador de un usuario cuando el usuario las solicita.
Los servidores web, servidores de correo y servidores de bases de datos son a
lo que tiene acceso la
mayoría de la gente al usar Internet.
200914939
UNIVERSIDAD DE SAN CARLOS DE GUATEMALA
DICIEMBRE 2013
ESTRUCTURA DE DATOS
APLICACIONES
El estándar J2EE permite el desarrollo de aplicaciones de empresa de una manera
sencilla y eficiente.
Una aplicación desarrollada con las tecnologías J2EE permite ser desplegada en
cualquier servidor de
aplicaciones o servidor web que cumpla con el estándar. Un
servidor de aplicaciones es una
implementación de la especificación J2EE. La arquitectura J2EE es la siguiente
Figura 1. Arquitectura J2EE.
Definimos a continuación algunos de los conceptos que aparecen en la figura 1
Cliente web (contenedor de applets): Es usualmente un navegador e interactúa
con el contenedor web
haciendo uso de HTTP. Recibe páginas HTML o XML y puede
ejecutar applets y código JavaScript.
Aplicación cliente: Son clientes que no se ejecutan dentro de un navegador y pueden utilizar cualquier
tecnología para comunicarse con el contenedor web o directamente con la base de
datos.
Contenedor web: Es lo que comúnmente denominamos servidor web. Es la parte
visible del
servidor de
aplicaciones. Utiliza losprotocolos HTTP y SSL (seguro) para
comunicarse.
200914939
UNIVERSIDAD DE SAN CARLOS DE GUATEMALA
DICIEMBRE 2013
ESTRUCTURA DE DATOS
Servidor de aplicaciones: Proporciona servicios que soportan la ejecución y
disponibilidad de las
aplicaciones desplegadas. Es el corazón de un gran
sistema distribuido.
Frente a la tradicional estructura en dos capas de un
servidor web (ver Figura 2) un servidor de
aplicaciones proporciona una estructura en tres capas que permite estructurar
nuestro sistema de
forma más eficiente. Un concepto que debe quedar claro
desde el principio es que no todas las
aplicaciones de empresa necesitan un servidor de aplicaciones para funcionar.
Una pequeña aplicación
que acceda a una base de datos no muy compleja y que no sea distribuida
probablemente no necesitará
un servidor de aplicaciones, tan solo con un servidor
web (usando servlets y jsp) sea suficiente.
Como hemos
comentado, un servidor de aplicaciones es una
implementación de la especificación J2EE.
Existen diversas implementaciones, cada una con sus propias características que
la pueden hacer más
atractiva en el desarrollo de un determinado sistema.
Algunas de las implementaciones más utilizadas
son las siguientes:
BEA WebLogic
IBM WebSphere
Sun-Netscape IPlanet
Sun One
Oracle IAS
Borland AppServer
HP Bluestone
200914939
UNIVERSIDAD DE SAN CARLOS DE GUATEMALA
DICIEMBRE 2013
ESTRUCTURA DE DATOS
Los dos primeros son los más utilizados en el mercado. Nosotros
vamos autilizar el servidor BEA
WebLogic. La principal ventaja de WebLogic es que podemos crear un sistema con varias máquinas con
distintos sistemas operativos: Linux, Unix, Windows NT, etc. El
sistema funciona sin importarle en qué
máquina está corriendo el servidor.
Servidor proxy: Centraliza peticiones de los clientes y las reenvía hacia otras
máquinas. Puede servir
como
nivel de indirección y seguridad. También puede ser usado
para realizar balanceo de carga.
Cortafuegos (firewall): Proporciona servicios de filtrado, autorización y autentificación.
Puede actuar
como
proxy y ayuda a manejar los ataques de los hackers.
Máquina: Representa una unidad física donde reside un
servidor. Una máquina se define como tipo Unix
o no Unix (Windows NT, etc.).
Servidor: Un servidor es una instancia de la clase
weblogic.Server ejecutándose dentro de una máquina
virtual de Java. Un servidor está alojado en una
máquina, pero una máquina puede contener varios
servidores. Si un servidor no lo declaramos en ninguna
máquina WLS asume que está en una creada por
defecto.
Dominio: Un dominio es una unidad administrativa.
Sirve para declarar varios servidores, aplicaciones
etc. y que todos ellos estén asociados mediante el nombre del dominio.
Clustering (asociación): Los clusters permiten asociar maquinas y servidores
para que actúen de forma
conjunta como
una única instancia. La creación de un cluster va a
permitir el balanceo de carga y la
recuperación frente a fallos.
Balanceo de carga: Es una técnica utilizada para distribuir laspeticiones entre
varios servidores de tal
forma que todos los servidores respondan al mismo número de peticiones.
Recuperación ante fallos (failover): Permite evitar la caída de un sistema cuando una máquina deja de
funcionar o funciona incorrectamente.
Puerto de escucha: Un servidor tiene varios puertos
por los que puede 'escuchar' las peticiones. Existen
puertos ya asignados a aplicaciones concretas, como por ejemplo el
puerto de http que suele ser el 80.
Los puertos permiten que varias aplicaciones puedan atender
distintas peticiones en la misma máquina.
Un puerto en una dirección se especifica de la siguiente manera:
https://localhost:7001/direc . Con
:7001
indicamos el puerto que estamos atacando. Los puertos del 0 al 1023 son
reservados por el sistema.
Podemos disponer de los puertos del 1024 al 65536. Hay que tener
en cuenta que dos servicios no
pueden estar escuchando en el mismo puerto.
Modo producción y modo desarrollo. Hablaremos
muy a menudo de modo desarrollo y modo
producción. El modo desarrollo es cuando nos
encontramos desarrollando nuestra aplicación y no está
disponible exteriormente. El modo producción es cuando
está funcionando a pleno rendimiento y
tenemos clientes que se encuentran utilizándola. Por defecto, un dominio se arranca en modo
desarrollo.
200914939
UNIVERSIDAD DE SAN CARLOS DE GUATEMALA
DICIEMBRE 2013
ESTRUCTURA DE DATOS
SERVICIOS WEB
La W3C define 'Servicio web' como un sistema de software
diseñado para permitir interoperatibilidad
máquinaa máquina en una red. En general, los servicios web son sólo APIs Web
que pueden ser
accedidas en una red, como internet, y ejecutadas en un
sistema de hosting remoto.
En términos sencillos, un servicio web es cualquier
sistema de software diseñado para soportar
interacción máquina a máquina sobre una red.
Esta amplia definición abarca múltiples y diferentes
sistemas, pero en general 'servicio web' suele
referir a clientes y servidores que se comunican usando mensajes XML que siguen
el estándar SOAP.
En definitiva, permite comunicación entre diferentes máquinas, con diferentes
plataformas y entre
programas distintos. Esta comunicación se logra a través de
la adoptación de diversos estándares
abiertos.
El organismo WS-I se creó para mejorar la interoperatibilidad
entre las distintas implementaciones de
los servicios web.
Algunas especificaciones que define el servicio web
Las especificaciones que definen los servicios web son intencionalmente
modulares y esto resulta en
que no hay ni un sólo documento que las contenga a
todas ellas. Tampoco no hay ni un solo conjunto
estable de especificaciones.
SOAP, WSDL, UDDI, WS-Security, WS-ReliableMessaging,
WS-Reliability, WS-Addressing
Ventajas de los servicios web
ï‚·
ï‚·
ï‚·
ï‚·
Aumenta la interoperatibilidad entre programas independientemente de la
plataforma en
donde están instalados.
Aumenta la interoperatibilidad entre servicios y programas de
diferentes compañías y ubicados
en diferentes lugares geográficos.
Fomentan los estándares y protocolosbasados en texto,
haciendo más fácil acceder y entender
su contenido y funcionamiento (pero, en general, produciendo una baja en su
rendimiento).
Al emplear HTTP, pueden utilizar un sistema firewall
sin cambiar las reglas de filtrado.
Desventajas de los servicios web
ï‚·
ï‚·
No son tan desarrollados para realizar transacciones comparado a otros sistemas
como CORBA
(Common Object Request Broker Architecture).
Su rendimiento es bajo comparado con otros sistemas como CORBA, DCOM o RMI
especialmente por el uso de protocolos y estándares basados en texto.
200914939
UNIVERSIDAD DE SAN CARLOS DE GUATEMALA
DICIEMBRE 2013
ESTRUCTURA DE DATOS
SOLUCIONES WEB POR EMPRESA
The PHP Group: PHP
PHP es un lenguaje de programación de uso general de
código del lado del servidor originalmente
diseñado para el desarrollo web de contenido dinámico. Fue uno de los primeros
lenguajes de
programación del lado
del servidor
que se podían incorporar directamente en el documento HTML en
lugar de llamar a un archivo externo que procese los datos. El código es
interpretado por un servidor
web con un módulo de procesador de PHP que genera la página Web resultante. PHP ha evolucionado
por lo que ahora incluye también una interfaz de línea de comandos que puede
ser usada en
aplicaciones gráficas independientes. Puede ser usado en la mayoría de
los servidores web al igual que
en casi todos los sistemas operativos y plataformas sin ningún costo.
Fue creado originalmente por Rasmus Lerdorf en 1995.
Actualmente ellenguaje sigue siendo
desarrollado con nuevas funciones por el grupo PHP.2 Este lenguaje forma parte
del software libre
publicado bajo la licencia PHP, que es incompatible con la Licencia Pública
General de GNU debido a las
restricciones del uso del término PHP.3
Django Project -> Python -> Django
Django es un framework de desarrollo web de código abierto, escrito en Python,
que respeta el
paradigma conocido como Model Template View. Fue desarrollado en origen para gestionar varias
páginas orientadas a noticias de la World Company de Lawrence, Kansas, y fue liberada
al público bajo
una licencia BSD en julio de 2005; el framework fue nombrado en alusión al
guitarrista de jazz gitano
Django Reinhardt.
En junio del
2008 fue anunciado que la recién formada Django Software Foundation se haría
cargo de
Django en el futuro.
La meta fundamental de Django es facilitar la creación
de sitios web complejos. Django pone énfasis en
el re-uso, la conectividad y extensibilidad de componentes, el desarrollo
rápido y el principio No te
repitas (DRY, del
inglés Don't Repeat Yourself). Python es usado en todas las partes del framework
incluso en configuraciones, archivos, y en los modelos de datos.
Rails Core Team -> Ruby on Rails
Ruby on Rails, también conocido como RoR o Rails, es un framework de
aplicaciones web de código
abierto escrito en el lenguaje de programación Ruby, siguiendo el paradigma de
la arquitectura Modelo
Vista Controlador (MVC). Trata de combinar la simplicidad con la posibilidad de
desarrollaraplicaciones
del
mundo real escribiendo menos código que con otros frameworks y con un mínimo de
configuración.
El lenguaje de programación Ruby permite la metaprogramación, de la cual Rails
hace uso, lo que resulta
200914939
UNIVERSIDAD DE SAN CARLOS DE GUATEMALA
DICIEMBRE 2013
ESTRUCTURA DE DATOS
en una sintaxis que muchos de sus usuarios encuentran muy legible. Rails se distribuye a través de
RubyGems, que es el formato oficial de paquete y canal de distribución de
bibliotecas y aplicaciones
Ruby.
Los principios fundamentales de Ruby on Rails incluyen No te repitas (del inglés Don't repeat
yourself
DRY) y Convención sobre configuración.
No te repitas significa que las definiciones deberían
hacerse una sola vez. Dado que Ruby on Rails es un
framework de pila completa, los componentes están integrados de manera que no
hace falta establecer
puentes entre ellos. Por ejemplo, en ActiveRecord, las definiciones de las
clases no necesitan especificar
los nombres de las columnas; Ruby puede averiguarlos a partir de la propia base
de datos, de forma que
definirlos tanto en el código como en el programa sería
redundante.
Convención sobre configuración significa que el programador
sólo necesita definir aquella configuración
que no es convencional. Por ejemplo, si hay una clase Historia en el
modelo, la tabla correspondiente de
la base de datos es historias, pero si la tabla no sigue la convención (por
ejemplo blogposts) debe ser
especificada manualmente (set_table_name 'blogposts').Así, cuando se
diseña una aplicación
partiendo de cero sin una base de datos preexistente, el seguir las
convenciones de Rails significa usar
menos código (aunque el comportamiento puede ser configurado si el sistema debe
ser compatible con
un sistema heredado anterior)
ORACLE->JAVA->JSP
JavaServer Pages (JSP) es una tecnología que ayuda a los desarrolladores de
software a crear páginas
web dinámicas basadas en HTML, XML entre otros tipos de documentos. JSP es
similar a PHP pero usa el
lenguaje de programación Java.
Para desplegar y correr JavaServer Pages, es requerido un
servidor web compatible con contenedores
servlet como
Apache Tomcat o Jetty.
TagLibs -> JSP -> Servidor Aplicaciones (Servlets) -> Cliente
(Navegador
El rendimiento de una página JSP es el mismo que tendría el servlet
equivalente, ya que el código es
compilado como
cualquier otra clase Java. A su vez, la máquina virtual
compilará dinámicamente a
código de máquina las partes de la aplicación que lo requieran. Esto
hace que JSP tenga un buen
desempeño y sea más eficiente que otras tecnologías web que ejecutan el código
de una manera
puramente interpretada.
La principal ventaja de JSP frente a otros lenguajes es que el lenguaje Java es
un lenguaje de propósito
general que excede el mundo web y que es apto para crear clases que manejen
lógica de negocio y
acceso a datos de una manera prolija. Esto permite separar en niveles las
aplicaciones web, dejando la
parte encargada de generar el documento HTML en el archivo JSP.
DIEGO RAFAELROMERO
200914939
UNIVERSIDAD DE SAN CARLOS DE GUATEMALA
DICIEMBRE 2013
ESTRUCTURA DE DATOS
Otra ventaja es que JSP hereda la portabilidad de Java, y es posible ejecutar
las aplicaciones en múltiples
plataformas sin cambios. Es común incluso que los
desarrolladores trabajen en una plataforma y que la
aplicación termine siendo ejecutada en otra.
Los servlets y Java Server Pages (JSPs) son dos métodos de creación de páginas
web dinámicas en
servidor usando el lenguaje Java. En ese sentido son
similares a otros métodos o lenguajes tales como el
PHP, ASP o los CGIs, programas que generan páginas web en el servidor. Sin embargo, se diferencian de
ellos en otras cosas.
Para empezar, los JSPs y servlets se ejecutan
en una máquina virtual Java, lo cual permite que, en
principio, se puedan usar en cualquier tipo de
ordenador, siempre que exista una máquina virtual Java
para él. Cada servlet (o JSP, a partir de ahora lo usaremos de forma
indistinta) se ejecuta en su propio
hilo, es decir,
en su propio contexto; pero no se comienza a ejecutar cada vez que recibe una
petición
sino que persiste de una petición a la siguiente, de forma que no se pierde
tiempo en invocarlo (cargar
programa + intérprete). Su persistencia le permite también hacer una serie de
cosas de forma más
eficiente: conexión a bases de datos y manejo de sesiones, por ejemplo.
Las JSPs son en realidad una forma alternativa de crear servlets ya que el
código JSP se traduce a código
de servlet Java la primera vez que se le invoca y en adelantees el código del
nuevo servlet el que se
ejecuta produciendo como salida el código HTML que compone la página web de
respuesta.
Perl
Perl es un lenguaje de programación diseñado por Larry
Wall en 1987. Perl toma características del
lenguaje C, del
lenguaje interpretado bourne shell (sh), AWK, sed, Lisp y, en un grado
inferior, de
muchos otros lenguajes de programación.
Estructuralmente, Perl está basado en un estilo de
bloques como los del C o AWK, y fue ampliamente
adoptado por su destreza en el procesado de texto y no tener ninguna de las
limitaciones de los otros
lenguajes de script.
La estructura completa de Perl deriva ampliamente del lenguaje C. Perl es un
lenguaje imperativo, con
variables, expresiones, asignaciones, bloques de código delimitados por llaves,
estructuras de control y
subrutinas.
Perl también toma características de la programación shell.
Todas las variables son marcadas con un
Sigilo precedente (Sigil, en inglés). Los sigilos identifican inequívocamente
los nombres de las variables
permitiendo a Perl tener una rica sintaxis. Notablemente, los sigilos permiten
interpolar variables
directamente dentro de las cadenas de caracteres (strings). Como
en los shell, Perl tiene muchas
funciones integradas para tareas comunes y para acceder a los recursos del
sistema.
Perl toma las listas del Lisp, hash (memoria
asociativa) del AWK y expresiones regulares del
sed. Todo
esto simplifica y facilita todas las formas del análisis sintáctico, manejo de texto y
tareas de gestión de
datos.
