Este blog tiene como objeto la interacción cognoscitiva de los estudiantes de la asignatura Desarrollo de Software, trayecto II-2 nocturno y sabatino, de la misión Sucre núcleo Charavare.
martes, 27 de octubre de 2009
Plan de Evaluación Nocturno
Señores en este enlace se encuentra colgado el plan de evaluación, procedan a descargarlo. Saludos http://rapidshare.com/files/298756339/Desarrollo_de_Software_Nocturno.xls.html
Análisis de exposición sobre POO. En dichas exposiciones se hablo sobre la historia de la Programación Orientada a Objetos, el concepto del mismo y sus principales características, además se dio una explicación sobre sus características y los programas que trabajan con dichos métodos. Entre las cosas que considero importante es la definición de que el POO no es un lenguaje de programación como tal, sino una serie de métodos que permite a los entorno de desarrollos que cuentan con dichas características ofrecerle al programador una interfaz grafica para la creación de software de aplicaciones y de otra índole. Entre las principales características que tiene el POO se encuentra: • La herencia • El encapsulamiento • El polimorfismo Dichas características le dan a los entornos de desarrollo el toque esencial que requieren para programar orientados a objetos. La taxonomía de los lenguajes orientados a objetos es una clasificación para los lenguajes de programación con respecto a la orientación a objetos, en esta se establece claramente que para que un lenguaje de programación sea considerado orientado a objetos éste debe soportar la creación de clases y la herencia. Además la POO cuenta con características adicionales que son: • Tipificación fuerte. • Manejo de excepciones. • Paso de mensajes. • Generalidad. • Multitarea. • Persistencia. Estas permiten desarrollar aplicaciones con diversas características que permitirán al usuario final tener una mejor interacción con los programas Entre las ventajas que tiene la POO tenemos: • Permite la Flexibilidad podemos pensar en estos módulos como bloques con los cuales podemos construir diferentes programas. • Por medio de la Reusabilidad podemos utilizar una clase definida previamente en las aplicaciones que nos sea conveniente. Es claro que la flexibilidad con la que se definió la clase va a ser fundamental para su reutilización. • La Mantenibilidad. Las clases que conforman una aplicación, vistas como módulos independientes entre sí, son fáciles de mantener sin afectar a los demás componentes de la aplicación. • La Extensibilidad. Gracias a la modularidad y a la herencia una aplicación diseñada bajo el paradigma de la orientación a objetos puede ser fácilmente extensible para cubrir necesidades de crecimiento de la aplicación. Como resumen diré que la tecnología orientada a objetos nos permite diseñar e implementar sistemas bajo un paradigma de programación en el cual, por medio de la abstracción definimos a las clases o entidades de software a partir de entidades del mundo real. De dichas entidades instanciaremos objetos de software que se corresponderán con los objetos reales que representan. Esto nos permite enfocarnos más en la solución del problema que en la implantación de dicha solución.
Objetos en POO Los objetos son ejemplares de una clase cualquiera. Cuando creamos un ejemplar tenemos que especificar la clase a partir de la cual se creará. Esta acción de crear un objeto a partir de una clase se llama instanciar (que viene de una mala traducción de la palabra instace que en inglés significa ejemplar). Por ejemplo, un objeto de la clase fracción es por ejemplo 3/5. El concepto o definición de fracción sería la clase, pero cuando ya estamos hablando de una fracción en concreto 4/7, 8/1000 o cualquier otra, la llamamos objeto. Para crear un objeto se tiene que escribir una instrucción especial que puede ser distinta dependiendo el lenguaje de programación que se emplee, pero será algo parecido a esto. miCoche = new Coche() Con la palabra new especificamos que se tiene que crear una instancia de la clase que sigue a continuación. Dentro de los paréntesis podríamos colocar parámetros con los que inicializar el objeto de la clase coche. Estados en objetos Cuando tenemos un objeto sus propiedades toman valores. Por ejemplo, cuando tenemos un coche la propiedad color tomará un valor en concreto, como por ejemplo rojo o gris metalizado. El valor concreto de una propiedad de un objeto se llama estado. Para acceder a un estado de un objeto para ver su valor o cambiarlo se utiliza el operador punto. miCoche.color = rojo El objeto es miCoche, luego colocamos el operador punto y por último el nombre e la propiedad a la que deseamos acceder. En este ejemplo estamos cambiando el valor del estado de la propiedad del objeto a rojo con una simple asignación. Mensajes en objetos Un mensaje en un objeto es la acción de efectuar una llamada a un método. Por ejemplo, cuando le decimos a un objeto coche que se ponga en marcha estamos pasándole el mensaje “ponte en marcha”. Para mandar mensajes a los objetos utilizamos el operador punto, seguido del método que deseamos invocar. Objetos Entender que es un objeto es la clave para entender cualquier lenguaje orientado a objetos. Existen muchas definiciones que se le ha dado al Objeto. Primero empecemos entendiendo que es un objeto del mundo real. Un objeto del mundo real es cualquier cosa que vemos a nuestro alrededor. Digamos que para leer este artículo lo hacemos a través del monitor y una computadora, ambos son objetos, al igual que nuestro teléfono celular, un árbol o un automóvil. Analicemos un poco más a un objeto del mundo real, como la computadora. No necesitamos ser expertos en hardware para saber que una computadora está compuesta internamente por varios componentes: la tarjeta madre, el chip del procesador, un disco duro, una tarjeta de video, y otras partes más. El trabajo en conjunto de todos estos componentes hace operar a una computadora. Internamente, cada uno de estos componentes puede ser sumamente complicado y puede ser fabricado por diversas compañías con diversos métodos de diseño. Pero nosotros no necesitamos saber cómo trabajan cada uno de estos componentes, como saber que hace cada uno de los chips de la tarjeta madre, o cómo funciona internamente el procesador. Cada componente es una unidad autónoma, y todo lo que necesitamos saber de adentro es cómo interactúan entre sí los componentes, saber por ejemplo si el procesador y las memorias son compatibles con la tarjeta madre, o conocer donde se coloca la tarjeta de video. Cuando conocemos como interaccionan los componentes entre sí, podremos armar fácilmente una computadora.
Herencia La herencia es uno de los conceptos más cruciales en la POO. La herencia básicamente consiste en que una clase puede heredar sus variables y métodos a varias subclases (la clase que hereda es llamada superclase o clase padre). Esto significa que una subclase, aparte de los atributos y métodos propios, tiene incorporados los atributos y métodos heredados de la superclase. De esta manera se crea una jerarquía de herencia. Por ejemplo, imaginemos que estamos haciendo el análisis de un Sistema para una tienda que vende y repara equipos celulares.
Clases en POO Las clases son declaraciones de objetos, también se podrían definir como abstracciones de objetos. Esto quiere decir que la definición de un objeto es la clase. Cuando programamos un objeto y definimos sus características y funcionalidades en realidad lo que estamos haciendo es programar una clase. En los ejemplos anteriores en realidad hablábamos de las clases coche o fracción porque sólo estuvimos definiendo, aunque por encima, sus formas. Propiedades en clases Las propiedades o atributos son las características de los objetos. Cuando definimos una propiedad normalmente especificamos su nombre y su tipo. Nos podemos hacer a la idea de que las propiedades son algo así como variables donde almacenamos datos relacionados con los objetos. Métodos en las clases Son las funcionalidades asociadas a los objetos. Cuando estamos programando las clases las llamamos métodos. Los métodos son como funciones que están asociadas a un objeto. Objetos en POO Los objetos son ejemplares de una clase cualquiera. Cuando creamos un ejemplar tenemos que especificar la clase a partir de la cual se creará. Esta acción de crear un objeto a partir de una clase se llama instanciar (que viene de una mala traducción de la palabra instace que en inglés significa ejemplar). Por ejemplo, un objeto de la clase fracción es por ejemplo 3/5. El concepto o definición de fracción sería la clase, pero cuando ya estamos hablando de una fracción en concreto 4/7, 8/1000 o cualquier otra, la llamamos objeto. Para crear un objeto se tiene que escribir una instrucción especial que puede ser distinta dependiendo el lenguaje de programación que se emplee, pero será algo parecido a esto.
ANALISIS DEL ENTORNO AL POO El elemento fundamental de la OOP es el objeto. El objeto es un conjunto complejo de datos y programas que poseen estructura .El POO se basa en varias técnicas, incluyendo herencia, modularidad, polimorfismo y encapsulamiento. El POO expresa a un programa como un conjunto de estos objetos, que colaboran entre ellos para realizar tareas. Esto permite hacer los programas y módulos más fáciles de escribir, mantener, reutilizar y volver a utilizar. Un objeto es un ente que posee sus características propias (propiedades) y un conjunto de acciones que es capaz de realizar (métodos). El objeto contiene toda la información para permitirle definirlo e identificarlo frente a otros objetos que pertenecen a otras clases, incluso frente a objetos de una misma clase, tienen valores diferenciados en sus atributos. Los objetos tienen mecanismos de interacción llamados métodos para favorecer la comunicación entre ellos. Tienen características que llevan a tratarlos individualmente, no se separan ni deben separarse del estado y el comportamiento. Una clase es un ente abstracto que permite declarar las propiedades y los métodos de objetos similares. Un lenguaje de programación orientado a objetos debe permitir al programador realizar definiciones de clases, y construir objetos a partir de esas clases. El objeto no es un dato simple si no que tiene componentes estructurados, no es aislado, forma parte de una organización jerárquica o de otro tipo. Una de las ventajas más importantes, es permitir la realización de las clases que definen un programa de forma totalmente independiente al programa donde se utilizan. Gracias a la encapsulación y el polimorfismo. La herencia nos permite crear estructuras jerárquicas de clases donde es posible la creación de sub-clases que incluyan nuevas propiedades y atributos. Estas sub-clases admiten la definición de nuevos atributos, así como crear, modificar o inhabilitar propiedades. El POO no depende estrictamente del lenguaje: se puede hacer con lenguajes no clasificados como tales (por ejemplo C). Los lenguajes funcionales son de una clase un poco diferente -entre otras cosas, los lenguajes funcionales son un superconjunto de POO.
Ya que la OOP no es un lenguaje de programación, puede aplicarse a cualquier lenguaje, y de hecho hoy en día está disponible en mayor o menor medida en todos los lenguajes tradicionales (C se ha convertido en C++, Pascal en Delphi, VB incorpora parte de la OOP) y no aparece un lenguaje nuevo sin que incluya OOP (como es el caso de Java). Es por esto que intentaremos que todo lo que aquí se diga pueda ser aplicado a cualquier lenguaje OOP. En OOP, cada objeto es una entidad única, evitando que las ordenes contenidos en alguno de los objetos puedan mezclarse con rutinas de otros objetos. Una clase es un conjunto de reglas de creación y comportamiento de los objetos. Un objeto es un conjunto de datos que se comporta de acuerdo a las reglas de su clase. Encapsulamiento, es el vínculo que existe entre los datos de un objeto y los métodos que lo utilizan.
La herencia, es la cualidad que permite reutilizar un codigo previamente escrito modificando las diferencias que existan entre las clases y las subclases. Capacidad que tienen las clases derivadas o hijas para utilizar toda la información (datos y métodos) de todas las cla ses superiores. Polimorfismo, es la capacidad que tienen los objetos de clases diferentes para actuar frente al mismo mensaje de formas distintas. Sobrecarga, es la posibilidad de definir distintas funciones con el mismo nombre, pero con diferente conjunto de argumentos. Clase, es el conjunto de reglas de creación y comportamiento de los objetos. Superclase, es la clase de donde se derivan una o más clases. Subclase, es la clase que es derivada de otra u otras. Tambien se llama clase hija.
ANÁLISIS DE LA ESTRUCTURA DE OBJETOS El análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos. OBJETOS Y TIPOS DE OBJETOS En el análisis se trata de identificar los tipos de objeto más que los objetos individuales en un sistema. Los tipos de objetos se definen en base a la comprensión del analista de nuestro mundo. Un objeto puede categorizarse de variadas formas. ASOCIACIONES DE OBJETOS Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad). Representación para la Asociación entre dos Tipos de Objetos. ANÁLISIS DEL COMPORTAMIENTO DE OBJETOS En el análisis del comportamiento de objetos (ACO) realizamos esquemas de eventos que muestran eventos, la secuencia en que ocurren y cómo los eventos cambian el estado de los objetos. Estados de un Objeto. Un objeto puede existir en varios estados. Por ejemplo, un objeto reservación aérea puede ser una instancia de alguno de los siguientes tipos de objeto: Reservación solicitada, Reservación en lista de espera, Reservación confirmada, Reservación cancelada, Reservación satisfecha ,Reservación archivada. Tales tipos de objetos suelen percibirse como estados posibles del ciclo vital de un objeto. Sin embargo, un objeto puede tener una gran variedad de perspectivas de ciclos vitales. Por ejemplo, el mismo objeto reservación aérea también puede tener los siguientes estados relacionados con el pago: Reservación no liquidada, Reservación con un pago de depósito, Reservación totalmente pagada, Reservación reembolsada. Así, el estado de un objeto es la colección de asociaciones que tiene un objeto. Eventos. En el análisis orientado a objetos el mundo se describe en términos de los objetos y sus estados, así como los eventos que modifican esos estados. Un evento produce un cambio en el estado de un objeto. Los eventos sirven como indicadores de los instantes en que ocurren los cambios de estado. Para saber de los cambios y reaccionar adecuadamente ante ellos, debemos entender y modelar los eventos.
Sobrecarga se refiere a la posibilidad de tener dos o más funciones con el mismo nombre pero funcionalidad diferente. Es decir, dos o más funciones con el mismo nombre realizan acciones diferentes. El compilador usará una u otra dependiendo de los parámetros usados. A esto se llama también sobrecarga de funciones. La interfaz gráfica de usuario, conocida también como GUI es un tipo de interfaz de usuario que utiliza un conjunto de imágenes y objetos gráficos para representar la información y acciones disponibles en la interfaz. Habitualmente las acciones se realizan mediante manipulación directa para facilitar la interacción del usuario con la computadora. Surge como evolución de la línea de comandos de los primeros sistemas operativos y es pieza fundamental en un entorno gráfico. Como ejemplo de interfaz gráfica de usuario podemos citar el entorno de escritorio del sistema operativo Windows, el X-Window de Linux o el de Mac OS X, Aqua. En el contexto del proceso de interacción persona-ordenador, la interfaz gráfica de usuario es el artefacto tecnológico de un sistema interactivo que posibilita, a través del uso y la representación del lenguaje visual, una interacción amigable con un sistema informático Tipos de interfaces gráficas de usuario PUI's y Zooming user interface Los GUIs que no son PUIs son encontrados en juegos de computadora, y los GUIs avanzados basados en realidad virtual ahora son usados con más frecuencia en las investigaciones. Muchos grupos de investigación en Norteamérica y Europa están trabajando actualmente en el interfaz de enfoque del usuario o ZUI (Zooming User Interface), que es un adelanto lógico en los GUI, mezclando 3D con 2.o ó "2D y medio objetos vectoriales de una D". "Touchscreen user interface" Algunos GUIs son diseñados para cumplir con los rigurosos requisitos de los mercados verticales. Éstos se conocen como "GUIs de uso específico." Un ejemplo de un GUI de uso específico es el ahora familiar Touchscreen o Pantalla Táctil (pantalla que al ser tocada efectúa los comandos del mouse en el software. Es encontrado en muchos restaurantes alrededor del mundo y en tiendas de autoservicio. Primero iniciado por Gene Mosher en la computadora del ST de Atari en 1986, el uso que el específico GUI en el Touchscreen ha encabezado una revolución mundial en el uso de las computadoras a través de las industrias alimenticias y de bebidas, y en venta al por menor. Otros ejemplos de GUIs de uso específico, relacionados con el Touchscreen son los cajeros automáticos, los kioscos de información y las pantallas de monitoreo y control en los usos industriales, que emplean un sistema operativo de tiempo real (RTOS). Los teléfonos móviles y los sistemas o consolas de juego también emplean el Touchscreen. Además la domótica no es posible sin una buena interfaz de usuario, o GUI. ANÁLISIS DE LA ESTRUCTURA DE OBJETOS Si se construye software, los módulos de software OO se basan en los tipos de objetos. El software que implanta el objeto contiene estructuras de datos y operaciones que expresan dicho comportamiento. Las operaciones se codifican como métodos. La representación en software OO del objeto es entonces una colección de tipos de datos y objetos. Entonces, dentro del software orientado a objeto, un objeto es cualquier cosa, real o abstracta, acerca de la cual almacenamos datos y los métodos que controlan dichos datos. Un objeto puede estar compuesto por otros objetos.
ANÁLISIS DEL COMPORTAMIENTO DE OBJETOS En el análisis del comportamiento de objetos (ACO) realizamos esquemas de eventos que muestran eventos, la secuencia en que ocurren y cómo los eventos cambian el estado de los objetos. Estados de un Objeto. Un objeto puede existir en varios estados. Por ejemplo, un objeto reservación aérea puede ser una instancia de alguno de los siguientes tipos de objeto: Reservación solicitada, Reservación en lista de espera, Reservación confirmada, Reservación cancelada, Reservación satisfecha ,Reservación archivada. Eventos. En el análisis orientado a objetos el mundo se describe en términos de los objetos y sus estados, así como los eventos que modifican esos estados. Un evento produce un cambio en el estado de un objeto. Los eventos sirven como indicadores de los instantes en que ocurren los cambios de estado. Para saber de los cambios y reaccionar adecuadamente ante ellos, debemos entender y modelar los eventos.
Tipos de Eventos El analista no necesita conocer cada evento que ocurra en una organización: sólo los tipos de eventos. Los tipos de eventos indican los cambios sencillos en el estado de un objeto; por ejemplo, cuando se deposita dinero en una cuenta bancaria o se actualiza el sueldo de un trabajador. Básicamente, los tipos de eventos describen las siguientes formas de cambios de estado: Un objeto se crea. Un objeto se termina. Un objeto se clasifica como una instancia de un tipo de objeto. Un objeto se desclasifica como una instancia de un tipo de objeto. Un objeto cambia de clasificación. Un atributo de un objeto se cambia.
C++ proporciona las herramientas necesarias que permiten definir funciones y operadores que utilizan el mismo nombre o símbolo que una función u operador incorporado. Estas funciones y operadores se dicen que están sobrecargados y se pueden utilizar para redefinir una función u operador definido.
Sobrecarga de funciones
En C++ dos o más funciones pueden tener el mismo nombre representando cada una de ellas un código diferente. Esta característica se conoce como sobrecarga de funciones.
Una función sobrecargada es una función que tiene más de una definición.
Estas funciones se diferencian en el número y tipo de argumentos, pero también hay funciones sobrecargadas que devuelven tipos distintos.
Sobrecarga se refiere al uso de un mismo nombre para múltiples significados de un operador o una función.
Dado el énfasis del concepto de clase, el uso principal de la sobrecarga es con las funciones miembro de una clase. Cuando más de una función miembro con igual nombre se declara en una clase, se dice que el nombre de la función está sobrecargado en esa clase. El ámbito del nombre sobrecargado es el de la clase
La sobrecarga. La sobrecarga se refiere a la posibilidad de tener dos o más funciones con el mismo nombre pero funcionalidad diferente. Es decir, dos o más funciones con el mismo nombre realizan acciones diferentes. El compilador usará una u otra dependiendo de los parámetros usados. A esto se llama también sobrecarga de funciones. También existe la sobrecarga de operadores que al igual que con la sobrecarga de funciones se le da más de una implementación a un operador. Interfaz grafica de usuario
la idea de simplificar el uso de los ordenadores para usuarios de todo tipo y no sólo para los expertos, se ha convertido en una práctica habitual utilizar metáforas visuales por medio de la llamada interfaz gráfica de usuario (IGU ó GUI en inglés) para que el usuario interactúe y establezca un contacto más fácil e intuitivo con el ordenador. Modelo de Casos de Uso del sistema El modelo de casos de uso permite que los desarrolladores del software y los clientes lleguen a un acuerdo sobre los requisitos, es decir, sobre las condiciones y posibilidades que debe cumplir el sistema. Describe lo que hace el sistema para cada tipo de usuario. Actores del sistema Un actor no es más que un conjunto de roles que los usuarios de Casos de Uso desempeñan cuando interaccionan con estos Casos de Uso. Los actores representan a terceros fuera del sistema que colaboran con el mismo. Una vez que hemos identificado los actores del sistema, tenemos identificado el entorno externo del sistema. Ventanas.
El escritorio del sistema operativo Windows de Microsoft y su sistema de ventanas sobre la pantalla se ha estandarizado y universalizado, pero fueron los ordenadores Macintosh de la compañía Apple los El modelo de casos de uso permite que los desarrolladores del software y los clientes lleguen a un acuerdo sobre los requisitos, es decir, sobre las condiciones y posibilidades que debe cumplir el sistema. Describe lo que hace el sistema para cada tipo de usuario. La Estructura de Objetos. Objetos y Tipos de Objetos. Asociaciones de Objetos. Jerarquías de Generalización. Jerarquías Compuestas. Diagramas de relación entre los objetos. Esquemas de Objetos. Ejercicios.
Análisis de la Estructura de Objetos. El análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos. Describe lo que hace el sistema para Análisis del Comportamiento de Objetos. Estados de un Objeto. Eventos. Tipos de Eventos El Ciclo Vital de un Objeto Interacciones entre tipos de objetos Operaciones. Fuentes externas de eventos Reglas de activación Condiciones de Control Subtipos y Supertipos de Eventos.
En el análisis del comportamiento de objetos (ACO) realizamos esquemas de eventos que muestran eventos, la secuencia en que ocurren y cómo los eventos cambian. La mayoría de los objetos tienen un ciclo vital en el que una sucesión de eventos pueden ocurrirle y cada uno de éstos modifica su estado. En este análisis, se dibuja un diagrama que muestre el ciclo vital de un objeto, incluyendo los estados posibles de los objetos, además de los cambios de estado permisibles. Este se denomina diagrama de reja. Este es un diagrama de reja que muestra los estados posibles de un objeto reservación aérea. Las líneas horizontales representan estados y las verticales muestran las transiciones entre estados. do de lLa mayoría de los objetos tienen un ciclo vital en el que una sucesión de eventos pueden ocurrirle y cada uno de éstos modifica su estado. En este análisis, se dibuja un diagrama que muestre el ciclo vital de un objeto, incluyendo los estados posibles de los objetos, además de los cambios de estado permisibles. Este se denomina diagrama de reja. Este es un diagrama de reja que muestra los estados posibles de un objeto reservación aérea. Las líneas horizontales representan estados y las verticales muestran las transiciones entre estados.
La sobrecarga. La sobrecarga se refiere a la posibilidad de tener dos o más funciones con el mismo nombre pero funcionalidad diferente. Es decir, dos o más funciones con el mismo nombre realizan acciones diferentes. El compilador usará una u otra dependiendo de los parámetros usados. A esto se llama también sobrecarga de funciones. También existe la sobrecarga de operadores que al igual que con la sobrecarga de funciones se le da más de una implementación a un operador. Interfaz grafica de usuario
la idea de simplificar el uso de los ordenadores para usuarios de todo tipo y no sólo para los expertos, se ha convertido en una práctica habitual utilizar metáforas visuales por medio de la llamada interfaz gráfica de usuario (IGU ó GUI en inglés) para que el usuario interactúe y establezca un contacto más fácil e intuitivo con el ordenador. Modelo de Casos de Uso del sistema El modelo de casos de uso permite que los desarrolladores del software y los clientes lleguen a un acuerdo sobre los requisitos, es decir, sobre las condiciones y posibilidades que debe cumplir el sistema. Describe lo que hace el sistema para cada tipo de usuario. Actores del sistema Un actor no es más que un conjunto de roles que los usuarios de Casos de Uso desempeñan cuando interaccionan con estos Casos de Uso. Los actores representan a terceros fuera del sistema que colaboran con el mismo. Una vez que hemos identificado los actores del sistema, tenemos identificado el entorno externo del sistema. Ventanas.
El escritorio del sistema operativo Windows de Microsoft y su sistema de ventanas sobre la pantalla se ha estandarizado y universalizado, pero fueron los ordenadores Macintosh de la compañía Apple los El modelo de casos de uso permite que los desarrolladores del software y los clientes lleguen a un acuerdo sobre los requisitos, es decir, sobre las condiciones y posibilidades que debe cumplir el sistema. Describe lo que hace el sistema para cada tipo de usuario. La Estructura de Objetos. Objetos y Tipos de Objetos. Asociaciones de Objetos. Jerarquías de Generalización. Jerarquías Compuestas. Diagramas de relación entre los objetos. Esquemas de Objetos. Ejercicios.
Análisis de la Estructura de Objetos. El análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos. Describe lo que hace el sistema para Análisis del Comportamiento de Objetos. Estados de un Objeto. Eventos. Tipos de Eventos El Ciclo Vital de un Objeto Interacciones entre tipos de objetos Operaciones. Fuentes externas de eventos Reglas de activación Condiciones de Control Subtipos y Supertipos de Eventos.
En el análisis del comportamiento de objetos (ACO) realizamos esquemas de eventos que muestran eventos, la secuencia en que ocurren y cómo los eventos cambian. La mayoría de los objetos tienen un ciclo vital en el que una sucesión de eventos pueden ocurrirle y cada uno de éstos modifica su estado. En este análisis, se dibuja un diagrama que muestre el ciclo vital de un objeto, incluyendo los estados posibles de los objetos, además de los cambios de estado permisibles. Este se denomina diagrama de reja. Este es un diagrama de reja que muestra los estados posibles de un objeto reservación aérea. Las líneas horizontales representan estados y las verticales muestran las transiciones entre estados. do de lLa mayoría de los objetos tienen un ciclo vital en el que una sucesión de eventos pueden ocurrirle y cada uno de éstos modifica su estado. En este análisis, se dibuja un diagrama que muestre el ciclo vital de un objeto, incluyendo los estados posibles de los objetos, además de los cambios de estado permisibles. Este se denomina diagrama de reja. Este es un diagrama de reja que muestra los estados posibles de un objeto reservación aérea. Las líneas horizontales representan estados y las verticales muestran las transiciones entre estados.
La programación Orientada a objetos (POO) es una forma especial de programar, más cercana a como expresaríamos las cosas en la vida real que otros tipos de programación. Con la POO tenemos que aprender a pensar las cosas de una manera distinta, para escribir nuestros programas en términos de objetos, propiedades, métodos y otras cosas que veremos rápidamente para aclarar conceptos y dar una pequeña base que permita ver este tipo de programación. La complejidad del software se desarrolla mediante las personas que son hábiles para lo cual necesitan recopilar información necesaria es decir dominar la problemática del sistema para lo cual se ven enfocados al tratamiento del problema y después a gestionar un proceso mediante el cual desarrollaran el software y así através de eso podrán llevarlo a la practica hasta que atreves del usuario pueda tener la flexibilidad de probarlo, para lo cual el software y la Poo tienen varias aplicaciones en la programación formando grandes estructuras de ellas
Análisis de la Estructura de Objetos. El análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos.
Objetos y Tipos de Objetos. En el análisis se trata de identificar los tipos de objeto más que los objetos individuales en un sistema. Los tipos de objetos se definen en base a la comprensión del analista de nuestro mundo. Un objeto puede categorizarse de variadas formas.
Representación para Tipo de Objeto (Persona). Asociaciones de Objetos. Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad).
Representación para la Asociación entre dos Tipos de Objetos. Un objeto del tipo persona posee cero o muchos objetos del tipo vehículo. Un objeto del tipo vehículo es de un y sólo un objeto del tipo persona. Jerarquías de Generalización. Una de las vías de sentido común por las que el hombre organiza su volumen de conocimiento es el de las jerarquías, de lo más general a lo más específico.
Representación de una Jerarquía de generalización, para el tipo de objeto Persona. En las jerarquías se habla de subtipo o especialización de un supertipo o generalización. En el caso anterior, persona es el supertipo para Empleado y Estudiante, que son sus subtipos. Por otra parte, Empleado es el supertipo para los subtipos Ejecutivo y Vendedor. Los subtipos (niveles inferiores de la jerarquía) heredan las características de sus supertipos, además, cada instancia de un tipo de objeto lo es también de sus supertipos. Jerarquías Compuestas. Un objeto se denomina complejo si está formado por otros. Las jerarquías Compuestas permiten realizar agregaciones de objetos.
tiene más de una definición. Estas funciones se diferencian en el número y tipo de argumentos, pero también hay funciones sobrecargadas que devuelven tipos distintos. Sobrecarga se refiere al uso de un mismo nombre para múltiples significados de un operador o una función. Dado el énfasis del concepto de clase, el uso principal de la sobrecarga es con las funciones miembro de una clase. Cuando más de una función miembro con igual nombre se declara en una clase, se dice que el nombre de la función está sobrecargado en esa clase. El ámbito del nombre sobrecargado es el de la clase. La sobrecarga de funciones amigas es similar a la de funciones miembro, con la única diferencia de que es necesaria la palabra reservada friend al igual que en la declaración de cualquier función amiga. Sobrecarga de operadores De modo análogo a la sobrecarga de funciones, la sobrecarga de operadores permite al programador dar nuevos significados a los símbolos de los operadores existentes en C++. C++ permite a los programadores sobrecargar a los operadores para tipos abstractos de datos.
Una ventana es una parte de la pantalla sobre la que se ejecutará un programa o se realizarán una serie de tareas. Todas ellas poseen una serie de elementos comunes (figura de abajo) tales como: • Barra de títulos: Muestra el nombre de la ventana. Con mucha frecuencia el nombre de la ventana contiene el nombre de la aplicación abierta en ella, seguido del nombre del documento activo. • Barra de menús: Inmediatamente debajo de la barra de títulos de la mayoría de las ventanas, hay un banda horizontal llamada Barra de Menús que contiene nombres tales como Archivo, Edición o ? (Ayuda). Haciendo clic en cualquiera de estos nombres se despliega un menú en forma de persiana, es decir se despliega una lista de comandos. Para escoger uno, basta con desplazar el puntero del ratón sobre el comando correspondiente y hacer clic. Barra de títulos y barra de menús. • Botón de minimizar: Haciendo clic sobre este botón (figura inferior) la ventana se reduce y se coloca su nombre en una barra que está en la parte inferior de la pantalla denominada Barra de Tareas. • Botón de maximizar: En este caso al presionar el botón la ventana aumenta de tamaño hasta ocupar la totalidad de la pantalla. • Botón de restaurar: Una vez maximizada la ventana, el botón de maximizar cambia al de restaurar. Presionando éste, la ventana vuelve al tamaño que poseía antes de ser maximizada. • Botón de cerrar: Cierra una ventana y la aplicación que está abierta. Suele estar en la esquina superior derecha o bien en la esquina superior izquierda en forma de un pequeño icono correspondiente a la aplicación. • Botón de Ayuda: Este botón que aparece en la esquina superior derecha de muchas de las cajas de diálogo, sirve para que Windows muestre información acerca de un elemento de la pantalla. Para ello hacer clic sobre el botón y arrastrar el cursor transformado en un signo de interrogación sobre el objeto de la pantalla que se desconoce o del que se desea obtener una breve explicación.
Cuando se trabaja con Windows XP, a menudo se querrá tener en la pantalla más de una ventana abierta a la vez, y cambiar de una a otra. Para mover una ventana de posición se debe desplazar el puntero del ratón sobre la barra de títulos de la ventana a desplazar, y manteniendo pulsado el botón del ratón, mover éste. Al arrastrar la barra de títulos se desplazará toda la ventana a una nueva posición. Para intercambiar entre dos ventanas se debe tener en cuenta que la ventana activa posee la Barra de Títulos resaltada (de color) mientras que la otra está en color gris. Con Windows es particularmente fácil conmutar ventanas. Para ello hay dos métodos principalmente: haciendo clic sobre la ventana que se desea volver activa o utilizando la Barra de Tareas. Ésta última se verá más adelante.
Para poder realizar cualquier operación dentro de una ventana ésta debe estar activa. Cuando hay dos o más ventanas superpuestas en la pantalla, la ventana activa siempre aparece en primer plano.
Análisis de la Estructura de Objetos. El análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos.
Objetos y Tipos de Objetos. En el análisis se trata de identificar los tipos de objeto más que los objetos individuales en un sistema. Los tipos de objetos se definen en base a la comprensión del analista de nuestro mundo. Un objeto puede categorizarse de variadas formas.
Representación para Tipo de Objeto (Persona). Asociaciones de Objetos. Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad).
Representación para la Asociación entre dos Tipos de Objetos. Un objeto del tipo persona posee cero o muchos objetos del tipo vehículo. Un objeto del tipo vehículo es de un y sólo un objeto del tipo persona. Jerarquías de Generalización. Una de las vías de sentido común por las que el hombre organiza su volumen de conocimiento es el de las jerarquías, de lo más general a lo más específico.
Esquemas de Objetos. La comprensión de un modelo suele ser más sencilla si los tipos de objetos y relaciones se presentan mediante un diagrama de relación entre objetos; los supertipos y subtipos se presentan en un diagrama de jerarquías de generalización y las estructuras compuestas en un diagrama compuesto. Sin embargo, para los usuarios más sofisticados puede ser útil presentarlo todo en un mismo diagrama, el que se denomina esquema de objetos.
Ciclo vital El tiempo de vida o ciclo vital ("Lifetime") de un objeto es una propiedad de tiempo de ejecución ("Runtime"). Viene determinado por el lapso entre su creación y su destrucción. Por supuesto no puede exceder la duración de su almacenamiento. El ciclo vital comienza cuando se le asigna espacio de almacenamiento y, si no es un objeto trivial, cuando el objeto es convenientemente iniciado por su constructor. Finaliza cuando es llamado el destructor o se rehúsa la zona de almacenamiento que le había sido asignada. Nota: decimos que un objeto es trivial cuando es, por ejemplo, un tipo simple preconstruido en el lenguaje. En este caso una expresión del tipo x hasta para que el compilador pueda reservar espacio de almacenamiento. Observe que el ciclo vital de los objetos automáticos y estáticos es controlado automáticamente por el compilador. En los primeros la destrucción se realiza cuando el objeto sale de ámbito. En los segundos la destrucción ocurre con las rutinas de finalización del programa. Por su parte el ciclo vital de los objetos dinámicos es controlado por el programador. Generalmente esta memoria reside en un segmento de datos fijo, situado de acuerdo con el modelo de memoria que se esté utilizando, aunque en los ambientes de 32 bits de PC y compatibles, solo está disponible el denominado modelo plano ("Flat memory model"). Esta última, denominada "dinámica" en la mayoría de los textos, incluyendo la propia literatura inglesa (por ejemplo los manuales de Borland), nos parece un término desafortunado para designar la duración de los objetos almacenados en el montón. Por esta razón preferimos designarlos como objetos "persistentes", ya que esta palabra califica más adecuadamente las características de tales objetos. Precisamente por esto y en especial si se trata de punteros, su uso puede resultar peligroso si no son inicializados correctamente. Hay una excepción en los llamados punteros inteligentes que destruyen el objeto señalado antes de ser ellos mismos destruidos.
Ciclo vital El tiempo de vida o ciclo vital ("Lifetime") de un objeto es una propiedad de tiempo de ejecución ("Runtime"). Viene determinado por el lapso entre su creación y su destrucción. Por supuesto no puede exceder la duración de su almacenamiento.El ciclo vital comienza cuando se le asigna espacio de almacenamiento y, si no es un objeto trivial, cuando el objeto es convenientemente iniciado por su constructor. Finaliza cuando es llamado el destructor o se rehúsa la zona de almacenamiento que le había sido asignada. El ciclo vital de los objetos automáticos y estáticos es controlado automáticamente por el compilador. En los primeros la destrucción se realiza cuando el objeto sale de ámbito. En los segundos la destrucción ocurre con las rutinas de finalización del programa. Por su parte el ciclo vital de los objetos dinámicos es controlado por el programador. El ciclo de vida lo que impone es una estructrura de trabajo, no un paradigma de desarrollo. Nació con la idea de aportar mejores soluciones y enfoques para dirigir sistemas desarrollados en lenguaje OO. Pero estas prácticas pueden escalarse hacia otros tipos de A/D.
Vinculación: el objeto es almacenado igual en la base datos, pero se establece un vínculo con el archivo original de forma que si modificamos el objeto desde el formulario, los cambios afectarán al archivo original. Incrustación: el objeto es almacenado en la base de datos, pero si el objeto original sufre algún cambio, en la base de datos no se reflejará el cambio. Tanto si incrustamos como si vinculamos, el objeto debe crearse en el formulario mediante el control llamado marco de objeto. Podemos utilizar estas opciones para insertar una imagen de una persona como si fuese un campo más de la base de datos. Eventos: Para entender la programación dirigida por eventos, podemos oponerla a lo que no es: mientras en la programación secuencial (o estructurada) es el programador el que define cuál va a ser el flujo del programa, en la programación dirigida por eventos será el propio usuario --o lo que sea que esté accionando el programa-- el que dirija el flujo del programa. En la programación dirigida por eventos, al comenzar la ejecución del programa se llevarán a cabo las inicializaciones y demás código inicial y a continuación el programa quedará bloqueado hasta que se produzca algún evento. Cuando alguno de los eventos esperados por el programa tenga lugar, el programa pasará a ejecutar el código del correspondiente administrador de evento. Cualquier actividad que se realiza en un sistema operativo orientado a eventos se comunica entre los distintos procesos interesados a través de mensajes denominados eventos. Por ejemplo cuando se presiona el botón izquierdo del ratón sobre una ventana de aplicación, el sistema operativo subyacente notifica a la aplicación de dicho suceso para que ésta pueda responder de manera adecuada a esta situación. El código que se encarga de dar respuesta a un evento específico se conoce como procedimiento manejador de evento. Tipos de eventos Eventos del teclado: Ocurren cuando el usuario presiona una tecla determinada como Tabulador o una combinación de teclas como Ctrl+P. Eventos del ratón: Ocurren cuando el usuario mueve el ratón, lo presiona una sóla vez o dos veces o arrastra el ratón a través de la pantalla. Eventos de la aplicación: Ocurren cuando la aplicación es cargada en memoria o cuando se abre o cierra una ventana o forma. Los eventos del teclado y del ratón ocurren cuando el usuario hace algo y los eventos de programación ocurren cuando el código hace algo, por ejemplo dar la indicación de cerrar la forma actual. Funciones miembro Función miembro es aquella que está declarada en ámbito de clase. Son similares a las funciones habituales, con la salvedad de que el compilador realizara el proceso de Decoración de nombre (Name Mangling en inglés): Cambiara el nombre de la función añadiendo un identificador de la clase en la que está declarada, pudiendo incluir caracteres especiales o identificadores numéricos. Las funciones miembro se invocan accediendo primero al objeto al cual refieren, con la sintaxis: myobject.mymemberfunction(), esto es un claro ejemplo de una función miembro.
Objetos y Miembros: Los objetos están compuestos de miembros. Los miembros son características, propiedades, métodos, y eventos, y representan los datos y la funcionalidad que caracterizan al objeto. Las propiedades representan los datos miembros de un objeto. Los métodos son acciones que el objeto puede realizar, y los eventos son notificaciones que un objeto envía o recibe hacia otros objetos cuando una actividad sucede. Constructor: Método que devuelve un objeto de la clase a la que el constructor pertenece. Los constructores, habitualmente permiten asignar valores a todos o algunos datos del objeto que van a generar. Destructor : Método que libera cualquier recurso requerido por el objeto durante su creación o existencia. Destructor por defecto: Al igual que existe un constructor por defecto, existe un destructor por defecto. Este método, elimina de memoria el objeto al terminarse el ámbito de la variable que lo contiene, recuperando para su uso la porción de memoria que el objeto ocupaba. El operador de envío: Para poder mandar mensajes a los objetos, necesitamos un operador, a este le llamamos el operador de envío. Cada lenguaje puede tener el suyo, pero es frecuente que se utilicen los dos puntos (':')o el punto ('.') (en C++ es el punto simple, igual que para referirnos a los elementos de los struct's). El operador de envío hace que se ejecute la porción del código agrupada bajo el nombre del método, y el método trabajará con los datos propios de la instancia de la clase a ala que se refiera. Herencia Un objeto es heredero de otro cuando posee todas sus propiedades y todos sus métodos y reconoce todos sus eventos, aunque pueda disfrutar de propiedades, métodos y eventos adicionales. Se define la herencia como la característica que tienen los objetos de derivarse unos de otros. Por otra parte la herencia supone una clase base y una jerarquía de clases que contienen las clases derivadas de la clase base, así las clases derivadas pueden heredar las propiedades y métodos de una clase base, añadiendo sus propios métodos y propiedades, incluso cambiar aquellos elementos de la clase base que necesiten sean diferentes. Tipos de Herencia: Existen dos tipos de herencia Herencia Simple: En esta jerarquía cada clase tiene como máximo una sola superclase. La herencia simple permite que una clase herede las propiedades y métodos de su superclase en una cadena jerárquica. Herencia múltiple: Una malla o retícula consta de clases, cada una de las cuales pueden tener dos o más superclases inmediatas. Una herencia múltiple es aquella en la que cada clase puede heredar las propiedades y métodos de cualquier número de clases.
SOBRECARGA En programación orientada a objetos la sobrecarga se refiere a la posibilidad de tener dos o más funciones con el mismo nombre pero funcionalidad diferente. Es decir, dos o más funciones con el mismo nombre realizan acciones diferentes. . INTERFAZ GRAFICA La interfaz gráfica de usuario, es un tipo de interfaz que utiliza un conjunto de imágenes y objetos gráficos para representar la información y acciones disponibles en la interfaz. La interfaz gráfica de usuario es el artefacto tecnológico de un sistema interactivo que posibilita, a través del uso y la representación del lenguaje visual, una interacción amigable con un sistema informático.
Manejo de ventanas en Windows
Una ventana es una parte de la pantalla sobre la que se ejecutará un programa o se realizarán una serie de tareas. Todas ellas poseen una serie de elementos comunes tales como: • Barra de títulos: Muestra el nombre de la ventana. Con mucha frecuencia el nombre de la ventana contiene el nombre de la aplicación abierta en ella, seguido del nombre del documento. • Barra de menús: Inmediatamente debajo de la barra de títulos de la mayoría de las ventanas, hay un banda horizontal llamada Barra de Menús que contiene nombres tales como Archivo, Edición o ? (Ayuda). Haciendo clic en cualquiera de estos nombres se despliega un menú en forma de persiana, es decir se despliega una lista de comandos. Para escoger uno, basta con desplazar el puntero del ratón sobre el comando correspondiente y hacer clic. Análisis de la Estructura de Objetos. El análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos.
Objetos y Tipos de Objetos. En el análisis se trata de identificar los tipos de objeto más que los objetos individuales en un sistema. Los tipos de objetos se definen en base a la comprensión del analista de nuestro mundo. Un objeto puede categorizarse de variadas formas.
Representación para Tipo de Objeto (Persona)
Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad).
Representación para la Asociación entre dos Tipos de Objetos. Un objeto del tipo persona posee cero o muchos objetos del tipo vehículo. Un objeto del tipo vehículo es de un y sólo un objeto del tipo persona.
Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad).
Representación para la Asociación entre dos Tipos de Objetos. Un objeto del tipo persona posee cero o muchos objetos del tipo vehículo. Un objeto del tipo vehículo es de un y sólo un objeto del tipo persona.
Jerarquías de Generalización. Una de las vías de sentido común por las que el hombre organiza su volumen de conocimiento es el de las jerarquías, de lo más general a lo más específico.
Representación de una Jerarquía de generalización, para el tipo de objeto Persona. En las jerarquías se habla de subtipo o especialización de un supertipo o generalización. Ejemplo. profesor: supertipo, vocero: supertipo, estudiantes: subtipo. Jerarquías Compuestas. Un objeto se denomina complejo si está formado por otros. Las jerarquías Compuestas permiten realizar agregaciones de objetos. Ejemplo. Universidad – coordinación – escaleras - salón – pupitres. Universidad se compone de un objeto, del tipo a su vez el objeto de coordinación de tipo universidad que pueden ser varias u objetos de salón y pupitres. Diagramas de relación entre los objetos. Los tipos de objetos están relacionados con otros tipos de objeto. Estudiante: Richard profesor: Alquimedes Materia: Programacion
Diagrama de Relación entre objetos. Un objeto del tipo cliente puede ordenar muchos objetos del tipo pedidos, y un objeto del tipo pedido es ordenado por un y sólo un objeto del tipo cliente. Un objeto del tipo producto está en muchos o ningún objeto del tipo pedido, mientras que un objeto del tipo pedido tiene al menos un objeto del tipo producto.
Análisis del Comportamiento de Objetos. Estados de un Objeto. Eventos. Tipos de Eventos El Ciclo Vital de un Objeto Estados de un Objeto. Un objeto puede existir en varios estados. Tales tipos de objetos suelen percibirse como estados posibles del ciclo vital de un objeto. Sin embargo, un objeto puede tener una gran variedad de perspectivas de ciclos vitales. El estado de un objeto es la colección de asociaciones que tiene un objeto.
Eventos. En el análisis orientado a objetos el mundo se describe en términos de los objetos y sus estados, así como los eventos que modifican esos estados. Un evento produce un cambio en el estado de un objeto. Los eventos sirven como indicadores de los instantes en que ocurren los cambios de estado. Tipos de Eventos El analista no necesita conocer cada evento que ocurra en una organización: sólo los tipos de eventos. • Un objeto se crea. • Un objeto se termina. • Un objeto se clasifica como una instancia de un tipo de objeto. • Un objeto se desclasifica como una instancia de un tipo de objeto. • Un objeto cambia de clasificación. • Un atributo de un objeto se cambia. Los objetos pueden asociar un objeto con otro. Un evento clasificará al objeto como empleado.
El Ciclo Vital de un Objeto La mayoría de los objetos tienen un ciclo vital en el que una sucesión de eventos pueden ocurrirle y cada uno de éstos modifica su estado. Todo puede variar de acuerdo de las modificaciones posibles a los objetos.
Historia de la Programación Orientado a Objeto (POO): (Exposición)
Al mismo tiempo que se da la Crisis del Software, por otro lado la Orientación a Objetos (OO) se empezóa discutir a fines de los años 60 con el desarrollo del lenguaje SIMULA67 por Nygaard y Ole-Johan Dahlen el Centro de Cálculo Noruego, en él, introdujeron los conceptos de clase, subclases y rutinas, muy parecidos los conceptos a los lenguajes orientados a objetos de hoy en día. A mitad de la década de los 70 los científicos del Centro de Investigaciones Palo Alto de XEROX (PARC) (XEROX Palo Alto Research Center) crearon el lenguaje SMALLTALK, el primer lenguaje orientado a objetos consistente y completo. En él cada elemento del lenguaje fue realizado un objeto. Este último lenguaje evolucionó a través de varios lanzamientos realizados por PARC. A pesar de este movimiento temprano hacia los lenguajes orientados a objetos, sólo se lograron pequeñas incursiones en la comunidad de la programación general. El progreso reciente se ha acelerado debido principalmente a la disponibilidad de las extensiones orientadas a objetos para dos lenguajes populares: C y PASCAL, y a las extensiones prometidas para otros lenguajes comerciales populares como BASIC y COBOL.
1era Evaluación 03/11/2009 (Taller)
La sobrecarga se refiere a la práctica de cargar una función con mas un significado. Básicamente el termino expresa que se cargan con uno o mas identificadores de función sobre un identificador previo. El diseño de interfaces gráficas: Es una aplicación que estudia y trata de poner en práctica procesos orientados a construir la interfaz mas visible posible, dada ciertas condiciones de entorno.
Análisis de la Estructura de Objetos: (AEO), define las categorías de los objetos que percibimos y las formas en que los asociamos. En el análisis se trata de identificar los tipos de objetos más que los objetos individuales en un sistema.
Análisis del Comportamiento de Objetos: (ACO), en el realizamos esquemas de cuentos que muestran eventos, la secuencia en que ocurren y como los eventos cambian el estado de los objetos.
Ciclo vital de un objeto: La mayoría de los objetos tiene un ciclo vital en el que una sucesión de eventos pueden ocurrirle y cada uno de éstos modifica su estado. En este análisis, se dibuja un diagrama que muestra el ciclo vital de un objeto, incluyendo los estados posibles de los objetos, además de los cambios de estado permisibles. Este se denomina diagrama de reja.
Diagrama de reja que muestra los estados posibles de un objeto reservación aérea. Las líneas horizontales representan estados y las verticales demuestran las transacciones entre estados
Objetos: Un objeto es una entidad lógica que contiene datos y un código que manipula estos datos;
Abstracción: En el sentido mas general, una abstracción es una representación concisa de una idea o de un objeto complicado. En un sentido mas especifico, la abstracción localiza y oculta los detalles de un modelo o diseño para generar y manipular objetos.
Clase: Podemos considerar una clase como una colección de objetos que poseen características y operaciones comunes. Una clase contiene toda la información necesaria para crear nuevos objetos.
Herencia: La herencia es un proceso mediante el cual un objeto puede adquirir las propiedades de otro objeto.
Encapsulación: Es una técnica que permite localizar y ocultar los detalles de un objeto. La encapsulación previene que un objeto sea manipulado por operaciones distintas de las definidas. La encapsulación es como una caja negra que esconde los datos y solamente permite acceder a ellos de forma controlada.
Polimorfismo: Significa que un nombre se puede utilizar para especificar una clase genérica de acciones
Un evento es un mensaje que un objeto envía cuando se produce una situación determinada sobre dicho objeto, y que podrá ser respondido o no por el código de la aplicación.
Tipos de eventos: Eventos del mouse. OnClick: Este evento ocurre cuando el usuario hace clic dentro del área de la forma. Eventos del teclado. Estos eventos suceden cuando el usuario presiona un determinada tecla. Eventos de sistema. No todos los eventos ocurren por acciones que realice el usuario, algunos son ejecutados por el sistema operativo Windows.
Funciones Miembros Se les llama así a las funciones que realizan operaciones con los datos de un objeto. También llamados funciones miembro. Los datos privados de una clase sólo pueden ser modificados por medio de las funciones miembro -todos los métodos de esa clase y sólo los de esa clase-.
Constructores Los constructores son procedimientos de la clase que permiten crear objetos. Un constructor es llamado para asignar memoria a un objeto, para asignar valores a los datos del objeto y realizar tareas iniciales para un nuevo objeto. Esto implique que si no podemos trabajar con un objeto que no haya sido creado a través de un constructor y si sólo se pueden modificar mediante los procedimientos de la clase NO TENEMOS FORMA DE CORROMPER EL OBJETO, lo cual aumenta la confiabilidad y facilita la rehusabilidad. Método que devuelve un objeto de la clase a la que el constructor pertenece. Los constructores, habitualmente permiten asignar valores a todos o algunos datos del objeto que van a generar.` Un constructor es una función especial que es miembro de esa clase y que tiene el mismo nombre de la clase. Es muy frecuente que una cierta parte de un objeto necesite una iniciación antes de que pueda ser utilizada; como el requisito de iniciación es tan frecuente C++ permite que los objetos se den a sí mismos valores iniciales cuando se crean. Esta iniciación automáticamente se lleva a cabo mediante el uso de una función de construcción o constructor. La función de construcción de un objeto se invoca cuando se crea el objeto. Esto significa que se invoca cuando se ejecuta la declaración del objeto. Además, para los objetos locales, el constructor se invoca cada vez que se llega a la declaración del objeto. Como lo dice el nombre, un constructor es una función que se utiliza para construir un objeto de una clase dada; esto puede implicar la presencia de diferentes escenarios.
1.- Creación de objetos con iniciación definida. 2.- Creación de objetos con iniciación especifica. 3.- Creación de objetos copiando otro objeto. Cada uno de estos procesos implica un tipo diferente de constructor. Un constructor tiene el nombre de la clase a la que pertenece.
Un constructor private, impediría que los usuarios genéricos crearan objetos a partir de esa clase y forzarán el cumplimiento de una de las condiciones siguientes antes de que se pueda crear un objeto.
1.- Un miembro estático de la clase invoca al constructor. 2.- Una clase friend de esa clase invoca al constructor. 3.- Un objeto existente de la clase tiene una función miembro que crea nuevos objetos invocando al constructor. Constructores con argumentos. La función básica de un constructor consiste en inicializar un objeto antes de usarlo. Constructores para copiar objetos. Cuando se crea un objeto, a menudo no se desea inicializar ningún valor de manera específica; simplemente se desea que un objeto “sea como otro”. Esto implica hacer una copia de un objeto preexistente, lo cual requiere un tipo especial de construcción, llamada en general: constructor de copia.
Destructores Un destructor es un procedimiento de la clase que realiza la tarea opuesta a su constructor, libera la memoria que fue asignada al objeto que fue creado por el constructor. Es deseable que el destructor se invoque implícitamente cuando el objeto abandone el bloque donde fue declarado. El destructor le permite al programador despreocuparse de tener que liberar la memoria que deja de utilizar y correr el riesgo de que ésta se sature. Método que libera cualquier recurso requerido por el objeto durante su creación o existencia. Los destructores entran en la misma categoría que los constructores. Se utilizan para realizar ciertas operaciones que son necesarias cuando ya no se utiliza un objeto como es la liberación de memoria.
Existen algunas diferencias importantes entre los constructores y los destructores:
1.- Los destructores pueden ser virtuales, los constructores NO. 2.- A los destructores no se les puede mandar argumentos. 3.- Sólo se puede declarar un destructor para una clase dada.
El destructor se nombra como la clase pero este va precedido de un tilde (~). El destructor se utiliza para cerrar el dispositivo gráfico y rechazar cualquier espacio de memoria asignado al objeto.
Herencia. La herencia es un mecanismo que para expresar similaridad entre clases, simplificando definiciones De clases similares previamente detenidas. • La herencia simple es cuando el lenguaje sólo permite que una clase derive de una clase. • La herencia múltiple es cuando una clase puede ser derivada de más de una clase.
Una clase puede heredar los atributos de dos o más clases. Para lograr esto, se utiliza una lista de herencia separada mediante comas en la lista de clases base de la clase derivada. La herencia es uno de los rasgos fundamentales de un lenguaje de programación orientado a objetos. En C++, la herencia se basa en permitir que una clase contenga a otra clase en su declaración;
Tipos De Herencias
Herencia múltiple Cuando una clase hija deriva de más de una clase padre; con lo que adquiere los datos y métodos de todas las clases de las cuales deriva.
Una clase puede heredar los atributos de dos o más clases. Para lograr esto, se utiliza una lista de herencia separada mediante comas en la lista de clases base de la clase derivada.
Eventos Es el suceso donde interactua el usuario con la máquina, enviando el mensaje adecuado al objeto respectivo. También se puede definir como evento, a la reacción que desencadena un objeto, es decir la acción que genera.
Como se produce un evento? Cada vez que se produce un evento sobre un determinado tipo de control, se ejecuta una determinada función o procedimiento que realiza la acción programada por el usuario para ese evento concreto. Estos procedimientos se definen con un nombre que se forma a partir del nombre del objeto y el nombre del evento, separados por el carácter (_), como por ejemplo txtBox_click, que es el nombre del procedimiento que se ocupará de responder al evento click en el objeto txtBox.
Tipos de Eventos
- Eventos relacionados al formulario Inicio del formulario. Respuesta a una acción (de usuario). Vinculación de los objetos. Cierre del formulario.
- Eventos relacionados al puntero del ratón El click sobre un botón, Hacer doble click sobre el nombre de un fichero para abrirlo, Arrastrar un icono, etc,
- Eventos relacionados con gráficos Color de texto. Dibujar una caja de texto. Imprimir.
- Eventos personalizados (generados por el usuario) El usuario declara un evento al módulo myClass, utilizando la instrucción Event para declarar un evento con los argumentos que se desea. Los eventos deben ser declarados con Public. Disparando el eventos de acuerdo a la clase, usando la instrucción RaiseEvent, suministrando los parámetros requeridos.
Vinculación de los Objetos (Polimorfismo) Es la asociación de un atributo con su valor - Variable con un valor. - Llamada a función con el cuerpo de la función.
Puede ser: Estática (early binding): en tiempo de compilación o antes de ejecutar. C++, Pascal, COBOL, FORTRAN
Dinámica (late binding): en tiempo de ejecución. C++, Smalltalk, Objetive-C, Java Ejemplo:
Cuando una variable de un tipo Coche posee una referencia a un objeto de clase Taxi (siendo Taxi descendiente de Coche) y se invoca a un método por medio de la variable. Con la vinculación dinámica se asociará la ejecución al tipo más específico, en este caso a Taxi.
El mecanismo para la búsqueda empieza por el tipo dinámico de la variable receptora y remontarse por la jerarquía de herencia hasta encontrar una implementación válida.
Funciones Miembro Generalmente en las clases se suelen ubicar los datos miembros bajo la etiqueta private, y las funciones miembro bajo la etiqueta public, esto favorece a una buena ingeniería de software. La idea es que los clientes de las clases no puedan acceder directamente a los datos miembros de la clase, sino a través de las funciones miembro y sólo cuando sea necesario. Si intentaramos acceder a un dato miembro privado, obtendríamos un error en tiempo de compilación que nos alertaría.
Clasificación de las funciones miembro
- Funciones Set: Permite acceder a los datos miembros de la clase y asignarle un valor. Permite generar datos miembros en la clase y asignar controles para que sólo puedan establecerse datos miembros válidos. Ejemplo: Set establecerTitulo, Set establecerPaginas, Set establecerCodigo.
- Funciones GET: Permite obtener valores de los datos miembro para luego dirigir la salida de los datos de diferente manera. Ejemplo: Get imprime().
- Funciones predicado: Permite verifican la falsedad o veracidad de una condición. Ejemplo: En una clase Libro, se tiene una función miembro llamada hayStock, Esta función tendrá un valor True si el número de stock es mayor que cero y False si es menor que cero.
- Funciones de utilidad: No pueden ser definidas bajo la etiqueta public. El usuario no puede tener acceso directamente. Son de utilidad para otras funciones miembro de la clase.
Concepto de Grafo Los grafos son un conjunto de puntos, de los cuales algún par de ellos está conectado por unas líneas. Si estas líneas son flechas, hablaremos de grafo dirigido (digrafo), mientras que si son simples líneas estamos ante un grafo no dirigido. Más formalmente se pueden definir como un conjunto de vértices y un conjunto de aristas. Cada arista es un par (u,v), donde u y v pertenecen al conjunto de vértices. Si este par es ordenado el grafo es dirigido. Par de ejemplos: Grafo no dirigido Grafo dirigido.
Un grafo consta de vértices (o nodos) y aristas. Los vértices son objetos que contienen información y las aristas son conexiones entre vértices. Para representarlos, se suelen utilizar puntos para los vértices y líneas para las conexiones, aunque hay que recordar siempre que la definición de un grafo no depende de su representación. Un camino entre dos vértices es una lista de vértices en la que dos elementos sucesivos están conectados por una arista del grafo. Así, el camino AJLOE es un camino que comienza en el vértice A y pasa por los vértices J,L y O (en ese orden) y al final va del O al E. El grafo será conexo si existe un camino desde cualquier nodo del grafo hasta cualquier otro. Si no es conexo constará de varias componentes conexas. Un camino simple es un camino desde un nodo a otro en el que ningún nodo se repite (no se pasa dos veces). Si el camino simple tiene como primer y último elemento al mismo nodo se denomina ciclo. Cuando el grafo no tiene ciclos tenemos un árbol (ver árboles). Varios árboles independientes forman un bosque. Un árbol de expansión de un grafo es una reducción del grafo en el que solo entran a formar parte el número mínimo de aristas que forman un árbol y conectan a todos los nodos. Según el número de aristas que contiene, un grafo es completo si cuenta con todas las aristas posibles (es decir, todos los nodos están conectados con todos), disperso si tiene relativamente pocas aristas y denso si le faltan pocas para ser completo. Las aristas son la mayor parte de las veces bidireccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A: estos son llamados grafos no dirigidos. Sin embargo, en ocasiones tenemos que las uniones son unidireccionales. Estas uniones se suelen dibujar con una flecha y definen un grafo dirigido. Cuando las aristas llevan un coste asociado (un entero al que se denomina peso) el grafo es ponderado. Una red es un grafo dirigido y ponderado.
Ordenamiento Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento. El ordenamiento se efectúa con base en el valor de algún campo en un registro. El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado. Ej. de ordenamientos: Dir. Telefónico, tablas de contenido, bibliotecas y diccionarios, etc. El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente. Tipos de ordenamientos: Los 2 tipos de ordenamientos que se pueden realizar son: los internos y los externos. Los internos: Son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo (a [1], a[500], etc.). Los externos: Son aquellos en los que los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc.), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada (posición 1, posición 500, etc.). Clasificación de los algoritmos de ordenamiento de información: El hecho de que la información está ordenada, nos sirve para poder encontrarla y accesarla de manera más eficiente ya que de lo contrario se tendría que hacer de manera secuencial. Algoritmos de inserción: En este tipo de algoritmo los elementos que van a ser ordenados son considerados uno a la vez. Cada elemento es INSERTADO en la posición apropiada con respecto al resto de los elementos ya ordenados. Entre estos algoritmos se encuentran el de INSERCION DIRECTA, SHELL SORT, INSERCION BINARIA y HASHING. Algoritmos de intercambio: En este tipo de algoritmos se toman los elementos de dos en dos, se comparan y se INTERCAMBIAN si no están en el orden adecuado. Este proceso se repite hasta que se ha analizado todo el conjunto de elementos y ya no hay intercambios. Entre estos algoritmos se encuentran el BURBUJA y QUICK SORT. Algoritmos de selección: En este tipo de algoritmos se SELECCIONA o se busca el elemento más pequeño (o más grande) de todo el conjunto de elementos y se coloca en su posición adecuada. Este proceso se repite para el resto de los elementos hasta que todos son analizados. Entre estos algoritmos se encuentra el de SELECCION DIRECTA. Algoritmos de enumeración: En este tipo de algoritmos cada elemento es comparado contra los demás. En la comparación se cuenta cuántos elementos son más pequeños que el elemento que se está analizando, generando así una ENUMERACION. El número generado para cada elemento indicará su posición.
Los métodos simples son: Inserción (o por inserción directa), selección, burbuja y shell, en dónde el último es una extensión al método de inserción, siendo más rápido. Los métodos más complejos son el quick-sort (ordenación rápida) y el heap sort. METODO DE INSERCIÓN. Este método toma cada elemento del arreglo para ser ordenado y lo compara con los que se encuentran en posiciones anteriores a la de él dentro del arreglo. Si resulta que el elemento con el que se está comparando es mayor que el elemento a ordenar, se recorre hacia la siguiente posición superior. Si por el contrario, resulta que el elemento con el que se está comparando es menor que el elemento a ordenar, se detiene el proceso de comparación pues se encontró que el elemento ya está ordenado y se coloca en su posición (que es la siguiente a la del último número con el que se comparó). MÉTODO DE SELECCIÓN. El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo. MÉTODO BURBUJA. El bubble sort, también conocido como ordenamiento burbuja, funciona de la siguiente manera: Se recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo va recorriendo de posición en posición hasta ponerlo en su lugar.
Algoritmo Shell 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. El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones: El ordenamiento por inserción es eficiente si la entrada está "casi ordenada". El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez. ShellSort no es estable porque se puede perder el orden relativo inicial con facilidad cuando usamos incrementos grandes, ya que mira los 2 números separados por ese incremento y nada de lo al medio de esos 2 números es considerado para conservar el orden inicial. Si usáramos solo incremento 1 ahí tendríamos estabilidad, pero dejaría de ser ShellSort y pasaría a ser BubbleSort. - No requiere memoria adicional, todo se ordena solo con una o dos variables temporales para hacer los intercambios. - Usa la comparación en el WHILE más interno por lo tanto está en la categoría de los comparativos. -El tiempo que requiere este algoritmo depende siempre de que sucesión de Incrementos se use. Algoritmo Quicksort El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Descripción del algoritmo [editar] El algoritmo fundamental es el siguiente: Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote. Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada. La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n•log n). En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos esta ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente. Algoritmo Heapsort El ordenamiento por montículos (heapsort en inglés) es un algoritmo de ordenamiento no recursivo, no estable, con complejidad computacional O (n log n). Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él. Algoritmo de búsqueda Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento concreto dentro de una estructura de datos. Consiste en solucionar un problema de existencia o no de un elemento determinado en un conjunto finito de elementos, es decir, si el elemento en cuestión pertenece o no a dicho conjunto, además de su localización dentro de éste. Búsqueda secuencial Se utiliza cuando el contenido del vector no se encuentra o no puede ser ordenado. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del arreglo hasta que éste se encuentre, o hasta que se llegue al final del arreglo. La existencia se puede asegurar desde el momento que el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo. Búsqueda binaria (dicotómica) Se utiliza cuando el vector en el que queremos determinar la existencia o no de un elemento está ordenado, o puede estarlo, este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente con el número de iteraciones. Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del arreglo (normalmente el elemento central), si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del arreglo que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del arreglo que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible, con el elemento buscado como elemento central. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en el arreglo.
Búsqueda Lineal Algoritmos de búsqueda lineal son los 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).
Hash Hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo. Una función de hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo). Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada. Una propiedad fundamental del hashing es que si dos resultados de una misma función son diferentes, entonces las dos entradas que generaron dichos resultados también lo son. Es posible que existan claves resultantes iguales para objetos diferentes, ya que el rango de posibles claves es mucho menor que el de posibles objetos a resumir (las claves suelen tener en torno al centenar de bits, pero los ficheros no tienen un tamaño límite). Son usadas en múltiples aplicaciones, como los arrays asociativos, criptografía, procesamiento de datos y firmas digitales, entre otros. Una buena función de hash es una que experimenta pocas colisiones en el conjunto esperado de entrada; es decir que se podrán identificar unívocamente las entradas (ver función inyectiva). FUNCIONES HASH Ó HASHING El método llamado por transformación de claves (hash), permite aumentar la velocidad de búsqueda sin necesidad de tener los elementos ordenados. Cuenta también con la ventaja de que el tiempo de búsqueda es prácticamente independiente del número de componentes del arreglo. Trabaja basándose en una función de transformación o función hash (H) que convierte una clave en una dirección (índice) dentro del arreglo. Dirección ¬ H (clave) Cuando se tienen claves que no se corresponden con índices (p. ejem. por ser alfanuméricas), o bien cuando las claves son valores numéricos muy grandes, debe utilizarse una función hash que permita transformar la clave para obtener una dirección apropiada. Esta función hash debe de ser simple de calcular y debe de asignar direcciones de la manera mas uniforme posible. Es decir, dadas dos claves diferentes debe generar posiciones diferentes. Si esto no ocurre (H (K1)=d, H (K2)=d y K1¬K2), hay una colisión. Se define, entonces, una colisión como la asignación de una misma dirección a dos o más claves distintas. Por todo lo mencionado, para trabajar con este método de búsqueda debe elegirse previamente: • Una función hash que sea fácil de calcular y que distribuya uniformemente las claves. • Un método para resolver colisiones. Si estas se presentan se debe contar con algún método que genere posiciones alternativas. Función Módulo (por división) Consiste en tomar el residuo de la división de la clave entre el número de componentes del arreglo. La función hash queda definida por la siguiente formula: H (K) = (K mod N) + 1 Se recomienda que N sea el número primo inmediato inferior al número total de elementos.
Función Centro de Cuadrados Consiste en elevar al cuadrado la clave y tomar los dígitos centrales como dirección. El numero de dígitos a tomar queda determinado por el rango del índice. La función hash que definida por la sig. Formula: H (K) = digitos_centrales (K²) + 1 Función Plegamiento Consiste en dividir la clave en partes de igual numero de dígitos (la ultima puede tener menos dígitos) y operar con ellas, tomando como dirección los dígitos menos significativos. La operación entre las partes puede hacerse por medio de sumas o multiplicaciones. La función hash queda definida por la sig. Formula: H (K) = dígnense ((d1...di) + (di + 1...dj) +... + (d1...dn)) + 1 Función Truncamiento Consiste en tomar algunos dígitos de la clave y formar con ellos una dirección. La función hash queda definida por la sig. Fórmula: H (K) = elegirdigitos (d1, d2...dn) + 1 Análisis de algoritmos El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes. A la hora de realizar un análisis teórico de algoritmos es corriente calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota superior asintótica, y las notaciones omega y theta se usan con esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(log(n)), coloquialmente "en tiempo logarítmico". Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen porque tener la misma eficiencia. No obstante la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas por una constante multiplicativa llamada constante oculta.
La medida exacta (no asintótica) de la eficiencia a veces puede ser computada pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo, llamada modelo de computación. Un modelo de computación puede definirse en términos de un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos una búsqueda binaria tiene n elementos, y podemos garantizar que una única búsqueda binaria puede realizarse en un tiempo unitario, entonces se requieren como mucho log2 N + 1 unidades de tiempo para devolver una respuesta.
Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usan algoritmos, porque tienen más precisión y así les permite saber cuanto tiempo pueden suponer que tomará la ejecución. Para algunas personas, como los desarrolladores de videojuegos, una constante oculta puede significar la diferencia entre éxito y fracaso.
Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido, debemos garantizar que el tiempo requerido para realizar un paso esté acotado superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuesto puede no estar garantizado en ciertos contextos. Si por ejemplo los números involucrados en la computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la adición requiere un tiempo constante (usando papel y lápiz, compara el tiempo que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlo con enteros de 1000 dígitos).
CONCEPTO. Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices. Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc. La notación G = A (V, A) se utiliza comúnmente para identificar un grafo. Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo. CLASIFICACION DE GRAFOS Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes. Algunos de los principales tipos de grafos son los que se muestran a continuación: • 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 Kn. A continuación pueden verse los dibujos de K3, K4, K5 y K6 • Un grafo bipartito regular: se denota Km,n 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.
• 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.
• Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.
GRAFOS EULERIANOS. Para definir un camino euleriano es importante definir un camino euleriano primero. Un camino euleriano se define de la manera más sencilla como un camino que contiene todos los arcos del grafo. Teniendo esto definido podemos hablar de los grafos eulerianos describiéndolos simplemente como aquel grafo que contiene un camino euleriano. Como ejemplos tenemos las siguientes imágenes: El primer grafo de ellos no contiene caminos eulerianos mientras el segundo contiene al menos uno.
GRAFOS CONEXOS. Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”.
ÁRBOLES. Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también acíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos).
BOSQUES DE ÁRBOLES. Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos. Como ejemplo tenemos la siguiente figura. RECORRIDO DE UN GRAFO. Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida. Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura; y el recorrido en profundidad.
• Recorrido en anchura: El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.
• Recorrido en profundidad: el recorrido en profundidad trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente. REPRESENTACIÓN DE GRAFOS EN PROGRAMAS. Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas. • Representación mediante matrices: La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.
• Representación mediante listas: En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.
• Representación mediante matrices dispersas: Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.
DÍGRAFO (GRAFO DIRIGIDO). A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas, como en el siguiente caso. Un grafo es una estructura capaz de representar relaciones complejas entre objetos de un mismo tipo. Formalmente se representa mediante el par G = (V, A), donde: V es un conjunto de objetos llamados vértices o nodos A es un conjunto de objetos denominados aristas o arcos. Las aristas representan relaciones entre los vértices, de forma que una arista es un par (u, v) de vértices de V Básicamente, podemos clasificar los grafos en 4 tipos dependiendo de dos criterios: Grafo dirigido. Es aquel cuyas aristas forman pares ordenados (u à v). Grafo no dirigido. Es aquel cuyas aristas no son pares ordenados. Grafo etiquetado o valorado. Cuando se asocia información a cada arista de un grafo. Grafo no etiquetado. Cuando no se asocia ninguna información a las aristas La teoría de grafos se aplica a campos tan diversos como química, geografía, ingeniería eléctrica, comunicaciones, etc. Un ejemplo de grafo podría ser la red de metro de Madrid, donde los vértices representan las estaciones y las aristas la línea que une dos estaciones: Otro ejemplo de aplicación de los grafos es la construcción de modelos donde se estudian las relaciones de precedencia que existen entre las tareas que se necesitan para completar un trabajo. El TAD Grafo Sol Gran Vía Tribunal Plaza de España Opera Callao Tirso de Molina 130 120 150 120 160 125 Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo. Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas. Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.
Historia El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología. En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos. En 1852 Francis Guthrie planteó el problema de los cuatro colores que plantea si es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel yWolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.
Estructuras de datos en la representación de grafos Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las características del grafo y elalgoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.
Estructura de lista lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas. lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra. En esta estructura de datos la idea es asociar a cada vértice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vértices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.
Estructuras matriciales Matriz de incidencia - El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (1 - conectado, 0 - no conectado) Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño n2, donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento mx,y es 1, de lo contrario, es 0.
El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n2) operaciones para ordenar una lista de n elementos. Su funcionamiento es el siguiente: Buscar el mínimo elemento de la lísta 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
De esta manera se puede escribir el siguiente seudocódigo para ordenar una lista de n elementos indexados desde el 1: para i=1 hasta n-1 minimo = i; para j=i+1 hasta n si lista[j] < lista[minimo] entonces minimo = j /* (!) */ fin si fin para intercambiar(lista[i], lista[minimo]) fin para Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación intercambiar() sería más costosa en este caso. Este algoritmo realiza muchas menos operaciones intercambiar () que el de la burbuja, por lo que lo mejora en algo. Si la línea comentada con (!) se sustituyera por intercambiar (lista[i], lista[j]) tendríamos una versión del algoritmo de la burbuja (naturalmente eliminando la orden intercambiar del final). Otra desventaja de este algoritmo respecto a otros como el de burbuja o de inserción directa es que no mejora su rendimiento cuando los datos ya están ordenados o parcialmente ordenados. Así como, por ejemplo, en el caso de la ordenación de burbuja se requeriría una única pasada para detectar que el vector ya está ordenado y finalizar, en la ordenación por selección se realizarían el mismo número de pasadas independientemente de si los datos están ordenados o no. Ejemplo de varios lenguajes de Programación: Java public static int[] selección (int[] v) { int min, aux;
for (int i = 0; i < v.length; i++){ min = i; for (int j = i + 1; j < v.length; j++){ if (v[min] > v[j]){ min = j; } } aux = v[i]; v[i] = v[min]; v[min] = aux; } return v; } C int minimo=0; for(i=0 ; i x[j]) minimo=j; } temp=x[minimo]; x[minimo]=x[i]; x[i]=temp; } Basic For i = 1 To n - 1 minimo = i For j = i + 1 To n If x(minimo) > x(j) Then minimo = j End If Next j temp = x(i) x(i) = x(minimo) x(minimo) = temp Next i C++ #include #include using namespace std;
template void ordena_seleccion(vector& v) { for (int i = 0; i < v.size() - 1; ++i) { int min = i; for (int c = i + 1; c < v.size(); ++c) { if (v[min] > v[c]) min = c; } T aux = v[i]; v[i] = v[min]; v[min] = aux; } }
Perl sub seleccion { my $array = shift; # Recibimos una referencia a un array
my $i; # Índice del elemento a comparar my $j; # Índice del valor mínimo a encontrar
# Para todos los elementos menos el último for ( $i = 0; $i < $#$array; $i++ ) {
# Índice y valor del elemento a comparar my ( $m, $x ) = ( $i, $array->[ $m ] );
# Buscamos el valor más pequeño de todos los demás for ( $j = $i + 1; $j < @$array; $j++ ) {
Complejidad de la búsqueda secuencial La complejidad de la búsqueda secuencial diferencia entre el comportamiento en el caso peor y mejor. El mejor caso se encuentra cuando aparece una coincidencia en el primer elemento de la lista y en ese caso el tiempo de ejecución es O (1). El caso peor se produce cuando el elemento no está en la lista o se encuentra al final de la lista. Esto requiere buscar en todos los n términos, lo que implica una complejidad de O(n). El caso medio requiere un poco de razonamiento probabilista. Para el caso de una lista aleatoria es probable que una coincidencia ocurra en cualquier posición. Después de la ejecución de un número grande de búsquedas, la posición media para una coincidencia es el elemento central n/2. El elemento central ocurre después de n/2 comparaciones, que define el coste esperado de la búsqueda. Por esta razón, se dice que la prestación media de la búsqueda secuencial es O(n).
Comparación de la búsqueda binaria y secuencial Búsqueda Secuencial: Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo. Búsqueda Binaria: El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central. Búsqueda Binaria: En cada comparación se puede eliminar la mitad de los elementos del array. Primera comparación: array de n elementos Segunda comparación: array de n/2 elementos Tercera comparación: array de n/4 elementos Cuarta comparación: array de n/8 elementos C-ésima comparación: array de n/2C elementos
Análisis de la Estructura de Objetos. El análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos.
Objetos y Tipos de Objetos. En el análisis se trata de identificar los tipos de objeto más que los objetos individuales en un sistema. Los tipos de objetos se definen en base a la comprensión del analista de nuestro mundo. Un objeto puede categorizarse de variadas formas.
Representación para Tipo de Objeto (Persona). Asociaciones de Objetos. Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad).
Representación para la Asociación entre dos Tipos de Objetos. Un objeto del tipo persona posee cero o muchos objetos del tipo vehículo. Un objeto del tipo vehículo es de un y sólo un objeto del tipo persona. Jerarquías de Generalización. Una de las vías de sentido común por las que el hombre organiza su volumen de conocimiento es el de las jerarquías, de lo más general a lo más específico.
Esquemas de Objetos. La comprensión de un modelo suele ser más sencilla si los tipos de objetos y relaciones se presentan mediante un diagrama de relación entre objetos; los supertipos y subtipos se presentan en un diagrama de jerarquías de generalización y las estructuras compuestas en un diagrama compuesto. Sin embargo, para los usuarios más sofisticados puede ser útil presentarlo todo en un mismo diagrama, el que se denomina esquema de objetos.
Estas funciones se diferencian en el número y tipo de argumentos, pero también hay funciones sobrecargadas que devuelven tipos distintos. Sobrecarga se refiere al uso de un mismo nombre para múltiples significados de un operador o una función. Dado el énfasis del concepto de clase, el uso principal de la sobrecarga es con las funciones miembro de una clase. Cuando más de una función miembro con igual nombre se declara en una clase, se dice que el nombre de la función está sobrecargado en esa clase. El ámbito del nombre sobrecargado es el de la clase. La sobrecarga de funciones amigas es similar a la de funciones miembro, con la única diferencia de que es necesaria la palabra reservada friend al igual que en la declaración de cualquier función amiga. Sobrecarga de operadores De modo análogo a la sobrecarga de funciones, la sobrecarga de operadores permite al programador dar nuevos significados a los símbolos de los operadores existentes en C++. C++ permite a los programadores sobrecargar a los operadores para tipos abstractos de datos.
Una ventana es una parte de la pantalla sobre la que se ejecutará un programa o se realizarán una serie de tareas. Todas ellas poseen una serie de elementos comunes (figura de abajo) tales como: • Barra de títulos: Muestra el nombre de la ventana. Con mucha frecuencia el nombre de la ventana contiene el nombre de la aplicación abierta en ella, seguido del nombre del documento activo. • Barra de menús: Inmediatamente debajo de la barra de títulos de la mayoría de las ventanas, hay un banda horizontal llamada Barra de Menús que contiene nombres tales como Archivo, Edición o ? (Ayuda). Haciendo clic en cualquiera de estos nombres se despliega un menú en forma de persiana, es decir se despliega una lista de comandos. Para escoger uno, basta con desplazar el puntero del ratón sobre el comando correspondiente y hacer clic. Barra de títulos y barra de menús. • Botón de minimizar: Haciendo clic sobre este botón (figura inferior) la ventana se reduce y se coloca su nombre en una barra que está en la parte inferior de la pantalla denominada Barra de Tareas. • Botón de maximizar: En este caso al presionar el botón la ventana aumenta de tamaño hasta ocupar la totalidad de la pantalla. • Botón de restaurar: Una vez maximizada la ventana, el botón de maximizar cambia al de restaurar. Presionando éste, la ventana vuelve al tamaño que poseía antes de ser maximizada. • Botón de cerrar: Cierra una ventana y la aplicación que está abierta. Suele estar en la esquina superior derecha o bien en la esquina superior izquierda en forma de un pequeño icono correspondiente a la aplicación. • Botón de Ayuda: Este botón que aparece en la esquina superior derecha de muchas de las cajas de diálogo, sirve para que Windows muestre información acerca de un elemento de la pantalla. Para ello hacer clic sobre el botón y arrastrar el cursor transformado en un signo de interrogación sobre el objeto de la pantalla que se desconoce o del que se desea obtener una breve explicación.
Para poder realizar cualquier operación dentro de una ventana ésta debe estar activa. Cuando hay dos o más ventanas superpuestas en la pantalla, la ventana activa siempre aparece en primer plano.
Análisis de la Estructura de Objetos. El análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos.
Objetos y Tipos de Objetos. En el análisis se trata de identificar los tipos de objeto más que los objetos individuales en un sistema. Los tipos de objetos se definen en base a la comprensión del analista de nuestro mundo. Un objeto puede categorizarse de variadas formas.
Representación para Tipo de Objeto (Persona). Asociaciones de Objetos. Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad).
Representación para la Asociación entre dos Tipos de Objetos. Un objeto del tipo persona posee cero o muchos objetos del tipo vehículo. Un objeto del tipo vehículo es de un y sólo un objeto del tipo persona. Jerarquías de Generalización. Una de las vías de sentido común por las que el hombre organiza su volumen de conocimiento es el de las jerarquías, de lo más general a lo más específico.
Esquemas de Objetos. La comprensión de un modelo suele ser más sencilla si los tipos de objetos y relaciones se presentan mediante un diagrama de relación entre objetos; los supertipos y subtipos se presentan en un diagrama de jerarquías de generalización y las estructuras compuestas en un diagrama compuesto. Sin embargo, para los usuarios más sofisticados puede ser útil presentarlo todo en un mismo diagrama, el que se denomina esquema de objetos.
Ciclo vital El tiempo de vida o ciclo vital ("Lifetime") de un objeto es una propiedad de tiempo de ejecución ("Runtime"). Viene determinado por el lapso entre su creación y su destrucción. Por supuesto no puede exceder la duración de su almacenamiento. El ciclo vital comienza cuando se le asigna espacio de almacenamiento y, si no es un objeto trivial, cuando el objeto es convenientemente iniciado por su constructor. Finaliza cuando es llamado el destructor o se rehúsa la zona de almacenamiento que le había sido asignada. Nota: decimos que un objeto es trivial cuando es, por ejemplo, un tipo simple preconstruido en el lenguaje. En este caso una expresión del tipo x hasta para que el compilador pueda reservar espacio de almacenamiento. Observe que el ciclo vital de los objetos automáticos y estáticos es controlado automáticamente por el compilador. En los primeros la destrucción se realiza cuando el objeto sale de ámbito. En los segundos la destrucción ocurre con las rutinas de finalización del programa. Por su parte el ciclo vital de los objetos dinámicos es controlado por el programador. Generalmente esta memoria reside en un segmento de datos fijo, situado de acuerdo con el modelo de memoria que se esté utilizando, aunque en los ambientes de 32 bits de PC y compatibles, solo está disponible el denominado modelo plano ("Flat memory model"). Esta última, denominada "dinámica" en la mayoría de los textos, incluyendo la propia literatura inglesa (por ejemplo los manuales de Borland), nos parece un término desafortunado para designar la duración de los objetos almacenados en el montón. Por esta razón preferimos designarlos como objetos "persistentes", ya que esta palabra califica más adecuadamente las características de tales objetos. Precisamente por esto y en especial si se trata de punteros, su uso puede resultar peligroso si no son inicializados correctamente. Hay una excepción en los llamados punteros inteligentes que destruyen el objeto señalado antes de ser ellos mismos destruidos.
Concepto de Grafo Los grafos son un conjunto de puntos, de los cuales algún par de ellos está conectado por unas líneas. Si estas líneas son flechas, hablaremos de grafo dirigido (digrafo), mientras que si son simples líneas estamos ante un grafo no dirigido. Más formalmente se pueden definir como un conjunto de vértices y un conjunto de aristas. Cada arista es un par (u,v), donde u y v pertenecen al conjunto de vértices. Si este par es ordenado el grafo es dirigido. Par de ejemplos: Grafo no dirigido Grafo dirigido. CLASIFICACION DE GRAFOS Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes. Algunos de los principales tipos de grafos son los que se muestran a continuación: • 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 Kn. A continuación pueden verse los dibujos de K3, K4, K5 y K6 • Un grafo bipartito regular: se denota Km,n 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.
• Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.
Teniendo esto definido podemos hablar de los grafos eulerianos describiéndolos simplemente como aquel grafo que contiene un camino euleriano. Como ejemplos tenemos las siguientes imágenes: El primer grafo de ellos no contiene caminos eulerianos mientras el segundo contiene al menos uno.
GRAFOS CONEXOS. Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”.
ÁRBOLES. Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también acíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos).
BOSQUES DE ÁRBOLES. Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos. Como ejemplo tenemos la siguiente figura. RECORRIDO DE UN GRAFO. Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida. Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura; y el recorrido en profundidad.
• Recorrido en anchura: El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.
• Recorrido en profundidad: el recorrido en profundidad trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente. REPRESENTACIÓN DE GRAFOS EN PROGRAMAS. Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas. • Representación mediante matrices: La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.
• Representación mediante listas: En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.
• Representación mediante matrices dispersas: Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.
Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo. El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n2) operaciones para ordenar una lista de n elementos. Su funcionamiento es el siguiente: Buscar el mínimo elemento de la lísta 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
El método de shell es una versión mejorada del método de inserción directa. Este método también se conoce con el nombre de inserción con incrementos decrecientes.
En el método de ordenación por inserción directa cada elemento se compara para su ubicación correcta en el arreglo, con los elementos que se encuentran en la parte izquierda del mismo. Si el elemento a insertar es más pequeño que el grupo de elementos que se encuentran a su izquierda, es necesario efectuar entonces varias comparaciones antes de su ubicación.
Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño pero con incrementos decrecientes. Así, los elementos quedarán ordenados en el arreglo más rápidamente. Para comprender mejor este algoritmo analícese el siguiente caso.
Considérese un arreglo que contenga 16 elementos. En primer lugar se dividirían los elementos del arreglo en 8 grupos teniendo en cuenta los elementos que se encuentran a 8 posiciones de distancia entre si y se ordenan por separado. Quedarán en el primer grupo los elementos (A[1],A[9]); en el segundo (A[2],A[10]); en el tercero (A[3],A[1]); y así sucesivamente. Después de este primer paso se dividirán los elementos del arreglo en 4 grupos, teniendo en cuenta ahora los elementos que se encuentren a 4 posiciones de distancia entre sí y se los ordenará por separado. Quedarán en el primer grupo los elementos (A[1],A[5]), (A[9],A[13]), en el segundo. (A[2],A[6]), (A[10],A[14]), y así sucesivamente. En el tercer paso se dividirán los elementos del arreglo en grupos, tomando en cuenta los elementos que se encuentran ahora a dos posiciones de distancia entre sí y nuevamente se les ordenará por separado.
En el primer grupo quedarán (A[1],A[3], A[5],A[7], A[9],A[11], A[13],A[15]) y en el segundo grupo (A[2], ],A[4], A[6],A[8], A[10],A[12], A[14],A[16]).
Finalmente se agruparán y ordenarán los elementos de manera normal, es decir, de uno en uno. El análisis de eficiencia del método de Shell es un problema muy complicado y aún no resuelto. No se ha podido establecer hasta el momento la mejor secuencia de incrementos cuando n es grande. Cabe recordar que cada vez que se propone una secuencia de intervalos es necesario “correr” el algoritmo para analizar el tiempo de ejecución del mismo.
En 1969 Pratt descubrió que el tiempo de ejecución del algoritmo es del orden de n*(log n)2. Unas pruebas exhaustivas realizadas para obtener la mejor secuencia de intervalos cuando el número de elementos del arreglo es igual a 8 arrojaron como resultado que la mejor secuencia corresponde a un intervalo de 1, que no es más que el método de inserción directa estudiado previamente. Estas pruebas también determinaron que el menor número de movimientos se registraba con la secuencia 3,2,1. Cabe aclarar que las pruebas exhaustivas corresponden al análisis de (8!) posibilidades, es decir, 40 320 casos diferentes. 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(n2) 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(nlog2 n) en el peor caso. Esto es mejor que las O(n2) 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 inserción, 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. Considere un pequeño valor que está inicialmente almacenado en el final del vector. Usando un ordenamiento O(n2) como el ordenamiento de burbuja o el ordenamiento por inserción, tomará aproximadamente n comparaciones e intercambios para mover este valor hacia el otro extremo del vector. El Shell sort primero mueve los valores usando tamaños de espacio gigantes, de manera que un valor pequeño se moverá bastantes posiciones hacia su posición final, con sólo unas pocas comparaciones e intercambios. Uno puede visualizar el algoritmo Shell sort de la siguiente manera: coloque la lista en una tabla y ordene las columnas (usando un ordenamiento por inserción). Repita este proceso, cada vez con un número menor de columnas más largas. Al final, la tabla tiene sólo una columna. Mientras que transformar la lista en una tabla hace más fácil visualizarlo, el algoritmo propiamente hace su ordenamiento en contexto (incrementando el índice por el tamaño de paso, esto es usando i += tamaño_de_paso en vez de i++). Por ejemplo, considere una lista de números como [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas. Esto quedaría así: 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 Entonces ordenamos cada columna, lo que nos da 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 Cuando lo leemos de nuevo como una única lista de números, obtenemos [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. Aquí, el 10 que estaba en el extremo final, se ha movido hasta el extremo inicial. Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de 3 posiciones, y después un ordenamiento con un espacio de 1 posición (ordenamiento por inserción simple).
El Shell sort lleva este nombre en honor a su inventor, Donald Shell, que lo publicó en 1959. Algunos libros de texto y referencias antiguas le llaman ordenación "Shell-Metzner" por Marlene Metzner Norton, pero según Metzner, "No tengo nada que ver con el algoritmo de ordenamiento, y mi nombre nunca debe adjuntarse a éste."
Secuencia de espacios La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la secuencia de espacios. Continúa para realizar un ordenamiento por inserción con espacio para cada número en la secuencia, hasta que termina con un espacio de 1. Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada. La secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar 1. Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción, se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento O(n2) del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice impar. Quizás la propiedad más crucial del Shell sort es que los elementos permanecen k-ordenados incluso mientras el espacio disminuye. Se dice que un vector dividido en k sub-vectores esta k-ordenado si cada uno de esos sub-vectores esta ordenado en caso de considerarlo aislado. Por ejemplo, si una lista fue 5-ordenada y después 3-ordenada, la lista está ahora no sólo 3-ordenada, sino tanto 5-ordenada como 3-ordenada. Si esto no fuera cierto, el algoritmo desharía el trabajo que había hecho en iteraciones previas, y no conseguiría un tiempo de ejecución tan bajo. Dependiendo de la elección de la secuencia de espacios, Shell sort tiene un tiempo de ejecución en el peor caso de O(n2) (usando los incrementos de Shell que comienzan con 1/2 del tamaño del vector y se dividen por 2 cada vez), O(n3 / 2) (usando los incrementos de Hibbard de 2k − 1), O(n4 / 3) (usando los incrementos de Sedgewick de 9(4i) − 9(2i) + 1, o 4i + 1 + 3(2i) + 1), o O(nlog2n), y posiblemente mejores tiempos de ejecución no comprobados. La existencia de una implementación O(nlogn) en el peor caso del Shell sort permanece como una pregunta por resolver. Implementaciones El Shell sort se usa comúnmente en lenguajes de programación; esto es una implementación del algoritmo en C/C++ para ordenar un vector de enteros. La secuencia de incrementos usada en este ejemplo de código da un tiempo de ejecución O(n2) en el peor caso. void shell_sort(int A[], int size) { int i, j, incrmnt, temp;
El algoritmo Shell sort en Java public static void shellSort(int[] a) { for ( int increment = a.length / 2; increment > 0; increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) { for (int i = increment; i < a.length; i++) { for (int j = i; j >= increment && a[j - increment] > a[j]; j -= increment) { int temp = a[j]; a[j] = a[j - increment]; a[j - increment] = temp; } } } } El algoritmo Shell sort en Perl sub shellsort { my $array = shift; # Recibimos una referencia a un array
my $i; # Índice del elemento a comparar my $j; # Índice del elemento actual a comparar my $shell; # Tamaño del incremento
# Calculamos el valor del incremento for ( $shell = 1; $shell < @$array; $shell = 2 * $shell + 1 ) { ; }
do { $shell = int( ( $shell - 1 ) / 2 );
# Para todos los elementos, elegidos con un incremento for ( $i = $shell; $i < @$array; $i++ ) { for ( $j = $i - $shell; $j >= 0 && $array->[ $j ] > $array->[ $j + $shell ]; $j -= $shell ) {
# Intercambiamos valores @$array[ $j, $j + $shell ] = @$array[ $j + $shell, $j ]; } } } while $shell > 1; } El algoritmo Shell sort en Python def shellsort(a): def new_increment(a): i = int(len(a) / 2) yield i while i != 1: if i == 2: i = 1 else: i = int(numpy.round(i/2.2)) yield i for increment in new_increment(a): for i in xrange(increment, len(a)): for j in xrange(i, increment-1, -increment): if a[j - increment] < a[j]: break temp = a[j]; a[j] = a[j - increment] a[j - increment] = temp return a El algoritmo Shell sort en C# using System; public class ShellSorter { public void Sort(int [] list) { int j,inc; inc=list.length/2; while(inc>0) { for(int i=inc+1;i0) { if(list[j] > list[j+inc]) { Swap(list[j],list[j+inc]); j=j-inc; } else { j=0; } } } inc=inc/2; } } } public class MainClass { public static void Main() { int[] iArrary=new int[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47}; ShellSorter sh=new ShellSorter(); sh.Sort(iArrary); for(int m=0;m<=13;m++) Console.WriteLine("{0}",iArrary[m]); } } El algoritmo Shell sort en Visual Basic Sub Shell_Sort(ByRef V) 'debemos pasarle el arreglo(de enteros) desde el programa principal() Dim I, Medio, J, Temp As Integer Dim Ordenado As Boolean Medio = UBound(V) While (Medio > 0) Medio = Medio \ 2 Do Ordenado = True For J = 0 To UBound(V) - Medio ' se asume que el arreglo va de 0 a UBound(V) elementos I = J + Medio If V(J) > V(I) Then ' Se intercambian los elementos Temp = V(J) V(J) = V(I) V(I) = Temp Ordenado = False End If Next Loop Until Ordenado Wend End Sub
----
Sub principal() Dim Arr(99) As Integer Dim I As Integer For I = 0 To 99 Arr(I) = Int(Rnd() * 1000) ' Se llena el arreglo con números menores que 1000 Next I Call Shell_Sort(Arr) End Sub
Algoritmo Selección El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición y así excluirlo de la lista. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo. Es un algoritmo lento, a pesar que sólo realiza un intercambio en cada ejecución del ciclo externo, puede ser una buena elección para listas con registros grandes y claves pequeñas. PSEUDOCÓDIGO ALGORITMO SELECCIÓN INICIO ENTERO I, J, MIN, ARREGLO[N] I 0 MIENTRAS(I < N) { MIN I J I + 1 MIENTRAS(J < N) { SI(ARREGLO[J] < ARREGLO[I]) { MIN J INTERCAMBIA(ARREGLO[MIN],ARREGLO[I]) } J J + 1 } I I + 1 } FIN CÓDIGO EN C++ void seleccion(void) { int i, j, min, ARREGLO[N], aux; i = 0 while(i < N) { min = i; j = i + 1; while (j < N) { if(ARREGLO[j] < ARREGLO[i]) { min = j; aux = ARREGLO[i]; ARREGLO[i] = ARREGLO[min]; ARREGLO[min] = aux; } j++; } i++ Ejemplo: [0] 15 10 10 10 7 7 7 7 7 7 7 7 7 7 7 [1] 10 15 15 15 15 15 14 11 10 10 10 10 10 10 10 [2] 14 14 14 14 14 14 15 15 15 15 14 11 11 11 11 [3] 11 11 11 11 11 11 11 14 14 14 15 15 15 14 14 [4] 7 7 7 7 10 10 10 10 11 11 11 14 14 15 15 I 0 0 0 0 0 1 1 1 1 2 2 2 3 3 4 J 1 1 2 3 4 2 2 3 4 3 3 4 4 4 5 MIN 0 0 1 1 4 1 2 3 4 2 3 4 3 4 4 Tiempo de Ejecución: El ciclo externo se ejecuta n veces para una lista de n elementos. Cada búsqueda requiere comparar todos los elementos no clasificados. Luego la complejidad es O(n2). Este algoritmo presenta un comportamiento constante independiente del orden de los datos. Estabilidad: Puede que haya algo de discrepancia pero esta implementación parece ser estable, puede verificar esto ordenando un conjunto de datos que tenga un par de ellos con la misma clave, el orden relativo entre ellos es conservado, pero algunos autores dicen que no es estable. Ventajas: • Fácil implementación. • No requiere memoria adicional. • Realiza pocos intercambios. • Rendimiento constante: poca diferencia entre el peor y el mejor caso. Desventajas: • Lento. • Realiza numerosas comparaciones. Algoritmo Shake Conocido como doble ordenamiento de burbuja; recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo coloca en su posición y al mismo tiempo también coloca el elemento menor en su posición. PSEUDOCÓDIGO ALGORITMO SHAKE INICIO ENTERO I 0, ARREGLO[N] ENTERO K N - 1 ENTERO MIN, MAX, J, AUX MIENTRAS(I < K) { MIN I MAX I PARA(J I + 1, HASTA K, J J + 1) { SI(ARREGLO[J] < ARREGLO[MIN]) { MIN J } SI(ARREGLO[J] > ARREGLO[MAX]) { MAX J } } AUX ARREGLO[MIN] ARREGLO[MIN] ARREGLO[I] ARREGLO[I] AUX SI(MAX I) { AUX ARREGLO[MIN] ARREGLO[MIN] ARREGLO[K] ARREGLO[K] AUX } SI NO { AUX ARREGLO[MAX] ARREGLO[MAX] ARREGLO[K] ARREGLO[K] AUX } I I + 1; K K - 1; } } CÓDIGO EN C++ void shake(void) { int i = 0, ARREGLO[N]; int k = N - 1; int min, max, j, aux; while (i < k) { min = i; max = i; for(j = i + 1; j <= k; j++) { if (ARREGLO[j] < ARREGLO[min]) min = j; if (ARREGLO[j] > ARREGLO[max]) max = j; } aux = ARREGLO[min]; ARREGLO[min] = ARREGLO[i]; ARREGLO[i] = aux; if (max == i) { aux = ARREGLO[min]; ARREGLO [min] = ARREGLO[k]; ARREGLO[k] = aux; } else { aux = ARREGLO[max]; ARREGLO[max] = ARREGLO[k]; ARREGLO[k] = aux; } i++; k--; } }
Ejemplo: [0] 15 7 7 [1] 10 10 10 [2] 14 14 11 [3] 11 11 14 [4] 7 15 15 I 0 1 2 K 4 3 2 J 1 2 3 4 2 3 4 3 MIN 0 1 4 1 2 MAX 0 1 2 2 Tiempo de ejecución: El bucle interno se efectuará ; el bucle interior se ejecutará entonces por la regla de la multiplicación tenemos O(n2) Ventajas: • Relativamente fácil de implementar. • No requiere memoria adicional. Estabilidad: Es inestable no mantiene el orden relativo de los registros. Desventajas: • Realiza numerosas comparaciones. • Realiza numerosos intercambios.
El método de shell es una versión mejorada del método de inserción directa. Este método también se conoce con el nombre de inserción con incrementos decrecientes.
En el método de ordenación por inserción directa cada elemento se compara para su ubicación correcta en el arreglo, con los elementos que se encuentran en la parte izquierda del mismo. Si el elemento a insertar es más pequeño que el grupo de elementos que se encuentran a su izquierda, es necesario efectuar entonces varias comparaciones antes de su ubicación.
Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño pero con incrementos decrecientes. Así, los elementos quedarán ordenados en el arreglo más rápidamente. Para comprender mejor este algoritmo analícese el siguiente caso.
Considérese un arreglo que contenga 16 elementos. En primer lugar se dividirían los elementos del arreglo en 8 grupos teniendo en cuenta los elementos que se encuentran a 8 posiciones de distancia entre si y se ordenan por separado. Quedarán en el primer grupo los elementos (A[1],A[9]); en el segundo (A[2],A[10]); en el tercero (A[3],A[1]); y así sucesivamente. Después de este primer paso se dividirán los elementos del arreglo en 4 grupos, teniendo en cuenta ahora los elementos que se encuentren a 4 posiciones de distancia entre sí y se los ordenará por separado. Quedarán en el primer grupo los elementos (A[1],A[5]), (A[9],A[13]), en el segundo. (A[2],A[6]), (A[10],A[14]), y así sucesivamente. En el tercer paso se dividirán los elementos del arreglo en grupos, tomando en cuenta los elementos que se encuentran ahora a dos posiciones de distancia entre sí y nuevamente se les ordenará por separado. En el primer grupo quedarán (A[1],A[3], A[5],A[7], A[9],A[11], A[13],A[15]) y en el segundo grupo (A[2], ],A[4], A[6],A[8], A[10],A[12], A[14],A[16]).
El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Descripción del algoritmo El algoritmo fundamental es el siguiente: Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote. Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada. La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido. En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n•log n). En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos esta ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente. En el caso promedio, el orden es O(n•log n). No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote. Demostración Podríamos probar el orden de ejecución en el mejor caso de la siguiente manera: Vamos a suponer que el número total de elementos a ordenar es potencia de dos, es decir, n = 2k. de aquí podemos ver que k =log2(n), donde k es el número de divisiones que realizará el algoritmo. En la primera fase del algoritmo habrán n comparaciones, en la segunda fase el algoritmo creará dos sublistas aproximadamente de tamaño n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n. En conclusión, el número total de comparaciones que hace el algoritmo es: n + n + n + ..... + n = kn, donde k = log2(n), por tanto el tiempo de ejecución del algoritmo en el mejor caso es O(n.log2n) Optimización del algoritmo Cabe destacar que de usarse en su versión recursiva las siguientes optimizaciones y sus desventajas no se ven vistas en el tiempo de ejecución del mismo manteniéndose, así el tiempo de ejecución planteado en un principio.
Finalmente se agruparán y ordenarán los elementos de manera normal, es decir, de uno en uno. El análisis de eficiencia del método de Shell es un problema muy complicado y aún no resuelto. No se ha podido establecer hasta el momento la mejor secuencia de incrementos cuando n es grande. Cabe recordar que cada vez que se propone una secuencia de intervalos es necesario “correr” el algoritmo para analizar el tiempo de ejecución del mismo.
En 1969 Pratt descubrió que el tiempo de ejecución del algoritmo es del orden de n*(log n)2. Unas pruebas exhaustivas realizadas para obtener la mejor secuencia de intervalos cuando el número de elementos del arreglo es igual a 8 arrojaron como resultado que la mejor secuencia corresponde a un intervalo de 1, que no es más que el método de inserción directa estudiado previamente. Estas pruebas también determinaron que el menor número de movimientos se registraba con la secuencia 3,2,1. Cabe aclarar que las pruebas exhaustivas corresponden al análisis de (8!) posibilidades, es decir, 40 320 casos diferentes. 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(n2) 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(nlog2 n) en el peor caso. Esto es mejor que las O(n2) 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 inserción, 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. Considere un pequeño valor que está inicialmente almacenado en el final del vector. Usando un ordenamiento O(n2) como el ordenamiento de burbuja o el ordenamiento por inserción, tomará aproximadamente n comparaciones e intercambios para mover este valor hacia el otro extremo del vector. El Shell sort primero mueve los valores usando tamaños de espacio gigantes, de manera que un valor pequeño se moverá bastantes posiciones hacia su posición final, con sólo unas pocas comparaciones e intercambios. Uno puede visualizar el algoritmo Shell sort de la siguiente manera: coloque la lista en una tabla y ordene las columnas (usando un ordenamiento por inserción). Repita este proceso, cada vez con un número menor de columnas más largas. Al final, la tabla tiene sólo una columna. Mientras que transformar la lista en una tabla hace más fácil visualizarlo, el algoritmo propiamente hace su ordenamiento en contexto (incrementando el índice por el tamaño de paso, esto es usando i += tamaño_de_paso en vez de i++). Por ejemplo, considere una lista de números como [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas.
Cuando lo leemos de nuevo como una única lista de números, obtenemos [10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45]. Aquí, el 10 que estaba en el extremo final, se ha movido hasta el extremo inicial. Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de 3 posiciones, y después un ordenamiento con un espacio de 1 posición (ordenamiento por inserción simple). El Shell sort lleva este nombre en honor a su inventor, Donald Shell, que lo publicó en 1959. Algunos libros de texto y referencias antiguas le llaman ordenación "Shell-Metzner" por Marlene Metzner Norton, pero según Metzner, "No tengo nada que ver con el algoritmo de ordenamiento, y mi nombre nunca debe adjuntarse a éste."
Secuencia de espacios La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la secuencia de espacios. Continua para realizar un ordenamiento por inserción con espacio para cada número en la secuencia, hasta que termina con un espacio de 1. Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada. La secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar 1. Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción, se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento O(n2) del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice impar. Quizás la propiedad más crucial del Shell sort es que los elementos permanecen k-ordenados incluso mientras el espacio disminuye. Se dice que un vector dividido en k sub-vectores esta k-ordenado si cada uno de esos sub-vectores esta ordenado en caso de considerarlo aislado. Por ejemplo, si una lista fue 5-ordenada y después 3-ordenada, la lista está ahora no sólo 3-ordenada, sino tanto 5-ordenada como 3-ordenada. Si esto no fuera cierto, el algoritmo desharía el trabajo que había hecho en iteraciones previas, y no conseguiría un tiempo de ejecución tan bajo. Dependiendo de la elección de la secuencia de espacios, Shell sort tiene un tiempo de ejecución en el peor caso de O(n2) (usando los incrementos de Shell que comienzan con 1/2 del tamaño del vector y se dividen por 2 cada vez), O(n3 / 2) (usando los incrementos de Hibbard de 2k − 1), O(n4 / 3) (usando los incrementos de Sedgewick de 9(4i) − 9(2i) + 1, o 4i + 1 + 3(2i) + 1), o O(nlog2n), y posiblemente mejores tiempos de ejecución no comprobados. La existencia de una implementación O(nlogn) en el peor caso del Shell sort permanece como una pregunta por resolver.
El Shell sort se usa comúnmente en lenguajes de programación; esto es una implementación del algoritmo en C/C++ para ordenar un vector de enteros. La secuencia de incrementos usada en este ejemplo de código da un tiempo de ejecución O(n2) en el peor caso. Algoritmo Selección El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición y así excluirlo de la lista. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo. Es un algoritmo lento, a pesar que sólo realiza un intercambio en cada ejecución del ciclo externo, puede ser una buena elección para listas con registros grandes y claves pequeñas.
Tiempo de Ejecución: El ciclo externo se ejecuta n veces para una lista de n elementos. Cada búsqueda requiere comparar todos los elementos no clasificados. Luego la complejidad es O(n2). Este algoritmo presenta un comportamiento constante independiente del orden de los datos. Estabilidad: Puede que haya algo de discrepancia pero esta implementación parece ser estable, puede verificar esto ordenando un conjunto de datos que tenga un par de ellos con la misma clave, el orden relativo entre ellos es conservado, pero algunos autores dicen que no es estable. Ventajas: • Fácil implementación. • No requiere memoria adicional. • Realiza pocos intercambios. • Rendimiento constante: poca diferencia entre el peor y el mejor caso. Desventajas: • Lento. • Realiza numerosas comparaciones. Algoritmo Shake Conocido como doble ordenamiento de burbuja; recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo coloca en su posición y al mismo tiempo también coloca el elemento menor en su posición. Tiempo de ejecución: El bucle interno se efectuará ; el bucle interior se ejecutará entonces por la regla de la multiplicación tenemos O(n2) Ventajas: • Relativamente fácil de implementar. • No requiere memoria adicional. Estabilidad: Es inestable no mantiene el orden relativo de los registros. Desventajas: • Realiza numerosas comparaciones. • Realiza numerosos intercambios.
El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Descripción del algoritmo El algoritmo fundamental es el siguiente: Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote. Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada. La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido. En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n•log n). En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos esta ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.
• HeapSort : - Este algoritmo no es estable, no mantiene el orden relativo inicial porque elementos iguales pueden terminar en distintos niveles del heap. - Vemos claramente en el código que no requiere memoria adicional para ordenar ya que solo ocupa 1 o 2 variables temporales para hacer los “intercambie” o “exchange”. - Funciona también claramente a base de comparación, Heapify ordena comparando al Padre con sus 2 hijos para luego ver si los cambia o no. Además tenemos que el tiempo de ejecución de HEAPIFY para un heap de n nodos es O(log n). Y además tenemos un FOR dentro de HeapSort, lo que nos dice que HEAPIFY se ejecuta N-1 veces. - Los Casos Medio y Mejor son también O( ) ya que igual entran al Build-Heap y al FOR, y en Heapify su tiempo de ejecución sigue teniendo una complejidad de O(log n).
Este método sirve para cualquier tipo de array. Consiste en ir recorriendo el contenido del array hasta que se encuentre el dato buscado o se llegue al final. Este método no es muy efectivo, puesto que al enfrentarse a un alto numero de información, si el dato buscado no se encuentra al principio, resulta muy lento. Búsqueda binaria. Este método de búsqueda solo puede utilizarse con un array ordenado. Es más eficaz que la búsqueda secuencial. Consiste en un procedimiento recursivo que compara el elemento buscado con el elemento que ocupe la posición media de un rango comprendido entre el principio y el final de la estructura. Si el elemento buscado es mayor que el comparado se redefinirá el rango entre el elemento que ocupa la posición media y el elemento que ocupa el final del rango, sí no, hace lo mismo pero entre la mitad del rango y el principio. Y así hasta dar con el dato buscado o no encontrarlo. El algoritmo de búsqueda lineal es uno de los más utilizados en situaciones bastante comunes. Es también uno de los algoritmos más sencillos e intuitivos. Sin embargo, resulta curioso comprobar cómo en gran cantidad de aplicaciones, muchas de ellas de ámbito altamente «profesional» se perpetran extrañas implementaciones que en algunos casos conllevan manifiestas ineficiencias y en otros peligros de salirse de los límites de los datos, por no hablar de situaciones en las que la programación estructurada se deja de lado. En éste artículo vamos a reflexionar acerca de la búsqueda lineal y de sus posibles implementaciones defendiendo la bondad o no de cada una de ellas. El escenario en el que se aplica el algoritmo es simple: tenemos una estructura de datos que es posible recorrer secuencialmente (aunque pueda ser recorrida de otra forma, por ejemplo, aleatoriamente, para este algoritmo basta con que se pueda hacer secuencialmente) y queremos saber si alguno de los datos de la estructura cumple algún predicado, y/o en qué posición está ese dato. Si hubiese varios datos que lo cumplen, basta con encontrar el primer dato que cumple dicho predicado. En este contexto, utilizamos predicado como una cualidad o condición del dato que sea comprobable mediante una expresión lógica booleana... es decir... que se pueda evaluar a verdadero o a falso para un determinado dato. Esa formulación básica puede ser asimilada a otras muchas situaciones... una vez encontrado un algoritmo de búsqueda lineal genérico veremos que la misma estructura puede ser adaptada a otros problemas de búsqueda... pero ya hablaremos de ello en otros artículos. Como hay que empezar por algún sitio, en éste artículo lo haremos razonando sobre un supuesto básico: saber si un elemento se encuentra en un array unidimensional, y si es así, conocer su posición.
Supongamos un array de enteros llamado A y un entero llamado x. Construiremos un método tal que dado el array A y el entero x nos diga si hay algún elemento en A cuyo valor sea x, y si es así, su posición.
Si hay algún entero en A que sea igual a x, nos devolverá su posición. Si no hay ninguno, utilizaremos el viejo truco de indicarlo devolviendo un "-1". Como las posiciones del array son números mayores o iguales a 0 y el tipo de retorno del método es un int, utilizamos un negativo (el -1) que es un valor que como posición del array no tiene sentido, para indicar que no se ha encontrado.
Una de las implemetaciones que se ven a menudo es la que sigue a continuación. Es muy común, sin embargo, muy ineficiente. En ella, se utiliza un bucle for, para recorrer todos los elementos del array, y una variable llamada posicion que va a contener la posición en la que se ha encontrado un elemento de A que es igual a x. Como inicialmente, cuando el algoritmo comienza, no se ha encontrado ningún elemento, se inicializa esa variable a "-1" directamente. A medida que avanza el bucle for, si encontramos un elemento que sea igual a x, cambiamos el valor de la variable posición.
El método de shell es una versión mejorada del método de inserción directa. Este método también se conoce con el nombre de inserción con incrementos decrecientes.
En el método de ordenación por inserción directa cada elemento se compara para su ubicación correcta en el arreglo, con los elementos que se encuentran en la parte izquierda del mismo. Si el elemento a insertar es más pequeño que el grupo de elementos que se encuentran a su izquierda, es necesario efectuar entonces varias comparaciones antes de su ubicación.
Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño pero con incrementos decrecientes. Así, los elementos quedarán ordenados en el arreglo más rápidamente. Para comprender mejor este algoritmo analícese el siguiente caso.
Considérese un arreglo que contenga 16 elementos. En primer lugar se dividirían los elementos del arreglo en 8 grupos teniendo en cuenta los elementos que se encuentran a 8 posiciones de distancia entre si y se ordenan por separado. Quedarán en el primer grupo los elementos (A[1],A[9]); en el segundo (A[2],A[10]); en el tercero (A[3],A[1]); y así sucesivamente. Después de este primer paso se dividirán los elementos del arreglo en 4 grupos, teniendo en cuenta ahora los elementos que se encuentren a 4 posiciones de distancia entre sí y se los ordenará por separado. Quedarán en el primer grupo los elementos (A[1],A[5]), (A[9],A[13]), en el segundo. (A[2],A[6]), (A[10],A[14]), y así sucesivamente. En el tercer paso se dividirán los elementos del arreglo en grupos, tomando en cuenta los elementos que se encuentran ahora a dos posiciones de distancia entre sí y nuevamente se les ordenará por separado.
El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Descripción del algoritmo El algoritmo fundamental es el siguiente: Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote. Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada. La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido. En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n•log n). En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos esta ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.
• HeapSort : - Este algoritmo no es estable, no mantiene el orden relativo inicial porque elementos iguales pueden terminar en distintos niveles del heap. - Vemos claramente en el código que no requiere memoria adicional para ordenar ya que solo ocupa 1 o 2 variables temporales para hacer los “intercambie” o “exchange”. - Funciona también claramente a base de comparación, Heapify ordena comparando al Padre con sus 2 hijos para luego ver si los cambia o no. Además tenemos que el tiempo de ejecución de HEAPIFY para un heap de n nodos es O(log n). Y además tenemos un FOR dentro de HeapSort, lo que nos dice que HEAPIFY se ejecuta N-1 veces. - Los Casos Medio y Mejor son también O( ) ya que igual entran al Build-Heap y al FOR, y en Heapify su tiempo de ejecución sigue teniendo una complejidad de O(log n). • HeapSort : - Este algoritmo no es estable, no mantiene el orden relativo inicial porque elementos iguales pueden terminar en distintos niveles del heap. - Vemos claramente en el código que no requiere memoria adicional para ordenar ya que solo ocupa 1 o 2 variables temporales para hacer los “intercambie” o “exchange”. - Funciona también claramente a base de comparación, Heapify ordena comparando al Padre con sus 2 hijos para luego ver si los cambia o no. Además tenemos que el tiempo de ejecución de HEAPIFY para un heap de n nodos es O(log n). Y además tenemos un FOR dentro de HeapSort, lo que nos dice que HEAPIFY se ejecuta N-1 veces. - Los Casos Medio y Mejor son también O( ) ya que igual entran al Build-Heap y al FOR, y en Heapify su tiempo de ejecución sigue teniendo una complejidad de O(log n).
Complejidad de la búsqueda secuencial La complejidad de la búsqueda secuencial diferencia entre el comportamiento en el caso peor y mejor. El mejor caso se encuentra cuando aparece una coincidencia en el primer elemento de la lista y en ese caso el tiempo de ejecución es O (1). El caso peor se produce cuando el elemento no está en la lista o se encuentra al final de la lista. Esto requiere buscar en todos los n términos, lo que implica una complejidad de O(n). El caso medio requiere un poco de razonamiento probabilista. Para el caso de una lista aleatoria es probable que una coincidencia ocurra en cualquier posición. Después de la ejecución de un número grande de búsquedas, la posición media para una coincidencia es el elemento central n/2. El elemento central ocurre después de n/2 comparaciones, que define el coste esperado de la búsqueda. Por esta razón, se dice que la prestación media de la búsqueda secuencial es O(n).
Comparación de la búsqueda binaria y secuencial Búsqueda Secuencial: Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo. Búsqueda Binaria: El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central. Búsqueda Binaria: En cada comparación se puede eliminar la mitad de los elementos del array. Primera comparación: array de n elementos Segunda comparación: array de n/2 elementos Tercera comparación: array de n/4 elementos Cuarta comparación: array de n/8 elementos C-ésima comparación: array de n/2C elementos
El método de shell es una versión mejorada del método de inserción directa. Este método también se conoce con el nombre de inserción con incrementos decrecientes.
En el método de ordenación por inserción directa cada elemento se compara para su ubicación correcta en el arreglo, con los elementos que se encuentran en la parte izquierda del mismo. Si el elemento a insertar es más pequeño que el grupo de elementos que se encuentran a su izquierda, es necesario efectuar entonces varias comparaciones antes de su ubicación. El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Descripción del algoritmo El algoritmo fundamental es el siguiente: Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote. Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada. La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. Complejidad de la búsqueda secuencial La complejidad de la búsqueda secuencial diferencia entre el comportamiento en el caso peor y mejor. El mejor caso se encuentra cuando aparece una coincidencia en el primer elemento de la lista y en ese caso el tiempo de ejecución es O (1). El caso peor se produce cuando el elemento no está en la lista o se encuentra al final de la lista. Esto requiere buscar en todos los n términos, lo que implica una complejidad de O(n). • HeapSort : - Este algoritmo no es estable, no mantiene el orden relativo inicial porque elementos iguales pueden terminar en distintos niveles del heap. - Vemos claramente en el código que no requiere memoria adicional para ordenar ya que solo ocupa 1 o 2 variables temporales para hacer los “intercambie” o “exchange”. - Funciona también claramente a base de comparación, Heapify ordena comparando al Padre con sus 2 hijos para luego ver si los cambia o no. Además tenemos que el tiempo de ejecución de HEAPIFY para un heap de n nodos es O(log n). Y además tenemos un FOR dentro de HeapSort, lo que nos dice que HEAPIFY se ejecuta N-1 veces. - Los Casos Medio y Mejor son también O( ) ya que igual entran al Build-Heap y al FOR, y en Heapify su tiempo de ejecución sigue teniendo una complejidad de O(log n).
Complejidad de la búsqueda secuencial La complejidad de la búsqueda secuencial diferencia entre el comportamiento en el caso peor y mejor. El mejor caso se encuentra cuando aparece una coincidencia en el primer elemento de la lista y en ese caso el tiempo de ejecución es O (1). El caso peor se produce cuando el elemento no está en la lista o se encuentra al final de la lista. Esto requiere buscar en todos los n términos, lo que implica una complejidad de O(n). El caso medio requiere un poco de razonamiento probabilista. Para el caso de una lista aleatoria es probable que una coincidencia ocurra en cualquier posición. Después de la ejecución de un número grande de búsquedas, la posición media para una coincidencia es el elemento central n/2. El elemento central ocurre después de n/2 comparaciones, que define el coste esperado de la búsqueda. Por esta razón, se dice que la prestación media de la búsqueda secuencial es O(n).
Comparación de la búsqueda binaria y secuencial Búsqueda Secuencial: Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo. Búsqueda Binaria: El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central. Búsqueda Binaria: En cada comparación se puede eliminar la mitad de los elementos del array. Primera comparación: array de n elementos Segunda comparación: array de n/2 elementos Tercera comparación: array de n/4 elementos Cuarta comparación: array de n/8 elementos C-ésima comparación: array de n/2C elementos
Análisis de exposición sobre POO.
ResponderEliminarEn dichas exposiciones se hablo sobre la historia de la Programación Orientada a Objetos, el concepto del mismo y sus principales características, además se dio una explicación sobre sus características y los programas que trabajan con dichos métodos.
Entre las cosas que considero importante es la definición de que el POO no es un lenguaje de programación como tal, sino una serie de métodos que permite a los entorno de desarrollos que cuentan con dichas características ofrecerle al programador una interfaz grafica para la creación de software de aplicaciones y de otra índole.
Entre las principales características que tiene el POO se encuentra:
• La herencia
• El encapsulamiento
• El polimorfismo
Dichas características le dan a los entornos de desarrollo el toque esencial que requieren para programar orientados a objetos.
La taxonomía de los lenguajes orientados a objetos es una clasificación para los lenguajes de programación con respecto a la orientación a objetos, en esta se establece claramente que para que un lenguaje de programación sea considerado orientado a objetos éste debe soportar la creación de clases y la herencia.
Además la POO cuenta con características adicionales que son:
• Tipificación fuerte.
• Manejo de excepciones.
• Paso de mensajes.
• Generalidad.
• Multitarea.
• Persistencia.
Estas permiten desarrollar aplicaciones con diversas características que permitirán al usuario final tener una mejor interacción con los programas
Entre las ventajas que tiene la POO tenemos:
• Permite la Flexibilidad podemos pensar en estos módulos como bloques con los cuales podemos construir diferentes programas.
• Por medio de la Reusabilidad podemos utilizar una clase definida previamente en las aplicaciones que nos sea conveniente. Es claro que la flexibilidad con la que se definió la clase va a ser fundamental para su reutilización.
• La Mantenibilidad. Las clases que conforman una aplicación, vistas como módulos independientes entre sí, son fáciles de mantener sin afectar a los demás componentes de la aplicación.
• La Extensibilidad. Gracias a la modularidad y a la herencia una aplicación diseñada bajo el paradigma de la orientación a objetos puede ser fácilmente extensible para cubrir necesidades de crecimiento de la aplicación.
Como resumen diré que la tecnología orientada a objetos nos permite diseñar e implementar sistemas bajo un paradigma de programación en el cual, por medio de la abstracción definimos a las clases o entidades de software a partir de entidades del mundo real. De dichas entidades instanciaremos objetos de software que se corresponderán con los objetos reales que representan. Esto nos permite enfocarnos más en la solución del problema que en la implantación de dicha solución.
Objetos en POO
ResponderEliminarLos objetos son ejemplares de una clase cualquiera. Cuando creamos un ejemplar tenemos que especificar la clase a partir de la cual se creará. Esta acción de crear un objeto a partir de una clase se llama instanciar (que viene de una mala traducción de la palabra instace que en inglés significa ejemplar). Por ejemplo, un objeto de la clase fracción es por ejemplo 3/5. El concepto o definición de fracción sería la clase, pero cuando ya estamos hablando de una fracción en concreto 4/7, 8/1000 o cualquier otra, la llamamos objeto. Para crear un objeto se tiene que escribir una instrucción especial que puede ser distinta dependiendo el lenguaje de programación que se emplee, pero será algo parecido a esto.
miCoche = new Coche()
Con la palabra new especificamos que se tiene que crear una instancia de la clase que sigue a continuación. Dentro de los paréntesis podríamos colocar parámetros con los que inicializar el objeto de la clase coche.
Estados en objetos
Cuando tenemos un objeto sus propiedades toman valores. Por ejemplo, cuando tenemos un coche la propiedad color tomará un valor en concreto, como por ejemplo rojo o gris metalizado. El valor concreto de una propiedad de un objeto se llama estado. Para acceder a un estado de un objeto para ver su valor o cambiarlo se utiliza el operador punto.
miCoche.color = rojo
El objeto es miCoche, luego colocamos el operador punto y por último el nombre e la propiedad a la que deseamos acceder. En este ejemplo estamos cambiando el valor del estado de la propiedad del objeto a rojo con una simple asignación.
Mensajes en objetos
Un mensaje en un objeto es la acción de efectuar una llamada a un método. Por ejemplo, cuando le decimos a un objeto coche que se ponga en marcha estamos pasándole el mensaje “ponte en marcha”.
Para mandar mensajes a los objetos utilizamos el operador punto, seguido del método que deseamos invocar.
Objetos
Entender que es un objeto es la clave para entender cualquier lenguaje orientado a objetos.
Existen muchas definiciones que se le ha dado al Objeto. Primero empecemos entendiendo que es un objeto del mundo real. Un objeto del mundo real es cualquier cosa que vemos a nuestro alrededor. Digamos que para leer este artículo lo hacemos a través del monitor y una computadora, ambos son objetos, al igual que nuestro teléfono celular, un árbol o un automóvil.
Analicemos un poco más a un objeto del mundo real, como la computadora. No necesitamos ser expertos en hardware para saber que una computadora está compuesta internamente por varios componentes: la tarjeta madre, el chip del procesador, un disco duro, una tarjeta de video, y otras partes más. El trabajo en conjunto de todos estos componentes hace operar a una computadora.
Internamente, cada uno de estos componentes puede ser sumamente complicado y puede ser fabricado por diversas compañías con diversos métodos de diseño. Pero nosotros no necesitamos saber cómo trabajan cada uno de estos componentes, como saber que hace cada uno de los chips de la tarjeta madre, o cómo funciona internamente el procesador. Cada componente es una unidad autónoma, y todo lo que necesitamos saber de adentro es cómo interactúan entre sí los componentes, saber por ejemplo si el procesador y las memorias son compatibles con la tarjeta madre, o conocer donde se coloca la tarjeta de video. Cuando conocemos como interaccionan los componentes entre sí, podremos armar fácilmente una computadora.
Herencia
ResponderEliminarLa herencia es uno de los conceptos más cruciales en la POO. La herencia básicamente consiste en que una clase puede heredar sus variables y métodos a varias subclases (la clase que hereda es llamada superclase o clase padre). Esto significa que una subclase, aparte de los atributos y métodos propios, tiene incorporados los atributos y métodos heredados de la superclase. De esta manera se crea una jerarquía de herencia.
Por ejemplo, imaginemos que estamos haciendo el análisis de un Sistema para una tienda que vende y repara equipos celulares.
Clases en POO
ResponderEliminarLas clases son declaraciones de objetos, también se podrían definir como abstracciones de objetos. Esto quiere decir que la definición de un objeto es la clase. Cuando programamos un objeto y definimos sus características y funcionalidades en realidad lo que estamos haciendo es programar una clase. En los ejemplos anteriores en realidad hablábamos de las clases coche o fracción porque sólo estuvimos definiendo, aunque por encima, sus formas.
Propiedades en clases
Las propiedades o atributos son las características de los objetos. Cuando definimos una propiedad normalmente especificamos su nombre y su tipo. Nos podemos hacer a la idea de que las propiedades son algo así como variables donde almacenamos datos relacionados con los objetos.
Métodos en las clases
Son las funcionalidades asociadas a los objetos. Cuando estamos programando las clases las llamamos métodos. Los métodos son como funciones que están asociadas a un objeto.
Objetos en POO
Los objetos son ejemplares de una clase cualquiera. Cuando creamos un ejemplar tenemos que especificar la clase a partir de la cual se creará. Esta acción de crear un objeto a partir de una clase se llama instanciar (que viene de una mala traducción de la palabra instace que en inglés significa ejemplar). Por ejemplo, un objeto de la clase fracción es por ejemplo 3/5. El concepto o definición de fracción sería la clase, pero cuando ya estamos hablando de una fracción en concreto 4/7, 8/1000 o cualquier otra, la llamamos objeto. Para crear un objeto se tiene que escribir una instrucción especial que puede ser distinta dependiendo el lenguaje de programación que se emplee, pero será algo parecido a esto.
ANALISIS DEL ENTORNO AL POO
ResponderEliminarEl elemento fundamental de la OOP es el objeto. El objeto es un conjunto complejo de datos y programas que poseen estructura .El POO se basa en varias técnicas, incluyendo herencia, modularidad, polimorfismo y encapsulamiento. El POO expresa a un programa como un conjunto de estos objetos, que colaboran entre ellos para realizar tareas. Esto permite hacer los programas y módulos más fáciles de escribir, mantener, reutilizar y volver a utilizar.
Un objeto es un ente que posee sus características propias (propiedades) y un conjunto de acciones que es capaz de realizar (métodos).
El objeto contiene toda la información para permitirle definirlo e identificarlo frente a otros objetos que pertenecen a otras clases, incluso frente a objetos de una misma clase, tienen valores diferenciados en sus atributos. Los objetos tienen mecanismos de interacción llamados métodos para favorecer la comunicación entre ellos. Tienen características que llevan a tratarlos individualmente, no se separan ni deben separarse del estado y el comportamiento.
Una clase es un ente abstracto que permite declarar las propiedades y los métodos de objetos similares.
Un lenguaje de programación orientado a objetos debe permitir al programador realizar definiciones de clases, y construir objetos a partir de esas clases.
El objeto no es un dato simple si no que tiene componentes estructurados, no es aislado, forma parte de una organización jerárquica o de otro tipo.
Una de las ventajas más importantes, es permitir la realización de las clases que definen un programa de forma totalmente independiente al programa donde se utilizan. Gracias a la encapsulación y el polimorfismo.
La herencia nos permite crear estructuras jerárquicas de clases donde es posible la creación de sub-clases que incluyan nuevas propiedades y atributos. Estas sub-clases admiten la definición de nuevos atributos, así como crear, modificar o inhabilitar propiedades.
El POO no depende estrictamente del lenguaje: se puede hacer con lenguajes no clasificados como tales (por ejemplo C). Los lenguajes funcionales son de una clase un poco diferente -entre otras cosas, los lenguajes funcionales son un superconjunto de POO.
Ya que la OOP no es un lenguaje de programación, puede aplicarse a cualquier lenguaje, y de hecho hoy en día está disponible en mayor o menor medida en todos los lenguajes tradicionales (C se ha convertido en C++, Pascal en Delphi, VB incorpora parte de la OOP) y no aparece un lenguaje nuevo sin que incluya OOP (como es el caso de Java). Es por esto que intentaremos que todo lo que aquí se diga pueda ser aplicado a cualquier lenguaje OOP.
ResponderEliminarEn OOP, cada objeto es una entidad única, evitando que las ordenes contenidos en alguno de los objetos puedan mezclarse con rutinas de otros objetos.
Una clase es un conjunto de reglas de creación y comportamiento de los objetos.
Un objeto es un conjunto de datos que se comporta de acuerdo a las reglas de su clase.
Encapsulamiento, es el vínculo que existe entre los datos de un objeto y los métodos que lo utilizan.
La herencia, es la cualidad que permite reutilizar un codigo previamente escrito modificando las diferencias que existan entre las clases y las subclases. Capacidad que tienen las clases derivadas o hijas para utilizar toda la información (datos y métodos) de todas las cla ses superiores.
Polimorfismo, es la capacidad que tienen los objetos de clases diferentes para actuar frente al mismo mensaje de formas distintas.
Sobrecarga, es la posibilidad de definir distintas funciones con el mismo nombre, pero con diferente conjunto de argumentos.
Clase, es el conjunto de reglas de creación y comportamiento de los objetos.
Superclase, es la clase de donde se derivan una o más clases.
Subclase, es la clase que es derivada de otra u otras. Tambien se llama clase hija.
ANÁLISIS DE LA ESTRUCTURA DE OBJETOS
ResponderEliminarEl análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos.
OBJETOS Y TIPOS DE OBJETOS En el análisis se trata de identificar los tipos de objeto más que los objetos individuales en un sistema. Los tipos de objetos se definen en base a la comprensión del analista de nuestro mundo. Un objeto puede categorizarse de variadas formas.
ASOCIACIONES DE OBJETOS Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad). Representación para la Asociación entre dos Tipos de Objetos.
ANÁLISIS DEL COMPORTAMIENTO DE OBJETOS
En el análisis del comportamiento de objetos (ACO) realizamos esquemas de eventos que muestran eventos, la secuencia en que ocurren y cómo los eventos cambian el estado de los objetos.
Estados de un Objeto.
Un objeto puede existir en varios estados. Por ejemplo, un objeto reservación aérea puede ser una instancia de alguno de los siguientes tipos de objeto:
Reservación solicitada, Reservación en lista de espera, Reservación confirmada, Reservación cancelada, Reservación satisfecha ,Reservación archivada.
Tales tipos de objetos suelen percibirse como estados posibles del ciclo vital de un objeto. Sin embargo, un objeto puede tener una gran variedad de perspectivas de ciclos vitales. Por ejemplo, el mismo objeto reservación aérea también puede tener los siguientes estados relacionados con el pago:
Reservación no liquidada, Reservación con un pago de depósito, Reservación totalmente pagada, Reservación reembolsada. Así, el estado de un objeto es la colección de asociaciones que tiene un objeto.
Eventos. En el análisis orientado a objetos el mundo se describe en términos de los objetos y sus estados, así como los eventos que modifican esos estados. Un evento produce un cambio en el estado de un objeto. Los eventos sirven como indicadores de los instantes en que ocurren los cambios de estado. Para saber de los cambios y reaccionar adecuadamente ante ellos, debemos entender y modelar los eventos.
Sobrecarga se refiere a la posibilidad de tener dos o más funciones con el mismo nombre pero funcionalidad diferente. Es decir, dos o más funciones con el mismo nombre realizan acciones diferentes. El compilador usará una u otra dependiendo de los parámetros usados. A esto se llama también sobrecarga de funciones.
ResponderEliminarLa interfaz gráfica de usuario, conocida también como GUI es un tipo de interfaz de usuario que utiliza un conjunto de imágenes y objetos gráficos para representar la información y acciones disponibles en la interfaz. Habitualmente las acciones se realizan mediante manipulación directa para facilitar la interacción del usuario con la computadora. Surge como evolución de la línea de comandos de los primeros sistemas operativos y es pieza fundamental en un entorno gráfico. Como ejemplo de interfaz gráfica de usuario podemos citar el entorno de escritorio del sistema operativo Windows, el X-Window de Linux o el de Mac OS X, Aqua. En el contexto del proceso de interacción persona-ordenador, la interfaz gráfica de usuario es el artefacto tecnológico de un sistema interactivo que posibilita, a través del uso y la representación del lenguaje visual, una interacción amigable con un sistema informático
Tipos de interfaces gráficas de usuario
PUI's y Zooming user interface Los GUIs que no son PUIs son encontrados en juegos de computadora, y los GUIs avanzados basados en realidad virtual ahora son usados con más frecuencia en las investigaciones. Muchos grupos de investigación en Norteamérica y Europa están trabajando actualmente en el interfaz de enfoque del usuario o ZUI (Zooming User Interface), que es un adelanto lógico en los GUI, mezclando 3D con 2.o ó "2D y medio objetos vectoriales de una D".
"Touchscreen user interface" Algunos GUIs son diseñados para cumplir con los rigurosos requisitos de los mercados verticales. Éstos se conocen como "GUIs de uso específico." Un ejemplo de un GUI de uso específico es el ahora familiar Touchscreen o Pantalla Táctil (pantalla que al ser tocada efectúa los comandos del mouse en el software. Es encontrado en muchos restaurantes alrededor del mundo y en tiendas de autoservicio. Primero iniciado por Gene Mosher en la computadora del ST de Atari en 1986, el uso que el específico GUI en el Touchscreen ha encabezado una revolución mundial en el uso de las computadoras a través de las industrias alimenticias y de bebidas, y en venta al por menor. Otros ejemplos de GUIs de uso específico, relacionados con el Touchscreen son los cajeros automáticos, los kioscos de información y las pantallas de monitoreo y control en los usos industriales, que emplean un sistema operativo de tiempo real (RTOS). Los teléfonos móviles y los sistemas o consolas de juego también emplean el Touchscreen. Además la domótica no es posible sin una buena interfaz de usuario, o GUI.
ANÁLISIS DE LA ESTRUCTURA DE OBJETOS
Si se construye software, los módulos de software OO se basan en los tipos de objetos. El software que implanta el objeto contiene estructuras de datos y operaciones que expresan dicho comportamiento. Las operaciones se codifican como métodos. La representación en software OO del objeto es entonces una colección de tipos de datos y objetos. Entonces, dentro del software orientado a objeto, un objeto es cualquier cosa, real o abstracta, acerca de la cual almacenamos datos y los métodos que controlan dichos datos. Un objeto puede estar compuesto por otros objetos.
ANÁLISIS DEL COMPORTAMIENTO DE OBJETOS
ResponderEliminarEn el análisis del comportamiento de objetos (ACO) realizamos esquemas de eventos que muestran eventos, la secuencia en que ocurren y cómo los eventos cambian el estado de los objetos.
Estados de un Objeto.
Un objeto puede existir en varios estados. Por ejemplo, un objeto reservación aérea puede ser una instancia de alguno de los siguientes tipos de objeto:
Reservación solicitada, Reservación en lista de espera, Reservación confirmada, Reservación cancelada, Reservación satisfecha ,Reservación archivada.
Eventos. En el análisis orientado a objetos el mundo se describe en términos de los objetos y sus estados, así como los eventos que modifican esos estados. Un evento produce un cambio en el estado de un objeto. Los eventos sirven como indicadores de los instantes en que ocurren los cambios de estado. Para saber de los cambios y reaccionar adecuadamente ante ellos, debemos entender y modelar los eventos.
Tipos de Eventos El analista no necesita conocer cada evento que ocurra en una organización: sólo los tipos de eventos. Los tipos de eventos indican los cambios sencillos en el estado de un objeto; por ejemplo, cuando se deposita dinero en una cuenta bancaria o se actualiza el sueldo de un trabajador. Básicamente, los tipos de eventos describen las siguientes formas de cambios de estado:
ResponderEliminarUn objeto se crea. Un objeto se termina. Un objeto se clasifica como una instancia de un tipo de objeto. Un objeto se desclasifica como una instancia de un tipo de objeto. Un objeto cambia de clasificación. Un atributo de un objeto se cambia.
Sobrecarga de funciones y operadores
ResponderEliminarC++ proporciona las herramientas necesarias que permiten definir funciones y operadores que utilizan el mismo nombre o símbolo que una función u operador incorporado. Estas funciones y operadores se dicen que están sobrecargados y se pueden utilizar para redefinir una función u operador definido.
Sobrecarga de funciones
En C++ dos o más funciones pueden tener el mismo nombre representando cada una de ellas un código diferente. Esta característica se conoce como sobrecarga de funciones.
Una función sobrecargada es una función que tiene más de una definición.
Estas funciones se diferencian en el número y tipo de argumentos, pero también hay funciones sobrecargadas que devuelven tipos distintos.
Sobrecarga se refiere al uso de un mismo nombre para múltiples significados de un operador o una función.
Dado el énfasis del concepto de clase, el uso principal de la sobrecarga es con las funciones miembro de una clase. Cuando más de una función miembro con igual nombre se declara en una clase, se dice que el nombre de la función está sobrecargado en esa clase. El ámbito del nombre sobrecargado es el de la clase
La sobrecarga.
ResponderEliminarLa sobrecarga se refiere a la posibilidad de tener dos o más funciones con el mismo nombre pero funcionalidad diferente. Es decir, dos o más funciones con el mismo nombre realizan acciones diferentes. El compilador usará una u otra dependiendo de los parámetros usados. A esto se llama también sobrecarga de funciones.
También existe la sobrecarga de operadores que al igual que con la sobrecarga de funciones se le da más de una implementación a un operador.
Interfaz grafica de usuario
la idea de simplificar el uso de los ordenadores para usuarios de todo tipo y no sólo para los expertos, se ha convertido en una práctica habitual utilizar metáforas visuales por medio de la llamada interfaz gráfica de usuario (IGU ó GUI en inglés) para que el usuario interactúe y establezca un contacto más fácil e intuitivo con el ordenador.
Modelo de Casos de Uso del sistema
El modelo de casos de uso permite que los desarrolladores del software y los clientes lleguen a un acuerdo sobre los requisitos, es decir, sobre las condiciones y posibilidades que debe cumplir el sistema. Describe lo que hace el sistema para cada tipo de usuario.
Actores del sistema
Un actor no es más que un conjunto de roles que los usuarios de Casos de Uso desempeñan cuando interaccionan con estos Casos de Uso. Los actores representan a terceros fuera del sistema que colaboran con el mismo. Una vez que hemos identificado los actores del sistema, tenemos identificado el entorno externo del sistema.
Ventanas.
El escritorio del sistema operativo Windows de Microsoft y su sistema de ventanas sobre la pantalla se ha estandarizado y universalizado, pero fueron los ordenadores Macintosh de la compañía Apple los El modelo de casos de uso permite que los desarrolladores del software y los clientes lleguen a un acuerdo sobre los requisitos, es decir, sobre las condiciones y posibilidades que debe cumplir el sistema. Describe lo que hace el sistema para cada tipo de usuario.
La Estructura de Objetos.
Objetos y Tipos de Objetos.
Asociaciones de Objetos.
Jerarquías de Generalización.
Jerarquías Compuestas.
Diagramas de relación entre los objetos.
Esquemas de Objetos.
Ejercicios.
Análisis de la Estructura de Objetos.
El análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos. Describe lo que hace el sistema para Análisis del Comportamiento de Objetos.
Estados de un Objeto.
Eventos.
Tipos de Eventos
El Ciclo Vital de un Objeto
Interacciones entre tipos de objetos
Operaciones.
Fuentes externas de eventos
Reglas de activación
Condiciones de Control
Subtipos y Supertipos de Eventos.
En el análisis del comportamiento de objetos (ACO) realizamos esquemas de eventos que muestran eventos, la secuencia en que ocurren y cómo los eventos cambian. La mayoría de los objetos tienen un ciclo vital en el que una sucesión de eventos pueden ocurrirle y cada uno de éstos modifica su estado.
En este análisis, se dibuja un diagrama que muestre el ciclo vital de un objeto, incluyendo los estados posibles de los objetos, además de los cambios de estado permisibles. Este se denomina diagrama de reja.
Este es un diagrama de reja que muestra los estados posibles de un objeto reservación aérea. Las líneas horizontales representan estados y las verticales muestran las transiciones entre estados.
do de lLa mayoría de los objetos tienen un ciclo vital en el que una sucesión de eventos pueden ocurrirle y cada uno de éstos modifica su estado.
En este análisis, se dibuja un diagrama que muestre el ciclo vital de un objeto, incluyendo los estados posibles de los objetos, además de los cambios de estado permisibles. Este se denomina diagrama de reja.
Este es un diagrama de reja que muestra los estados posibles de un objeto reservación aérea. Las líneas horizontales representan estados y las verticales muestran las transiciones entre estados.
La sobrecarga.
ResponderEliminarLa sobrecarga se refiere a la posibilidad de tener dos o más funciones con el mismo nombre pero funcionalidad diferente. Es decir, dos o más funciones con el mismo nombre realizan acciones diferentes. El compilador usará una u otra dependiendo de los parámetros usados. A esto se llama también sobrecarga de funciones.
También existe la sobrecarga de operadores que al igual que con la sobrecarga de funciones se le da más de una implementación a un operador.
Interfaz grafica de usuario
la idea de simplificar el uso de los ordenadores para usuarios de todo tipo y no sólo para los expertos, se ha convertido en una práctica habitual utilizar metáforas visuales por medio de la llamada interfaz gráfica de usuario (IGU ó GUI en inglés) para que el usuario interactúe y establezca un contacto más fácil e intuitivo con el ordenador.
Modelo de Casos de Uso del sistema
El modelo de casos de uso permite que los desarrolladores del software y los clientes lleguen a un acuerdo sobre los requisitos, es decir, sobre las condiciones y posibilidades que debe cumplir el sistema. Describe lo que hace el sistema para cada tipo de usuario.
Actores del sistema
Un actor no es más que un conjunto de roles que los usuarios de Casos de Uso desempeñan cuando interaccionan con estos Casos de Uso. Los actores representan a terceros fuera del sistema que colaboran con el mismo. Una vez que hemos identificado los actores del sistema, tenemos identificado el entorno externo del sistema.
Ventanas.
El escritorio del sistema operativo Windows de Microsoft y su sistema de ventanas sobre la pantalla se ha estandarizado y universalizado, pero fueron los ordenadores Macintosh de la compañía Apple los El modelo de casos de uso permite que los desarrolladores del software y los clientes lleguen a un acuerdo sobre los requisitos, es decir, sobre las condiciones y posibilidades que debe cumplir el sistema. Describe lo que hace el sistema para cada tipo de usuario.
La Estructura de Objetos.
Objetos y Tipos de Objetos.
Asociaciones de Objetos.
Jerarquías de Generalización.
Jerarquías Compuestas.
Diagramas de relación entre los objetos.
Esquemas de Objetos.
Ejercicios.
Análisis de la Estructura de Objetos.
El análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos. Describe lo que hace el sistema para Análisis del Comportamiento de Objetos.
Estados de un Objeto.
Eventos.
Tipos de Eventos
El Ciclo Vital de un Objeto
Interacciones entre tipos de objetos
Operaciones.
Fuentes externas de eventos
Reglas de activación
Condiciones de Control
Subtipos y Supertipos de Eventos.
En el análisis del comportamiento de objetos (ACO) realizamos esquemas de eventos que muestran eventos, la secuencia en que ocurren y cómo los eventos cambian. La mayoría de los objetos tienen un ciclo vital en el que una sucesión de eventos pueden ocurrirle y cada uno de éstos modifica su estado.
En este análisis, se dibuja un diagrama que muestre el ciclo vital de un objeto, incluyendo los estados posibles de los objetos, además de los cambios de estado permisibles. Este se denomina diagrama de reja.
Este es un diagrama de reja que muestra los estados posibles de un objeto reservación aérea. Las líneas horizontales representan estados y las verticales muestran las transiciones entre estados.
do de lLa mayoría de los objetos tienen un ciclo vital en el que una sucesión de eventos pueden ocurrirle y cada uno de éstos modifica su estado.
En este análisis, se dibuja un diagrama que muestre el ciclo vital de un objeto, incluyendo los estados posibles de los objetos, además de los cambios de estado permisibles. Este se denomina diagrama de reja.
Este es un diagrama de reja que muestra los estados posibles de un objeto reservación aérea. Las líneas horizontales representan estados y las verticales muestran las transiciones entre estados.
Programación orientada a objetos
ResponderEliminarLa programación Orientada a objetos (POO) es una forma especial de programar, más cercana a como expresaríamos las cosas en la vida real que otros tipos de programación.
Con la POO tenemos que aprender a pensar las cosas de una manera distinta, para escribir nuestros programas en términos de objetos, propiedades, métodos y otras cosas que veremos rápidamente para aclarar conceptos y dar una pequeña base que permita ver este tipo de programación.
La complejidad del software se desarrolla mediante las personas que son hábiles para lo cual necesitan recopilar información necesaria es decir dominar la problemática del sistema para lo cual se ven enfocados al tratamiento del problema y después a gestionar un proceso mediante el cual desarrollaran el software y así através de eso podrán llevarlo a la practica hasta que atreves del usuario pueda tener la flexibilidad de probarlo, para lo cual el software y la Poo tienen varias aplicaciones en la programación formando grandes estructuras de ellas
Análisis de la Estructura de Objetos.
ResponderEliminarEl análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos.
Objetos y Tipos de Objetos.
En el análisis se trata de identificar los tipos de objeto más que los objetos individuales en un sistema. Los tipos de objetos se definen en base a la comprensión del analista de nuestro mundo. Un objeto puede categorizarse de variadas formas.
Representación para Tipo de Objeto (Persona).
Asociaciones de Objetos.
Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad).
Representación para la Asociación entre dos Tipos de Objetos. Un objeto del tipo persona posee cero o muchos objetos del tipo vehículo. Un objeto del tipo vehículo es de un y sólo un objeto del tipo persona.
Jerarquías de Generalización.
Una de las vías de sentido común por las que el hombre organiza su volumen de conocimiento es el de las jerarquías, de lo más general a lo más específico.
Representación de una Jerarquía de generalización, para el tipo de objeto Persona.
En las jerarquías se habla de subtipo o especialización de un supertipo o generalización. En el caso anterior, persona es el supertipo para Empleado y Estudiante, que son sus subtipos. Por otra parte, Empleado es el supertipo para los subtipos Ejecutivo y Vendedor. Los subtipos (niveles inferiores de la jerarquía) heredan las características de sus supertipos, además, cada instancia de un tipo de objeto lo es también de sus supertipos.
Jerarquías Compuestas.
Un objeto se denomina complejo si está formado por otros. Las jerarquías Compuestas permiten realizar agregaciones de objetos.
tiene más de una definición.
ResponderEliminarEstas funciones se diferencian en el número y tipo de argumentos, pero también hay funciones sobrecargadas que devuelven tipos distintos.
Sobrecarga se refiere al uso de un mismo nombre para múltiples significados de un operador o una función.
Dado el énfasis del concepto de clase, el uso principal de la sobrecarga es con las funciones miembro de una clase. Cuando más de una función miembro con igual nombre se declara en una clase, se dice que el nombre de la función está sobrecargado en esa clase. El ámbito del nombre sobrecargado es el de la clase.
La sobrecarga de funciones amigas es similar a la de funciones miembro, con la única diferencia de que es necesaria la palabra reservada friend al igual que en la declaración de cualquier función amiga.
Sobrecarga de operadores
De modo análogo a la sobrecarga de funciones, la sobrecarga de operadores permite al programador dar nuevos significados a los símbolos de los operadores existentes en C++.
C++ permite a los programadores sobrecargar a los operadores para tipos abstractos de datos.
Una ventana es una parte de la pantalla sobre la que se ejecutará un programa o se realizarán una serie de tareas. Todas ellas poseen una serie de elementos comunes (figura de abajo) tales como:
ResponderEliminar• Barra de títulos: Muestra el nombre de la ventana. Con mucha frecuencia el nombre de la ventana contiene el nombre de la aplicación abierta en ella, seguido del nombre del documento activo.
• Barra de menús: Inmediatamente debajo de la barra de títulos de la mayoría de las ventanas, hay un banda horizontal llamada Barra de Menús que contiene nombres tales como Archivo, Edición o ? (Ayuda). Haciendo clic en cualquiera de estos nombres se despliega un menú en forma de persiana, es decir se despliega una lista de comandos. Para escoger uno, basta con desplazar el puntero del ratón sobre el comando correspondiente y hacer clic.
Barra de títulos y barra de menús.
• Botón de minimizar: Haciendo clic sobre este botón (figura inferior) la ventana se reduce y se coloca su nombre en una barra que está en la parte inferior de la pantalla denominada Barra de Tareas.
• Botón de maximizar: En este caso al presionar el botón la ventana aumenta de tamaño hasta ocupar la totalidad de la pantalla.
• Botón de restaurar: Una vez maximizada la ventana, el botón de maximizar cambia al de restaurar. Presionando éste, la ventana vuelve al tamaño que poseía antes de ser maximizada.
• Botón de cerrar: Cierra una ventana y la aplicación que está abierta. Suele estar en la esquina superior derecha o bien en la esquina superior izquierda en forma de un pequeño icono correspondiente a la aplicación.
• Botón de Ayuda: Este botón que aparece en la esquina superior derecha de muchas de las cajas de diálogo, sirve para que Windows muestre información acerca de un elemento de la pantalla. Para ello hacer clic sobre el botón y arrastrar el cursor transformado en un signo de interrogación sobre el objeto de la pantalla que se desconoce o del que se desea obtener una breve explicación.
Cuando se trabaja con Windows XP, a menudo se querrá tener en la pantalla más de una ventana abierta a la vez, y cambiar de una a otra. Para mover una ventana de posición se debe desplazar el puntero del ratón sobre la barra de títulos de la ventana a desplazar, y manteniendo pulsado el botón del ratón, mover éste. Al arrastrar la barra de títulos se desplazará toda la ventana a una nueva posición.
ResponderEliminarPara intercambiar entre dos ventanas se debe tener en cuenta que la ventana activa posee la Barra de Títulos resaltada (de color) mientras que la otra está en color gris. Con Windows es particularmente fácil conmutar ventanas. Para ello hay dos métodos principalmente: haciendo clic sobre la ventana que se desea volver activa o utilizando la Barra de Tareas. Ésta última se verá más adelante.
Para poder realizar cualquier operación dentro de una ventana ésta debe estar activa. Cuando hay dos o más ventanas superpuestas en la pantalla, la ventana activa siempre aparece en primer plano.
Análisis de la Estructura de Objetos.
ResponderEliminarEl análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos.
Objetos y Tipos de Objetos.
En el análisis se trata de identificar los tipos de objeto más que los objetos individuales en un sistema. Los tipos de objetos se definen en base a la comprensión del analista de nuestro mundo. Un objeto puede categorizarse de variadas formas.
Representación para Tipo de Objeto (Persona).
Asociaciones de Objetos.
Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad).
Representación para la Asociación entre dos Tipos de Objetos. Un objeto del tipo persona posee cero o muchos objetos del tipo vehículo. Un objeto del tipo vehículo es de un y sólo un objeto del tipo persona.
Jerarquías de Generalización.
Una de las vías de sentido común por las que el hombre organiza su volumen de conocimiento es el de las jerarquías, de lo más general a lo más específico.
Esquemas de Objetos.
La comprensión de un modelo suele ser más sencilla si los tipos de objetos y relaciones se presentan mediante un diagrama de relación entre objetos; los supertipos y subtipos se presentan en un diagrama de jerarquías de generalización y las estructuras compuestas en un diagrama compuesto. Sin embargo, para los usuarios más sofisticados puede ser útil presentarlo todo en un mismo diagrama, el que se denomina esquema de objetos.
Ciclo vital
ResponderEliminarEl tiempo de vida o ciclo vital ("Lifetime") de un objeto es una propiedad de tiempo de ejecución ("Runtime"). Viene determinado por el lapso entre su creación y su destrucción. Por supuesto no puede exceder la duración de su almacenamiento.
El ciclo vital comienza cuando se le asigna espacio de almacenamiento y, si no es un objeto trivial, cuando el objeto es convenientemente iniciado por su constructor. Finaliza cuando es llamado el destructor o se rehúsa la zona de almacenamiento que le había sido asignada.
Nota: decimos que un objeto es trivial cuando es, por ejemplo, un tipo simple preconstruido en el lenguaje. En este caso una expresión del tipo x hasta para que el compilador pueda reservar espacio de almacenamiento.
Observe que el ciclo vital de los objetos automáticos y estáticos es controlado automáticamente por el compilador. En los primeros la destrucción se realiza cuando el objeto sale de ámbito. En los segundos la destrucción ocurre con las rutinas de finalización del programa. Por su parte el ciclo vital de los objetos dinámicos es controlado por el programador.
Generalmente esta memoria reside en un segmento de datos fijo, situado de acuerdo con el modelo de memoria que se esté utilizando, aunque en los ambientes de 32 bits de PC y compatibles, solo está disponible el denominado modelo plano ("Flat memory model").
Esta última, denominada "dinámica" en la mayoría de los textos, incluyendo la propia literatura inglesa (por ejemplo los manuales de Borland), nos parece un término desafortunado para designar la duración de los objetos almacenados en el montón. Por esta razón preferimos designarlos como objetos "persistentes", ya que esta palabra califica más adecuadamente las características de tales objetos.
Precisamente por esto y en especial si se trata de punteros, su uso puede resultar peligroso si no son inicializados correctamente.
Hay una excepción en los llamados punteros inteligentes que destruyen el objeto señalado antes de ser ellos mismos destruidos.
Ciclo vital
ResponderEliminarEl tiempo de vida o ciclo vital ("Lifetime") de un objeto es una propiedad de tiempo de ejecución ("Runtime"). Viene determinado por el lapso entre su creación y su destrucción. Por supuesto no puede exceder la duración de su almacenamiento.El ciclo vital comienza cuando se le asigna espacio de almacenamiento y, si no es un objeto trivial, cuando el objeto es convenientemente iniciado por su constructor. Finaliza cuando es llamado el destructor o se rehúsa la zona de almacenamiento que le había sido asignada.
El ciclo vital de los objetos automáticos y estáticos es controlado automáticamente por el compilador. En los primeros la destrucción se realiza cuando el objeto sale de ámbito. En los segundos la destrucción ocurre con las rutinas de finalización del programa. Por su parte el ciclo vital de los objetos dinámicos es controlado por el programador.
El ciclo de vida lo que impone es una estructrura de trabajo, no un paradigma de desarrollo. Nació con la idea de aportar mejores soluciones y enfoques para dirigir sistemas desarrollados en lenguaje OO. Pero estas prácticas pueden escalarse hacia otros tipos de A/D.
Vinculación: el objeto es almacenado igual en la base datos, pero se establece un vínculo con el archivo original de forma que si modificamos el objeto desde el formulario, los cambios afectarán al archivo original.
ResponderEliminarIncrustación: el objeto es almacenado en la base de datos, pero si el objeto original sufre algún cambio, en la base de datos no se reflejará el cambio.
Tanto si incrustamos como si vinculamos, el objeto debe crearse en el formulario mediante el control llamado marco de objeto. Podemos utilizar estas opciones para insertar una imagen de una persona como si fuese un campo más de la base de datos.
Eventos: Para entender la programación dirigida por eventos, podemos oponerla a lo que no es: mientras en la programación secuencial (o estructurada) es el programador el que define cuál va a ser el flujo del programa, en la programación dirigida por eventos será el propio usuario --o lo que sea que esté accionando el programa-- el que dirija el flujo del programa. En la programación dirigida por eventos, al comenzar la ejecución del programa se llevarán a cabo las inicializaciones y demás código inicial y a continuación el programa quedará bloqueado hasta que se produzca algún evento. Cuando alguno de los eventos esperados por el programa tenga lugar, el programa pasará a ejecutar el código del correspondiente administrador de evento.
Cualquier actividad que se realiza en un sistema operativo orientado a eventos se comunica entre los distintos procesos interesados a través de mensajes denominados eventos. Por ejemplo cuando se presiona el botón izquierdo del ratón sobre una ventana de aplicación, el sistema operativo subyacente notifica a la aplicación de dicho suceso para que ésta pueda responder de manera adecuada a esta situación. El código que se encarga de dar respuesta a un evento específico se conoce como procedimiento manejador de evento.
Tipos de eventos
Eventos del teclado: Ocurren cuando el usuario presiona una tecla determinada como Tabulador o una combinación de teclas como Ctrl+P.
Eventos del ratón: Ocurren cuando el usuario mueve el ratón, lo presiona una sóla vez o dos veces o arrastra el ratón a través de la pantalla.
Eventos de la aplicación: Ocurren cuando la aplicación es cargada en memoria o cuando se abre o cierra una ventana o forma. Los eventos del teclado y del ratón ocurren cuando el usuario hace algo y los eventos de programación ocurren cuando el código hace algo, por ejemplo dar la indicación de cerrar la forma actual.
Funciones miembro
Función miembro es aquella que está declarada en ámbito de clase. Son similares a las funciones habituales, con la salvedad de que el compilador realizara el proceso de Decoración de nombre (Name Mangling en inglés): Cambiara el nombre de la función añadiendo un identificador de la clase en la que está declarada, pudiendo incluir caracteres especiales o identificadores numéricos.
Las funciones miembro se invocan accediendo primero al objeto al cual refieren, con la sintaxis: myobject.mymemberfunction(), esto es un claro ejemplo de una función miembro.
Objetos y Miembros:
ResponderEliminarLos objetos están compuestos de miembros. Los miembros son características, propiedades, métodos, y eventos, y representan los datos y la funcionalidad que caracterizan al objeto. Las propiedades representan los datos miembros de un objeto. Los métodos son acciones que el objeto puede realizar, y los eventos son notificaciones que un objeto envía o recibe hacia otros objetos cuando una actividad sucede.
Constructor: Método que devuelve un objeto de la clase a la que el constructor pertenece. Los constructores, habitualmente permiten asignar valores a todos o algunos datos del objeto que van a generar.
Destructor : Método que libera cualquier recurso requerido por el objeto durante su creación o existencia.
Destructor por defecto: Al igual que existe un constructor por defecto, existe un destructor por defecto. Este método, elimina de memoria el objeto al terminarse el ámbito de la variable que lo contiene, recuperando para su uso la porción de memoria que el objeto ocupaba.
El operador de envío: Para poder mandar mensajes a los objetos, necesitamos un operador, a este le llamamos el operador de envío. Cada lenguaje puede tener el suyo, pero es frecuente que se utilicen los dos puntos (':')o el punto ('.') (en C++ es el punto simple, igual que para referirnos a los elementos de los struct's).
El operador de envío hace que se ejecute la porción del código agrupada bajo el nombre del método, y el método trabajará con los datos propios de la instancia de la clase a ala que se refiera.
Herencia
Un objeto es heredero de otro cuando posee todas sus propiedades y todos sus métodos y reconoce todos sus eventos, aunque pueda disfrutar de propiedades, métodos y eventos adicionales. Se define la herencia como la característica que tienen los objetos de derivarse unos de otros. Por otra parte la herencia supone una clase base y una jerarquía de clases que contienen las clases derivadas de la clase base, así las clases derivadas pueden heredar las propiedades y métodos de una clase base, añadiendo sus propios métodos y propiedades, incluso cambiar aquellos elementos de la clase base que necesiten sean diferentes.
Tipos de Herencia:
Existen dos tipos de herencia
Herencia Simple: En esta jerarquía cada clase tiene como máximo una sola superclase. La herencia simple permite que una clase herede las propiedades y métodos de su superclase en una cadena jerárquica.
Herencia múltiple: Una malla o retícula consta de clases, cada una de las cuales pueden tener dos o más superclases inmediatas. Una herencia múltiple es aquella en la que cada clase puede heredar las propiedades y métodos de cualquier número de clases.
esto es una prueva.
ResponderEliminarSOBRECARGA
ResponderEliminarEn programación orientada a objetos la sobrecarga se refiere a la posibilidad de tener dos o más funciones con el mismo nombre pero funcionalidad diferente. Es decir, dos o más funciones con el mismo nombre realizan acciones diferentes.
.
INTERFAZ GRAFICA
La interfaz gráfica de usuario, es un tipo de interfaz que utiliza un conjunto de imágenes y objetos gráficos para representar la información y acciones disponibles en la interfaz.
La interfaz gráfica de usuario es el artefacto tecnológico de un sistema interactivo que posibilita, a través del uso y la representación del lenguaje visual, una interacción amigable con un sistema informático.
Manejo de ventanas en Windows
Una ventana es una parte de la pantalla sobre la que se ejecutará un programa o se realizarán una serie de tareas. Todas ellas poseen una serie de elementos comunes tales como:
• Barra de títulos: Muestra el nombre de la ventana. Con mucha frecuencia el nombre de la ventana contiene el nombre de la aplicación abierta en ella, seguido del nombre del documento. • Barra de menús: Inmediatamente debajo de la barra de títulos de la mayoría de las ventanas, hay un banda horizontal llamada Barra de Menús que contiene nombres tales como Archivo, Edición o ? (Ayuda). Haciendo clic en cualquiera de estos nombres se despliega un menú en forma de persiana, es decir se despliega una lista de comandos. Para escoger uno, basta con desplazar el puntero del ratón sobre el comando correspondiente y hacer clic.
Análisis de la Estructura de Objetos.
El análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos.
Objetos y Tipos de Objetos.
En el análisis se trata de identificar los tipos de objeto más que los objetos individuales en un sistema. Los tipos de objetos se definen en base a la comprensión del analista de nuestro mundo. Un objeto puede categorizarse de variadas formas.
Representación para Tipo de Objeto (Persona)
Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad).
Representación para la Asociación entre dos Tipos de Objetos. Un objeto del tipo persona posee cero o muchos objetos del tipo vehículo. Un objeto del tipo vehículo es de un y sólo un objeto del tipo persona.
Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad).
ResponderEliminarRepresentación para la Asociación entre dos Tipos de Objetos. Un objeto del tipo persona posee cero o muchos objetos del tipo vehículo. Un objeto del tipo vehículo es de un y sólo un objeto del tipo persona.
Jerarquías de Generalización.
Una de las vías de sentido común por las que el hombre organiza su volumen de conocimiento es el de las jerarquías, de lo más general a lo más específico.
Representación de una Jerarquía de generalización, para el tipo de objeto Persona.
En las jerarquías se habla de subtipo o especialización de un supertipo o generalización. Ejemplo.
profesor: supertipo, vocero: supertipo, estudiantes: subtipo.
Jerarquías Compuestas.
Un objeto se denomina complejo si está formado por otros. Las jerarquías Compuestas permiten realizar agregaciones de objetos.
Ejemplo.
Universidad – coordinación – escaleras - salón – pupitres.
Universidad se compone de un objeto, del tipo a su vez el objeto de coordinación de tipo universidad que pueden ser varias u objetos de salón y pupitres.
Diagramas de relación entre los objetos.
Los tipos de objetos están relacionados con otros tipos de objeto.
Estudiante: Richard profesor: Alquimedes Materia: Programacion
Diagrama de Relación entre objetos.
Un objeto del tipo cliente puede ordenar muchos objetos del tipo pedidos, y un objeto del tipo pedido es ordenado por un y sólo un objeto del tipo cliente. Un objeto del tipo producto está en muchos o ningún objeto del tipo pedido, mientras que un objeto del tipo pedido tiene al menos un objeto del tipo producto.
Análisis del Comportamiento de Objetos.
ResponderEliminarEstados de un Objeto.
Eventos.
Tipos de Eventos
El Ciclo Vital de un Objeto
Estados de un Objeto.
Un objeto puede existir en varios estados.
Tales tipos de objetos suelen percibirse como estados posibles del ciclo vital de un objeto. Sin embargo, un objeto puede tener una gran variedad de perspectivas de ciclos vitales.
El estado de un objeto es la colección de asociaciones que tiene un objeto.
Eventos.
En el análisis orientado a objetos el mundo se describe en términos de los objetos y sus estados, así como los eventos que modifican esos estados.
Un evento produce un cambio en el estado de un objeto. Los eventos sirven como indicadores de los instantes en que ocurren los cambios de estado.
Tipos de Eventos
El analista no necesita conocer cada evento que ocurra en una organización: sólo los tipos de eventos.
• Un objeto se crea.
• Un objeto se termina.
• Un objeto se clasifica como una instancia de un tipo de objeto.
• Un objeto se desclasifica como una instancia de un tipo de objeto.
• Un objeto cambia de clasificación.
• Un atributo de un objeto se cambia.
Los objetos pueden asociar un objeto con otro. Un evento clasificará al objeto como empleado.
El Ciclo Vital de un Objeto
La mayoría de los objetos tienen un ciclo vital en el que una sucesión de eventos pueden ocurrirle y cada uno de éstos modifica su estado. Todo puede variar de acuerdo de las modificaciones posibles a los objetos.
COMENTARIOS
ResponderEliminarHistoria de la Programación Orientado a Objeto (POO): (Exposición)
Al mismo tiempo que se da la Crisis del Software, por otro lado la Orientación a Objetos (OO) se empezóa discutir a fines de los años 60 con el desarrollo del lenguaje SIMULA67 por Nygaard y Ole-Johan Dahlen el Centro de Cálculo Noruego, en él, introdujeron los conceptos de clase, subclases y rutinas, muy parecidos los conceptos a los lenguajes orientados a objetos de hoy en día. A mitad de la década de los 70 los científicos del Centro de Investigaciones Palo Alto de XEROX (PARC) (XEROX Palo Alto Research Center) crearon el lenguaje SMALLTALK, el primer lenguaje orientado a objetos consistente y completo. En él cada elemento del lenguaje fue realizado un objeto. Este último lenguaje evolucionó a través de varios lanzamientos realizados por PARC.
A pesar de este movimiento temprano hacia los lenguajes orientados a objetos, sólo se lograron pequeñas incursiones en la comunidad de la programación general. El progreso reciente se ha acelerado debido principalmente a la disponibilidad de las extensiones orientadas a objetos para dos lenguajes populares: C y PASCAL, y a las extensiones prometidas para otros lenguajes comerciales populares como BASIC y COBOL.
1era Evaluación 03/11/2009 (Taller)
La sobrecarga se refiere a la práctica de cargar una función con mas un significado.
Básicamente el termino expresa que se cargan con uno o mas identificadores de función sobre un identificador previo.
El diseño de interfaces gráficas: Es una aplicación que estudia y trata de poner en práctica procesos orientados a construir la interfaz mas visible posible, dada ciertas condiciones de entorno.
Análisis de la Estructura de Objetos: (AEO), define las categorías de los objetos que percibimos y las formas en que los asociamos. En el análisis se trata de identificar los tipos de objetos más que los objetos individuales en un sistema.
Análisis del Comportamiento de Objetos: (ACO), en el realizamos esquemas de cuentos que muestran eventos, la secuencia en que ocurren y como los eventos cambian el estado de los objetos.
Ciclo vital de un objeto: La mayoría de los objetos tiene un ciclo vital en el que una sucesión de eventos pueden ocurrirle y cada uno de éstos modifica su estado.
En este análisis, se dibuja un diagrama que muestra el ciclo vital de un objeto, incluyendo los estados posibles de los objetos, además de los cambios de estado permisibles. Este se denomina diagrama de reja.
Diagrama de reja que muestra los estados posibles de un objeto reservación aérea. Las líneas horizontales representan estados y las verticales demuestran las transacciones entre estados
Objetos: Un objeto es una entidad lógica que contiene datos y un código que manipula estos datos;
Abstracción: En el sentido mas general, una abstracción es una representación concisa de una idea o de un objeto complicado. En un sentido mas especifico, la abstracción localiza y oculta los detalles de un modelo o diseño para generar y manipular objetos.
Clase: Podemos considerar una clase como una colección de objetos que poseen características y operaciones comunes. Una clase contiene toda la información necesaria para crear nuevos objetos.
Herencia: La herencia es un proceso mediante el cual un objeto puede adquirir las propiedades de otro objeto.
Encapsulación: Es una técnica que permite localizar y ocultar los detalles de un objeto. La encapsulación previene que un objeto sea manipulado por operaciones distintas de las definidas. La encapsulación es como una caja negra que esconde los datos y solamente permite acceder a ellos de forma controlada.
Polimorfismo: Significa que un nombre se puede utilizar para especificar una clase genérica de acciones
17/11/2009
ResponderEliminarUn evento es un mensaje que un objeto envía cuando se produce una situación determinada sobre dicho objeto, y que podrá ser respondido o no por el código de la aplicación.
Tipos de eventos:
Eventos del mouse.
OnClick: Este evento ocurre cuando el usuario hace clic dentro del área de la forma.
Eventos del teclado.
Estos eventos suceden cuando el usuario presiona un determinada tecla.
Eventos de sistema.
No todos los eventos ocurren por acciones que realice el usuario, algunos son ejecutados por el sistema operativo Windows.
Funciones Miembros
Se les llama así a las funciones que realizan operaciones con los datos de un objeto. También llamados funciones miembro.
Los datos privados de una clase sólo pueden ser modificados por medio de las funciones miembro -todos los métodos de esa clase y sólo los de esa clase-.
Constructores
Los constructores son procedimientos de la clase que permiten crear objetos. Un constructor es llamado para asignar memoria a un objeto, para asignar valores a los datos del objeto y realizar tareas iniciales para un nuevo objeto.
Esto implique que si no podemos trabajar con un objeto que no haya sido creado a través de un constructor y si sólo se pueden modificar mediante los procedimientos de la clase NO TENEMOS FORMA DE CORROMPER EL OBJETO, lo cual aumenta la confiabilidad y facilita la rehusabilidad.
Método que devuelve un objeto de la clase a la que el constructor pertenece. Los constructores, habitualmente permiten asignar valores a todos o algunos datos del objeto que van a generar.`
Un constructor es una función especial que es miembro de esa clase y que tiene el mismo nombre de la clase.
Es muy frecuente que una cierta parte de un objeto necesite una iniciación antes de que pueda ser utilizada; como el requisito de iniciación es tan frecuente C++ permite que los objetos se den a sí mismos valores iniciales cuando se crean. Esta iniciación automáticamente se lleva a cabo mediante el uso de una función de construcción o constructor.
La función de construcción de un objeto se invoca cuando se crea el objeto. Esto significa que se invoca cuando se ejecuta la declaración del objeto. Además, para los objetos locales, el constructor se invoca cada vez que se llega a la declaración del objeto.
Como lo dice el nombre, un constructor es una función que se utiliza para construir un objeto de una clase dada; esto puede implicar la presencia de diferentes escenarios.
1.- Creación de objetos con iniciación definida.
2.- Creación de objetos con iniciación especifica.
3.- Creación de objetos copiando otro objeto.
Cada uno de estos procesos implica un tipo diferente de constructor. Un constructor tiene el nombre de la clase a la que pertenece.
Un constructor private, impediría que los usuarios genéricos crearan objetos a partir de esa clase y forzarán el cumplimiento de una de las condiciones siguientes antes de que se pueda crear un objeto.
1.- Un miembro estático de la clase invoca al constructor.
ResponderEliminar2.- Una clase friend de esa clase invoca al constructor.
3.- Un objeto existente de la clase tiene una función miembro que crea nuevos objetos invocando al constructor.
Constructores con argumentos.
La función básica de un constructor consiste en inicializar un objeto antes de usarlo.
Constructores para copiar objetos.
Cuando se crea un objeto, a menudo no se desea inicializar ningún valor de manera específica; simplemente se desea que un objeto “sea como otro”. Esto implica hacer una copia de un objeto preexistente, lo cual requiere un tipo especial de construcción, llamada en general: constructor de copia.
Destructores
Un destructor es un procedimiento de la clase que realiza la tarea opuesta a su constructor, libera la memoria que fue asignada al objeto que fue creado por el constructor. Es deseable que el destructor se invoque implícitamente cuando el objeto abandone el bloque donde fue declarado.
El destructor le permite al programador despreocuparse de tener que liberar la memoria que deja de utilizar y correr el riesgo de que ésta se sature.
Método que libera cualquier recurso requerido por el objeto durante su creación o existencia.
Los destructores entran en la misma categoría que los constructores. Se utilizan para realizar ciertas operaciones que son necesarias cuando ya no se utiliza un objeto como es la liberación de memoria.
Existen algunas diferencias importantes entre los constructores y los destructores:
1.- Los destructores pueden ser virtuales, los constructores NO.
2.- A los destructores no se les puede mandar argumentos.
3.- Sólo se puede declarar un destructor para una clase dada.
El destructor se nombra como la clase pero este va precedido de un tilde (~).
El destructor se utiliza para cerrar el dispositivo gráfico y rechazar cualquier espacio de memoria asignado al objeto.
Herencia. La herencia es un mecanismo que para expresar similaridad entre clases, simplificando definiciones
De clases similares previamente detenidas.
• La herencia simple es cuando el lenguaje sólo permite que una clase derive de una clase.
• La herencia múltiple es cuando una clase puede ser derivada de más de una clase.
Una clase puede heredar los atributos de dos o más clases. Para lograr esto, se utiliza una lista de herencia separada mediante comas en la lista de clases base de la clase derivada.
La herencia es uno de los rasgos fundamentales de un lenguaje de programación orientado a objetos. En C++, la herencia se basa en permitir que una clase contenga a otra clase en su declaración;
Tipos De Herencias
Herencia múltiple Cuando una clase hija deriva de más de una clase padre; con lo que adquiere los datos y métodos de todas las clases de las cuales deriva.
Una clase puede heredar los atributos de dos o más clases. Para lograr esto, se utiliza una lista de herencia separada mediante comas en la lista de clases base de la clase derivada.
Eventos
ResponderEliminarEs el suceso donde interactua el usuario con la máquina, enviando el mensaje adecuado al objeto respectivo.
También se puede definir como evento, a la reacción que desencadena un objeto, es decir la acción que genera.
Como se produce un evento?
Cada vez que se produce un evento sobre un determinado tipo de control, se ejecuta una determinada función o procedimiento que realiza la acción programada por el usuario para ese evento concreto.
Estos procedimientos se definen con un nombre que se forma a partir del nombre del objeto y el nombre del evento, separados por el carácter (_), como por ejemplo txtBox_click, que es el nombre del procedimiento que se ocupará de responder al evento click en el objeto txtBox.
Tipos de Eventos
- Eventos relacionados al formulario
Inicio del formulario.
Respuesta a una acción (de usuario).
Vinculación de los objetos.
Cierre del formulario.
- Eventos relacionados al puntero del ratón
El click sobre un botón,
Hacer doble click sobre el nombre de un fichero para abrirlo,
Arrastrar un icono, etc,
- Eventos relacionados con gráficos
Color de texto.
Dibujar una caja de texto.
Imprimir.
- Eventos personalizados (generados por el usuario)
El usuario declara un evento al módulo myClass, utilizando la instrucción Event para declarar un evento con los argumentos que se desea. Los eventos deben ser declarados con Public. Disparando el eventos de acuerdo a la clase, usando la instrucción RaiseEvent, suministrando los parámetros requeridos.
Vinculación de los Objetos (Polimorfismo)
Es la asociación de un atributo con su valor
- Variable con un valor.
- Llamada a función con el cuerpo de la función.
Puede ser: Estática (early binding): en tiempo de compilación o antes de ejecutar.
C++, Pascal, COBOL, FORTRAN
Dinámica (late binding): en tiempo de ejecución.
C++, Smalltalk, Objetive-C, Java
Ejemplo:
Cuando una variable de un tipo Coche posee una referencia a un objeto de clase Taxi (siendo Taxi descendiente de Coche) y se invoca a un método por medio de la variable.
Con la vinculación dinámica se asociará la ejecución al tipo más específico, en este caso a Taxi.
El mecanismo para la búsqueda empieza por el tipo dinámico de la variable receptora y remontarse por la jerarquía de herencia hasta encontrar una implementación válida.
Funciones Miembro
Generalmente en las clases se suelen ubicar los datos miembros bajo la etiqueta private, y las funciones miembro bajo la etiqueta public, esto favorece a una buena ingeniería de software. La idea es que los clientes de las clases no puedan acceder directamente a los datos miembros de la clase, sino a través de las funciones miembro y sólo cuando sea necesario. Si intentaramos acceder a un dato miembro privado, obtendríamos un error en tiempo de compilación que nos alertaría.
Clasificación de las funciones miembro
- Funciones Set:
Permite acceder a los datos miembros de la clase y asignarle un valor.
Permite generar datos miembros en la clase y asignar controles para que sólo puedan establecerse datos miembros válidos.
Ejemplo: Set establecerTitulo,
Set establecerPaginas,
Set establecerCodigo.
- Funciones GET:
Permite obtener valores de los datos miembro para luego dirigir la salida de los datos de diferente manera.
Ejemplo: Get imprime().
- Funciones predicado:
Permite verifican la falsedad o veracidad de una condición.
Ejemplo: En una clase Libro, se tiene una función miembro llamada hayStock,
Esta función tendrá un valor True si el número de stock es mayor que cero
y False si es menor que cero.
- Funciones de utilidad:
No pueden ser definidas bajo la etiqueta public.
El usuario no puede tener acceso directamente.
Son de utilidad para otras funciones miembro de la clase.
Concepto de Grafo
ResponderEliminarLos grafos son un conjunto de puntos, de los cuales algún par de ellos está conectado por unas líneas. Si estas líneas son flechas, hablaremos de grafo dirigido (digrafo), mientras que si son simples líneas estamos ante un grafo no dirigido.
Más formalmente se pueden definir como un conjunto de vértices y un conjunto de aristas. Cada arista es un par (u,v), donde u y v pertenecen al conjunto de vértices. Si este par es ordenado el grafo es dirigido.
Par de ejemplos:
Grafo no dirigido Grafo dirigido.
Un grafo consta de vértices (o nodos) y aristas. Los vértices son objetos que contienen información y las aristas son conexiones entre vértices. Para representarlos, se suelen utilizar puntos para los vértices y líneas para las conexiones, aunque hay que recordar siempre que la definición de un grafo no depende de su representación.
Un camino entre dos vértices es una lista de vértices en la que dos elementos sucesivos están conectados por una arista del grafo. Así, el camino AJLOE es un camino que comienza en el vértice A y pasa por los vértices J,L y O (en ese orden) y al final va del O al E. El grafo será conexo si existe un camino desde cualquier nodo del grafo hasta cualquier otro. Si no es conexo constará de varias componentes conexas.
Un camino simple es un camino desde un nodo a otro en el que ningún nodo se repite (no se pasa dos veces). Si el camino simple tiene como primer y último elemento al mismo nodo se denomina ciclo. Cuando el grafo no tiene ciclos tenemos un árbol (ver árboles). Varios árboles independientes forman un bosque. Un árbol de expansión de un grafo es una reducción del grafo en el que solo entran a formar parte el número mínimo de aristas que forman un árbol y conectan a todos los nodos.
Según el número de aristas que contiene, un grafo es completo si cuenta con todas las aristas posibles (es decir, todos los nodos están conectados con todos), disperso si tiene relativamente pocas aristas y denso si le faltan pocas para ser completo.
Las aristas son la mayor parte de las veces bidireccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A: estos son llamados grafos no dirigidos. Sin embargo, en ocasiones tenemos que las uniones son unidireccionales. Estas uniones se suelen dibujar con una flecha y definen un grafo dirigido. Cuando las aristas llevan un coste asociado (un entero al que se denomina peso) el grafo es ponderado. Una red es un grafo dirigido y ponderado.
Ordenamiento
ResponderEliminarEs la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento.
El ordenamiento se efectúa con base en el valor de algún campo en un registro.
El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.
Ej. de ordenamientos:
Dir. Telefónico, tablas de contenido, bibliotecas y diccionarios, etc.
El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente.
Tipos de ordenamientos:
Los 2 tipos de ordenamientos que se pueden realizar son: los internos y los externos.
Los internos:
Son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo (a [1], a[500], etc.).
Los externos:
Son aquellos en los que los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc.), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada (posición 1, posición 500, etc.).
Clasificación de los algoritmos de ordenamiento de información:
El hecho de que la información está ordenada, nos sirve para poder encontrarla y accesarla de manera más eficiente ya que de lo contrario se tendría que hacer de manera secuencial.
Algoritmos de inserción:
En este tipo de algoritmo los elementos que van a ser ordenados son considerados uno a la vez. Cada elemento es INSERTADO en la posición apropiada con respecto al resto de los elementos ya ordenados.
Entre estos algoritmos se encuentran el de INSERCION DIRECTA, SHELL SORT, INSERCION BINARIA y HASHING.
Algoritmos de intercambio:
En este tipo de algoritmos se toman los elementos de dos en dos, se comparan y se INTERCAMBIAN si no están en el orden adecuado. Este proceso se repite hasta que se ha analizado todo el conjunto de elementos y ya no hay intercambios.
Entre estos algoritmos se encuentran el BURBUJA y QUICK SORT.
Algoritmos de selección:
En este tipo de algoritmos se SELECCIONA o se busca el elemento más pequeño (o más grande) de todo el conjunto de elementos y se coloca en su posición adecuada. Este proceso se repite para el resto de los elementos hasta que todos son analizados.
Entre estos algoritmos se encuentra el de SELECCION DIRECTA.
Algoritmos de enumeración:
En este tipo de algoritmos cada elemento es comparado contra los demás. En la comparación se cuenta cuántos elementos son más pequeños que el elemento que se está analizando, generando así una ENUMERACION. El número generado para cada elemento indicará su posición.
Los métodos simples son: Inserción (o por inserción directa), selección, burbuja y shell, en dónde el último es una extensión al método de inserción, siendo más rápido. Los métodos más complejos son el quick-sort (ordenación rápida) y el heap sort.
ResponderEliminarMETODO DE INSERCIÓN.
Este método toma cada elemento del arreglo para ser ordenado y lo compara con los que se encuentran en posiciones anteriores a la de él dentro del arreglo. Si resulta que el elemento con el que se está comparando es mayor que el elemento a ordenar, se recorre hacia la siguiente posición superior. Si por el contrario, resulta que el elemento con el que se está comparando es menor que el elemento a ordenar, se detiene el proceso de comparación pues se encontró que el elemento ya está ordenado y se coloca en su posición (que es la siguiente a la del último número con el que se comparó).
MÉTODO DE SELECCIÓN.
El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo.
MÉTODO BURBUJA.
El bubble sort, también conocido como ordenamiento burbuja, funciona de la siguiente manera: Se recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo va recorriendo de posición en posición hasta ponerlo en su lugar.
Algoritmo Shell
ResponderEliminarEl 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.
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:
El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.
ShellSort no es estable porque se puede perder el orden relativo inicial con facilidad cuando usamos incrementos grandes, ya que mira los 2 números separados por ese incremento y nada de lo al medio de esos 2 números es considerado para conservar el orden inicial. Si usáramos solo incremento 1 ahí tendríamos estabilidad, pero dejaría de ser ShellSort y pasaría a ser BubbleSort.
- No requiere memoria adicional, todo se ordena solo con una o dos variables temporales para hacer los intercambios.
- Usa la comparación en el WHILE más interno por lo tanto está en la categoría de los comparativos.
-El tiempo que requiere este algoritmo depende siempre de que sucesión de Incrementos se use.
Algoritmo Quicksort
El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
Descripción del algoritmo [editar] El algoritmo fundamental es el siguiente:
Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.
Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n•log n).
ResponderEliminarEn el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos esta ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.
Algoritmo Heapsort
El ordenamiento por montículos (heapsort en inglés) es un algoritmo de ordenamiento no recursivo, no estable, con complejidad computacional O (n log n).
Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.
Algoritmo de búsqueda
Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento concreto dentro de una estructura de datos. Consiste en solucionar un problema de existencia o no de un elemento determinado en un conjunto finito de elementos, es decir, si el elemento en cuestión pertenece o no a dicho conjunto, además de su localización dentro de éste.
Búsqueda secuencial
Se utiliza cuando el contenido del vector no se encuentra o no puede ser ordenado. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del arreglo hasta que éste se encuentre, o hasta que se llegue al final del arreglo. La existencia se puede asegurar desde el momento que el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo.
Búsqueda binaria (dicotómica)
Se utiliza cuando el vector en el que queremos determinar la existencia o no de un elemento está ordenado, o puede estarlo, este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente con el número de iteraciones.
Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del arreglo (normalmente el elemento central), si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del arreglo que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del arreglo que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible, con el elemento buscado como elemento central. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en el arreglo.
Búsqueda Lineal
ResponderEliminarAlgoritmos de búsqueda lineal son los 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).
Hash
ResponderEliminarHash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo.
Una función de hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo). Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada. Una propiedad fundamental del hashing es que si dos resultados de una misma función son diferentes, entonces las dos entradas que generaron dichos resultados también lo son.
Es posible que existan claves resultantes iguales para objetos diferentes, ya que el rango de posibles claves es mucho menor que el de posibles objetos a resumir (las claves suelen tener en torno al centenar de bits, pero los ficheros no tienen un tamaño límite).
Son usadas en múltiples aplicaciones, como los arrays asociativos, criptografía, procesamiento de datos y firmas digitales, entre otros. Una buena función de hash es una que experimenta pocas colisiones en el conjunto esperado de entrada; es decir que se podrán identificar unívocamente las entradas (ver función inyectiva).
FUNCIONES HASH Ó HASHING
El método llamado por transformación de claves (hash), permite aumentar la velocidad de búsqueda sin necesidad de tener los elementos ordenados. Cuenta también con la ventaja de que el tiempo de búsqueda es prácticamente independiente del número de componentes del arreglo.
Trabaja basándose en una función de transformación o función hash (H) que convierte una clave en una dirección (índice) dentro del arreglo.
Dirección ¬ H (clave)
Cuando se tienen claves que no se corresponden con índices (p. ejem. por ser alfanuméricas), o bien cuando las claves son valores numéricos muy grandes, debe utilizarse una función hash que permita transformar la clave para obtener una dirección apropiada. Esta función hash debe de ser simple de calcular y debe de asignar direcciones de la manera mas uniforme posible. Es decir, dadas dos claves diferentes debe generar posiciones diferentes. Si esto no ocurre (H (K1)=d, H (K2)=d y K1¬K2), hay una colisión. Se define, entonces, una colisión como la asignación de una misma dirección a dos o más claves distintas.
Por todo lo mencionado, para trabajar con este método de búsqueda debe elegirse previamente:
• Una función hash que sea fácil de calcular y que distribuya uniformemente las claves.
• Un método para resolver colisiones. Si estas se presentan se debe contar con algún método que genere posiciones alternativas.
Función Módulo (por división)
Consiste en tomar el residuo de la división de la clave entre el número de componentes del arreglo.
La función hash queda definida por la siguiente formula:
H (K) = (K mod N) + 1
Se recomienda que N sea el número primo inmediato inferior al número total de elementos.
Función Centro de Cuadrados
ResponderEliminarConsiste en elevar al cuadrado la clave y tomar los dígitos centrales como dirección. El numero de dígitos a tomar queda determinado por el rango del índice.
La función hash que definida por la sig. Formula:
H (K) = digitos_centrales (K²) + 1
Función Plegamiento
Consiste en dividir la clave en partes de igual numero de dígitos (la ultima puede tener menos dígitos) y operar con ellas, tomando como dirección los dígitos menos significativos. La operación entre las partes puede hacerse por medio de sumas o multiplicaciones. La función hash queda definida por la sig. Formula:
H (K) = dígnense ((d1...di) + (di + 1...dj) +... + (d1...dn)) + 1
Función Truncamiento
Consiste en tomar algunos dígitos de la clave y formar con ellos una dirección. La función hash queda definida por la sig. Fórmula:
H (K) = elegirdigitos (d1, d2...dn) + 1
Análisis de algoritmos
El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.
A la hora de realizar un análisis teórico de algoritmos es corriente calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota superior asintótica, y las notaciones omega y theta se usan con esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(log(n)), coloquialmente "en tiempo logarítmico". Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen porque tener la misma eficiencia. No obstante la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas por una constante multiplicativa llamada constante oculta.
La medida exacta (no asintótica) de la eficiencia a veces puede ser computada pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo, llamada modelo de computación. Un modelo de computación puede definirse en términos de un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos una búsqueda binaria tiene n elementos, y podemos garantizar que una única búsqueda binaria puede realizarse en un tiempo unitario, entonces se requieren como mucho log2 N + 1 unidades de tiempo para devolver una respuesta.
Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usan algoritmos, porque tienen más precisión y así les permite saber cuanto tiempo pueden suponer que tomará la ejecución. Para algunas personas, como los desarrolladores de videojuegos, una constante oculta puede significar la diferencia entre éxito y fracaso.
Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido, debemos garantizar que el tiempo requerido para realizar un paso esté acotado superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuesto puede no estar garantizado en ciertos contextos. Si por ejemplo los números involucrados en la computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la adición requiere un tiempo constante (usando papel y lápiz, compara el tiempo que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlo con enteros de 1000 dígitos).
CONCEPTO.
ResponderEliminarUn grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices.
Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc.
La notación G = A (V, A) se utiliza comúnmente para identificar un grafo.
Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.
CLASIFICACION DE GRAFOS
Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.
Algunos de los principales tipos de grafos son los que se muestran a continuación:
• 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 Kn.
A continuación pueden verse los dibujos de K3, K4, K5 y K6
• Un grafo bipartito regular: se denota Km,n 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.
• 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.
• Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.
GRAFOS EULERIANOS.
ResponderEliminarPara definir un camino euleriano es importante definir un camino euleriano primero. Un camino euleriano se define de la manera más sencilla como un camino que contiene todos los arcos del grafo.
Teniendo esto definido podemos hablar de los grafos eulerianos describiéndolos simplemente como aquel grafo que contiene un camino euleriano. Como ejemplos tenemos las siguientes imágenes:
El primer grafo de ellos no contiene caminos eulerianos mientras el segundo contiene al menos uno.
GRAFOS CONEXOS.
Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”.
ÁRBOLES.
Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también acíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos).
BOSQUES DE ÁRBOLES.
Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos. Como ejemplo tenemos la siguiente figura.
RECORRIDO DE UN GRAFO.
Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida. Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura; y el recorrido en profundidad.
• Recorrido en anchura: El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.
• Recorrido en profundidad: el recorrido en profundidad trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente.
REPRESENTACIÓN DE GRAFOS EN PROGRAMAS.
Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas.
• Representación mediante matrices: La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.
• Representación mediante listas: En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.
• Representación mediante matrices dispersas: Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.
DÍGRAFO (GRAFO DIRIGIDO).
ResponderEliminarA un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas, como en el siguiente caso.
Un grafo es una estructura capaz de representar relaciones complejas entre objetos de un mismo tipo. Formalmente se representa mediante el par G = (V, A), donde:
V es un conjunto de objetos llamados vértices o nodos
A es un conjunto de objetos denominados aristas o arcos.
Las aristas representan relaciones entre los vértices, de forma que una arista es un par (u, v) de vértices de V
Básicamente, podemos clasificar los grafos en 4 tipos dependiendo de dos criterios:
Grafo dirigido. Es aquel cuyas aristas forman pares ordenados (u à v).
Grafo no dirigido. Es aquel cuyas aristas no son pares ordenados.
Grafo etiquetado o valorado. Cuando se asocia información a cada arista de un grafo.
Grafo no etiquetado. Cuando no se asocia ninguna información a las aristas
La teoría de grafos se aplica a campos tan diversos como química, geografía, ingeniería eléctrica, comunicaciones, etc. Un ejemplo de grafo podría ser la red de metro de Madrid, donde los vértices representan las estaciones y las aristas la línea que une dos estaciones:
Otro ejemplo de aplicación de los grafos es la construcción de modelos donde se estudian las relaciones de precedencia que existen entre las tareas que se necesitan para completar un trabajo.
El TAD Grafo
Sol Gran Vía
Tribunal
Plaza de España
Opera Callao
Tirso de Molina
130
120
150
120
160
125
Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo.
Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas. Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.
Historia
ResponderEliminarEl trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología.
En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos.
En 1852 Francis Guthrie planteó el problema de los cuatro colores que plantea si es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que no fue resuelto hasta un siglo después por Kenneth Appel yWolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.
Estructuras de datos en la representación de grafos
Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las características del grafo y elalgoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.
Estructura de lista
lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.
lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.
En esta estructura de datos la idea es asociar a cada vértice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vértices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.
Estructuras matriciales
Matriz de incidencia - El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (1 - conectado, 0 - no conectado)
Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño n2, donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento mx,y es 1, de lo contrario, es 0.
El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n2) operaciones para ordenar una lista de n elementos.
ResponderEliminarSu funcionamiento es el siguiente:
Buscar el mínimo elemento de la lísta
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
De esta manera se puede escribir el siguiente seudocódigo para ordenar una lista de n elementos indexados desde el 1:
para i=1 hasta n-1
minimo = i;
para j=i+1 hasta n
si lista[j] < lista[minimo] entonces
minimo = j /* (!) */
fin si
fin para
intercambiar(lista[i], lista[minimo])
fin para
Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación intercambiar() sería más costosa en este caso. Este algoritmo realiza muchas menos operaciones intercambiar () que el de la burbuja, por lo que lo mejora en algo. Si la línea comentada con (!) se sustituyera por intercambiar (lista[i], lista[j]) tendríamos una versión del algoritmo de la burbuja (naturalmente eliminando la orden intercambiar del final).
Otra desventaja de este algoritmo respecto a otros como el de burbuja o de inserción directa es que no mejora su rendimiento cuando los datos ya están ordenados o parcialmente ordenados. Así como, por ejemplo, en el caso de la ordenación de burbuja se requeriría una única pasada para detectar que el vector ya está ordenado y finalizar, en la ordenación por selección se realizarían el mismo número de pasadas independientemente de si los datos están ordenados o no.
Ejemplo de varios lenguajes de Programación:
Java
public static int[] selección (int[] v) {
int min, aux;
for (int i = 0; i < v.length; i++){
min = i;
for (int j = i + 1; j < v.length; j++){
if (v[min] > v[j]){
min = j;
}
}
aux = v[i];
v[i] = v[min];
v[min] = aux;
}
return v;
}
C
int minimo=0;
for(i=0 ; i x[j]) minimo=j;
}
temp=x[minimo];
x[minimo]=x[i];
x[i]=temp;
}
Basic
For i = 1 To n - 1
minimo = i
For j = i + 1 To n
If x(minimo) > x(j) Then
minimo = j
End If
Next j
temp = x(i)
x(i) = x(minimo)
x(minimo) = temp
Next i
C++
#include
#include
using namespace std;
template
void ordena_seleccion(vector& v) {
for (int i = 0; i < v.size() - 1; ++i) {
int min = i;
for (int c = i + 1; c < v.size(); ++c) {
if (v[min] > v[c]) min = c;
}
T aux = v[i];
v[i] = v[min];
v[min] = aux;
}
}
Perl
sub seleccion {
my $array = shift; # Recibimos una referencia a un array
my $i; # Índice del elemento a comparar
my $j; # Índice del valor mínimo a encontrar
# Para todos los elementos menos el último
for ( $i = 0; $i < $#$array; $i++ ) {
# Índice y valor del elemento a comparar
my ( $m, $x ) = ( $i, $array->[ $m ] );
# Buscamos el valor más pequeño de todos los demás
for ( $j = $i + 1; $j < @$array; $j++ ) {
( $m, $x ) = ( $j, $array->[ $j ] ) # Nuevo mínimo encontrado
if $array->[ $j ] < $x;
}
# Hacemos el intercambio de elementos, si es necesario
@$array[ $m, $i ] = @$array[ $i, $m ] if $m != $i;
}
}
Pascal
ResponderEliminarProcedure SelectionSort(var Sort:Array_integer);
var
a,s,temp:integer;
Begin
For a := 0 to 8 do
For s := a+1 to 9 do
If (Sort[a] > Sort[s]) then
Begin
temp:= Sort[a];
Sort[a] := Sort[s];
Sort[s] := temp;
End;
End;
JavaScript
for(var i=0 ; i vector[j]) menor = j;
}
var temp = vector[menor];
vector[menor] = vector[i];
vector[i] = temp;
}
PHP
function IntercambiarElementos(&$arreglo,$pos1,$pos2){
$aux=$arreglo[$pos1];
$arreglo[$pos1]=$arreglo[$pos2];
$arreglo[$pos2]=$aux;
}
function PosicionMenorElemento($arreglo,$posinicial){
$posmenor=$posinicial;
for($i=$posinicial+1;$i$i){
IntercambiarElementos($arreglo,$i,$posmenor);
}
}
}
Lenguaje de programación Python
def seleccion(lista)
n = len(lista)
for i in range(0,n-1):
k = i
t = lista[i]
for j in range(i,n):
if lista[j] < t:
k = j
t = lista[j]
lista[k] = lista[i]
lista[i] = t
return lista
Complejidad de la búsqueda secuencial
ResponderEliminarLa complejidad de la búsqueda secuencial diferencia entre el comportamiento en el caso peor y mejor. El mejor caso se encuentra cuando aparece una coincidencia en el primer elemento de la lista y en ese caso el tiempo de ejecución es O (1). El caso peor se produce cuando el elemento no está en la lista o se encuentra al final de la lista. Esto requiere buscar en todos los n términos, lo que implica una complejidad de O(n).
El caso medio requiere un poco de razonamiento probabilista. Para el caso de una lista aleatoria es probable que una coincidencia ocurra en cualquier posición. Después de la ejecución de un número grande de búsquedas, la posición media para una coincidencia es el elemento central n/2. El elemento central ocurre después de n/2 comparaciones, que define el coste esperado de la búsqueda. Por esta razón, se dice que la prestación media de la búsqueda secuencial es O(n).
Comparación de la búsqueda binaria y secuencial
Búsqueda Secuencial: Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.
Búsqueda Binaria: El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.
Búsqueda Binaria: En cada comparación se puede eliminar la mitad de los elementos del array.
Primera comparación: array de n elementos
Segunda comparación: array de n/2 elementos
Tercera comparación: array de n/4 elementos
Cuarta comparación: array de n/8 elementos
C-ésima comparación: array de n/2C elementos
Análisis de la Estructura de Objetos.
ResponderEliminarEl análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos.
Objetos y Tipos de Objetos.
En el análisis se trata de identificar los tipos de objeto más que los objetos individuales en un sistema. Los tipos de objetos se definen en base a la comprensión del analista de nuestro mundo. Un objeto puede categorizarse de variadas formas.
Representación para Tipo de Objeto (Persona).
Asociaciones de Objetos.
Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad).
Representación para la Asociación entre dos Tipos de Objetos. Un objeto del tipo persona posee cero o muchos objetos del tipo vehículo. Un objeto del tipo vehículo es de un y sólo un objeto del tipo persona.
Jerarquías de Generalización.
Una de las vías de sentido común por las que el hombre organiza su volumen de conocimiento es el de las jerarquías, de lo más general a lo más específico.
Esquemas de Objetos.
La comprensión de un modelo suele ser más sencilla si los tipos de objetos y relaciones se presentan mediante un diagrama de relación entre objetos; los supertipos y subtipos se presentan en un diagrama de jerarquías de generalización y las estructuras compuestas en un diagrama compuesto. Sin embargo, para los usuarios más sofisticados puede ser útil presentarlo todo en un mismo diagrama, el que se denomina esquema de objetos.
Estas funciones se diferencian en el número y tipo de argumentos, pero también hay funciones sobrecargadas que devuelven tipos distintos.
ResponderEliminarSobrecarga se refiere al uso de un mismo nombre para múltiples significados de un operador o una función.
Dado el énfasis del concepto de clase, el uso principal de la sobrecarga es con las funciones miembro de una clase. Cuando más de una función miembro con igual nombre se declara en una clase, se dice que el nombre de la función está sobrecargado en esa clase. El ámbito del nombre sobrecargado es el de la clase.
La sobrecarga de funciones amigas es similar a la de funciones miembro, con la única diferencia de que es necesaria la palabra reservada friend al igual que en la declaración de cualquier función amiga.
Sobrecarga de operadores
De modo análogo a la sobrecarga de funciones, la sobrecarga de operadores permite al programador dar nuevos significados a los símbolos de los operadores existentes en C++.
C++ permite a los programadores sobrecargar a los operadores para tipos abstractos de datos.
Una ventana es una parte de la pantalla sobre la que se ejecutará un programa o se realizarán una serie de tareas. Todas ellas poseen una serie de elementos comunes (figura de abajo) tales como:
ResponderEliminar• Barra de títulos: Muestra el nombre de la ventana. Con mucha frecuencia el nombre de la ventana contiene el nombre de la aplicación abierta en ella, seguido del nombre del documento activo.
• Barra de menús: Inmediatamente debajo de la barra de títulos de la mayoría de las ventanas, hay un banda horizontal llamada Barra de Menús que contiene nombres tales como Archivo, Edición o ? (Ayuda). Haciendo clic en cualquiera de estos nombres se despliega un menú en forma de persiana, es decir se despliega una lista de comandos. Para escoger uno, basta con desplazar el puntero del ratón sobre el comando correspondiente y hacer clic.
Barra de títulos y barra de menús.
• Botón de minimizar: Haciendo clic sobre este botón (figura inferior) la ventana se reduce y se coloca su nombre en una barra que está en la parte inferior de la pantalla denominada Barra de Tareas.
• Botón de maximizar: En este caso al presionar el botón la ventana aumenta de tamaño hasta ocupar la totalidad de la pantalla.
• Botón de restaurar: Una vez maximizada la ventana, el botón de maximizar cambia al de restaurar. Presionando éste, la ventana vuelve al tamaño que poseía antes de ser maximizada.
• Botón de cerrar: Cierra una ventana y la aplicación que está abierta. Suele estar en la esquina superior derecha o bien en la esquina superior izquierda en forma de un pequeño icono correspondiente a la aplicación.
• Botón de Ayuda: Este botón que aparece en la esquina superior derecha de muchas de las cajas de diálogo, sirve para que Windows muestre información acerca de un elemento de la pantalla. Para ello hacer clic sobre el botón y arrastrar el cursor transformado en un signo de interrogación sobre el objeto de la pantalla que se desconoce o del que se desea obtener una breve explicación.
Para poder realizar cualquier operación dentro de una ventana ésta debe estar activa. Cuando hay dos o más ventanas superpuestas en la pantalla, la ventana activa siempre aparece en primer plano.
ResponderEliminarAnálisis de la Estructura de Objetos.
ResponderEliminarEl análisis de la estructura de objetos (AEO) define las categorías de los objetos que percibimos y las formas en que los asociamos.
Objetos y Tipos de Objetos.
En el análisis se trata de identificar los tipos de objeto más que los objetos individuales en un sistema. Los tipos de objetos se definen en base a la comprensión del analista de nuestro mundo. Un objeto puede categorizarse de variadas formas.
Representación para Tipo de Objeto (Persona).
Asociaciones de Objetos.
Es importante modelar la forma como los objetos se asocian entre sí. Además es necesario identificar el significado de la asociación y la cantidad de objetos con los que un objeto dado puede y debe asociarse (cardinalidad).
Representación para la Asociación entre dos Tipos de Objetos. Un objeto del tipo persona posee cero o muchos objetos del tipo vehículo. Un objeto del tipo vehículo es de un y sólo un objeto del tipo persona.
Jerarquías de Generalización.
Una de las vías de sentido común por las que el hombre organiza su volumen de conocimiento es el de las jerarquías, de lo más general a lo más específico.
Esquemas de Objetos.
La comprensión de un modelo suele ser más sencilla si los tipos de objetos y relaciones se presentan mediante un diagrama de relación entre objetos; los supertipos y subtipos se presentan en un diagrama de jerarquías de generalización y las estructuras compuestas en un diagrama compuesto. Sin embargo, para los usuarios más sofisticados puede ser útil presentarlo todo en un mismo diagrama, el que se denomina esquema de objetos.
Ciclo vital
ResponderEliminarEl tiempo de vida o ciclo vital ("Lifetime") de un objeto es una propiedad de tiempo de ejecución ("Runtime"). Viene determinado por el lapso entre su creación y su destrucción. Por supuesto no puede exceder la duración de su almacenamiento.
El ciclo vital comienza cuando se le asigna espacio de almacenamiento y, si no es un objeto trivial, cuando el objeto es convenientemente iniciado por su constructor. Finaliza cuando es llamado el destructor o se rehúsa la zona de almacenamiento que le había sido asignada.
Nota: decimos que un objeto es trivial cuando es, por ejemplo, un tipo simple preconstruido en el lenguaje. En este caso una expresión del tipo x hasta para que el compilador pueda reservar espacio de almacenamiento.
Observe que el ciclo vital de los objetos automáticos y estáticos es controlado automáticamente por el compilador. En los primeros la destrucción se realiza cuando el objeto sale de ámbito. En los segundos la destrucción ocurre con las rutinas de finalización del programa. Por su parte el ciclo vital de los objetos dinámicos es controlado por el programador.
Generalmente esta memoria reside en un segmento de datos fijo, situado de acuerdo con el modelo de memoria que se esté utilizando, aunque en los ambientes de 32 bits de PC y compatibles, solo está disponible el denominado modelo plano ("Flat memory model").
Esta última, denominada "dinámica" en la mayoría de los textos, incluyendo la propia literatura inglesa (por ejemplo los manuales de Borland), nos parece un término desafortunado para designar la duración de los objetos almacenados en el montón. Por esta razón preferimos designarlos como objetos "persistentes", ya que esta palabra califica más adecuadamente las características de tales objetos.
Precisamente por esto y en especial si se trata de punteros, su uso puede resultar peligroso si no son inicializados correctamente.
Hay una excepción en los llamados punteros inteligentes que destruyen el objeto señalado antes de ser ellos mismos destruidos.
Concepto de Grafo
ResponderEliminarLos grafos son un conjunto de puntos, de los cuales algún par de ellos está conectado por unas líneas. Si estas líneas son flechas, hablaremos de grafo dirigido (digrafo), mientras que si son simples líneas estamos ante un grafo no dirigido.
Más formalmente se pueden definir como un conjunto de vértices y un conjunto de aristas. Cada arista es un par (u,v), donde u y v pertenecen al conjunto de vértices. Si este par es ordenado el grafo es dirigido.
Par de ejemplos:
Grafo no dirigido Grafo dirigido.
CLASIFICACION DE GRAFOS
Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.
Algunos de los principales tipos de grafos son los que se muestran a continuación:
• 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 Kn.
A continuación pueden verse los dibujos de K3, K4, K5 y K6
• Un grafo bipartito regular: se denota Km,n 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.
• Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.
Teniendo esto definido podemos hablar de los grafos eulerianos describiéndolos simplemente como aquel grafo que contiene un camino euleriano. Como ejemplos tenemos las siguientes imágenes:
ResponderEliminarEl primer grafo de ellos no contiene caminos eulerianos mientras el segundo contiene al menos uno.
GRAFOS CONEXOS.
Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”.
ÁRBOLES.
Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también acíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos).
BOSQUES DE ÁRBOLES.
Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos. Como ejemplo tenemos la siguiente figura.
RECORRIDO DE UN GRAFO.
Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida. Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura; y el recorrido en profundidad.
• Recorrido en anchura: El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.
• Recorrido en profundidad: el recorrido en profundidad trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente.
REPRESENTACIÓN DE GRAFOS EN PROGRAMAS.
Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas.
• Representación mediante matrices: La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.
• Representación mediante listas: En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.
• Representación mediante matrices dispersas: Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.
Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo.
ResponderEliminarEl ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n2) operaciones para ordenar una lista de n elementos.
Su funcionamiento es el siguiente:
Buscar el mínimo elemento de la lísta
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
El método de shell es una versión mejorada del método de inserción directa. Este método también se conoce con el nombre de inserción con incrementos decrecientes.
ResponderEliminarEn el método de ordenación por inserción directa cada elemento se compara para su ubicación correcta en el arreglo, con los elementos que se encuentran en la parte izquierda del mismo. Si el elemento a insertar es más pequeño que el grupo de elementos que se encuentran a su izquierda, es necesario efectuar entonces varias comparaciones antes de su ubicación.
Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño pero con incrementos decrecientes. Así, los elementos quedarán ordenados en el arreglo más rápidamente. Para comprender mejor este algoritmo analícese el siguiente caso.
Considérese un arreglo que contenga 16 elementos. En primer lugar se dividirían los elementos del arreglo en 8 grupos teniendo en cuenta los elementos que se encuentran a 8 posiciones de distancia entre si y se ordenan por separado. Quedarán en el primer grupo los elementos (A[1],A[9]); en el segundo (A[2],A[10]); en el tercero (A[3],A[1]); y así sucesivamente. Después de este primer paso se dividirán los elementos del arreglo en 4 grupos, teniendo en cuenta ahora los elementos que se encuentren a 4 posiciones de distancia entre sí y se los ordenará por separado. Quedarán en el primer grupo los elementos (A[1],A[5]), (A[9],A[13]), en el segundo. (A[2],A[6]), (A[10],A[14]), y así sucesivamente. En el tercer paso se dividirán los elementos del arreglo en grupos, tomando en cuenta los elementos que se encuentran ahora a dos posiciones de distancia entre sí y nuevamente se les ordenará por separado.
En el primer grupo quedarán (A[1],A[3], A[5],A[7], A[9],A[11], A[13],A[15]) y en el segundo grupo (A[2], ],A[4], A[6],A[8], A[10],A[12], A[14],A[16]).
ResponderEliminarFinalmente se agruparán y ordenarán los elementos de manera normal, es decir, de uno en uno.
El análisis de eficiencia del método de Shell es un problema muy complicado y aún no resuelto. No se ha podido establecer hasta el momento la mejor secuencia de incrementos cuando n es grande. Cabe recordar que cada vez que se propone una secuencia de intervalos es necesario “correr” el algoritmo para analizar el tiempo de ejecución del mismo.
En 1969 Pratt descubrió que el tiempo de ejecución del algoritmo es del orden de n*(log n)2. Unas pruebas exhaustivas realizadas para obtener la mejor secuencia de intervalos cuando el número de elementos del arreglo es igual a 8 arrojaron como resultado que la mejor secuencia corresponde a un intervalo de 1, que no es más que el método de inserción directa estudiado previamente. Estas pruebas también determinaron que el menor número de movimientos se registraba con la secuencia 3,2,1. Cabe aclarar que las pruebas exhaustivas corresponden al análisis de (8!) posibilidades, es decir, 40 320 casos diferentes.
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(n2) 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(nlog2 n) en el peor caso. Esto es mejor que las O(n2) 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 inserción, 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.
ResponderEliminarConsidere un pequeño valor que está inicialmente almacenado en el final del vector. Usando un ordenamiento O(n2) como el ordenamiento de burbuja o el ordenamiento por inserción, tomará aproximadamente n comparaciones e intercambios para mover este valor hacia el otro extremo del vector. El Shell sort primero mueve los valores usando tamaños de espacio gigantes, de manera que un valor pequeño se moverá bastantes posiciones hacia su posición final, con sólo unas pocas comparaciones e intercambios.
Uno puede visualizar el algoritmo Shell sort de la siguiente manera: coloque la lista en una tabla y ordene las columnas (usando un ordenamiento por inserción). Repita este proceso, cada vez con un número menor de columnas más largas. Al final, la tabla tiene sólo una columna. Mientras que transformar la lista en una tabla hace más fácil visualizarlo, el algoritmo propiamente hace su ordenamiento en contexto (incrementando el índice por el tamaño de paso, esto es usando i += tamaño_de_paso en vez de i++).
Por ejemplo, considere una lista de números como [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas. Esto quedaría así:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
Entonces ordenamos cada columna, lo que nos da
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
Cuando lo leemos de nuevo como una única lista de números, obtenemos [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. Aquí, el 10 que estaba en el extremo final, se ha movido hasta el extremo inicial. Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de 3 posiciones, y después un ordenamiento con un espacio de 1 posición (ordenamiento por inserción simple).
El Shell sort lleva este nombre en honor a su inventor, Donald Shell, que lo publicó en 1959. Algunos libros de texto y referencias antiguas le llaman ordenación "Shell-Metzner" por Marlene Metzner Norton, pero según Metzner, "No tengo nada que ver con el algoritmo de ordenamiento, y mi nombre nunca debe adjuntarse a éste."
ResponderEliminarSecuencia de espacios
La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la secuencia de espacios. Continúa para realizar un ordenamiento por inserción con espacio para cada número en la secuencia, hasta que termina con un espacio de 1. Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada.
La secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar 1. Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción, se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento O(n2) del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice impar.
Quizás la propiedad más crucial del Shell sort es que los elementos permanecen k-ordenados incluso mientras el espacio disminuye. Se dice que un vector dividido en k sub-vectores esta k-ordenado si cada uno de esos sub-vectores esta ordenado en caso de considerarlo aislado. Por ejemplo, si una lista fue 5-ordenada y después 3-ordenada, la lista está ahora no sólo 3-ordenada, sino tanto 5-ordenada como 3-ordenada. Si esto no fuera cierto, el algoritmo desharía el trabajo que había hecho en iteraciones previas, y no conseguiría un tiempo de ejecución tan bajo.
Dependiendo de la elección de la secuencia de espacios, Shell sort tiene un tiempo de ejecución en el peor caso de O(n2) (usando los incrementos de Shell que comienzan con 1/2 del tamaño del vector y se dividen por 2 cada vez), O(n3 / 2) (usando los incrementos de Hibbard de 2k − 1), O(n4 / 3) (usando los incrementos de Sedgewick de 9(4i) − 9(2i) + 1, o 4i + 1 + 3(2i) + 1), o O(nlog2n), y posiblemente mejores tiempos de ejecución no comprobados. La existencia de una implementación O(nlogn) en el peor caso del Shell sort permanece como una pregunta por resolver.
Implementaciones
El Shell sort se usa comúnmente en lenguajes de programación; esto es una implementación del algoritmo en C/C++ para ordenar un vector de enteros. La secuencia de incrementos usada en este ejemplo de código da un tiempo de ejecución O(n2) en el peor caso.
void shell_sort(int A[], int size)
{
int i, j, incrmnt, temp;
incrmnt = size/2;
while (incrmnt > 0)
{
for (i=incrmnt; i < size; i++)
{
j = i;
temp = A[i];
while ((j >= incrmnt) && (A[j-incrmnt] > temp))
{
A[j] = A[j - incrmnt];
j = j - incrmnt;
}
A[j] = temp;
}
incrmnt /= 2;
}
}
El algoritmo Shell sort en Java
ResponderEliminarpublic static void shellSort(int[] a) {
for ( int increment = a.length / 2;
increment > 0;
increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) {
for (int i = increment; i < a.length; i++) {
for (int j = i; j >= increment && a[j - increment] > a[j]; j -= increment) {
int temp = a[j];
a[j] = a[j - increment];
a[j - increment] = temp;
}
}
}
}
El algoritmo Shell sort en Perl
sub shellsort {
my $array = shift; # Recibimos una referencia a un array
my $i; # Índice del elemento a comparar
my $j; # Índice del elemento actual a comparar
my $shell; # Tamaño del incremento
# Calculamos el valor del incremento
for ( $shell = 1; $shell < @$array; $shell = 2 * $shell + 1 ) {
;
}
do {
$shell = int( ( $shell - 1 ) / 2 );
# Para todos los elementos, elegidos con un incremento
for ( $i = $shell; $i < @$array; $i++ ) {
for ( $j = $i - $shell;
$j >= 0 && $array->[ $j ] > $array->[ $j + $shell ];
$j -= $shell ) {
# Intercambiamos valores
@$array[ $j, $j + $shell ] = @$array[ $j + $shell, $j ];
}
}
} while $shell > 1;
}
El algoritmo Shell sort en Python
def shellsort(a):
def new_increment(a):
i = int(len(a) / 2)
yield i
while i != 1:
if i == 2:
i = 1
else:
i = int(numpy.round(i/2.2))
yield i
for increment in new_increment(a):
for i in xrange(increment, len(a)):
for j in xrange(i, increment-1, -increment):
if a[j - increment] < a[j]:
break
temp = a[j];
a[j] = a[j - increment]
a[j - increment] = temp
return a
El algoritmo Shell sort en C#
using System;
public class ShellSorter
{
public void Sort(int [] list)
{
int j,inc;
inc=list.length/2;
while(inc>0)
{
for(int i=inc+1;i0)
{
if(list[j] > list[j+inc])
{
Swap(list[j],list[j+inc]);
j=j-inc;
}
else
{
j=0;
}
}
}
inc=inc/2;
}
}
}
public class MainClass
{
public static void Main()
{
int[] iArrary=new int[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47};
ShellSorter sh=new ShellSorter();
sh.Sort(iArrary);
for(int m=0;m<=13;m++)
Console.WriteLine("{0}",iArrary[m]);
}
}
El algoritmo Shell sort en Visual Basic
Sub Shell_Sort(ByRef V) 'debemos pasarle el arreglo(de enteros) desde el programa principal()
Dim I, Medio, J, Temp As Integer
Dim Ordenado As Boolean
Medio = UBound(V)
While (Medio > 0)
Medio = Medio \ 2
Do
Ordenado = True
For J = 0 To UBound(V) - Medio ' se asume que el arreglo va de 0 a UBound(V) elementos
I = J + Medio
If V(J) > V(I) Then ' Se intercambian los elementos
Temp = V(J)
V(J) = V(I)
V(I) = Temp
Ordenado = False
End If
Next
Loop Until Ordenado
Wend
End Sub
----
Sub principal()
Dim Arr(99) As Integer
Dim I As Integer
For I = 0 To 99
Arr(I) = Int(Rnd() * 1000) ' Se llena el arreglo con números menores que 1000
Next I
Call Shell_Sort(Arr)
End Sub
Algoritmo Selección
ResponderEliminarEl método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición y así excluirlo de la lista. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo.
Es un algoritmo lento, a pesar que sólo realiza un intercambio en cada ejecución del ciclo externo, puede ser una buena elección para listas con registros grandes y claves pequeñas.
PSEUDOCÓDIGO
ALGORITMO SELECCIÓN
INICIO
ENTERO I, J, MIN, ARREGLO[N]
I 0
MIENTRAS(I < N)
{
MIN I
J I + 1
MIENTRAS(J < N)
{
SI(ARREGLO[J] < ARREGLO[I])
{
MIN J
INTERCAMBIA(ARREGLO[MIN],ARREGLO[I])
}
J J + 1
}
I I + 1
}
FIN
CÓDIGO EN C++
void seleccion(void)
{
int i, j, min, ARREGLO[N], aux;
i = 0
while(i < N)
{
min = i;
j = i + 1;
while (j < N)
{
if(ARREGLO[j] < ARREGLO[i])
{
min = j;
aux = ARREGLO[i];
ARREGLO[i] = ARREGLO[min];
ARREGLO[min] = aux;
}
j++;
}
i++
Ejemplo:
[0] 15 10 10 10 7 7 7 7 7 7 7 7 7 7 7
[1] 10 15 15 15 15 15 14 11 10 10 10 10 10 10 10
[2] 14 14 14 14 14 14 15 15 15 15 14 11 11 11 11
[3] 11 11 11 11 11 11 11 14 14 14 15 15 15 14 14
[4] 7 7 7 7 10 10 10 10 11 11 11 14 14 15 15
I 0 0 0 0 0 1 1 1 1 2 2 2 3 3 4
J 1 1 2 3 4 2 2 3 4 3 3 4 4 4 5
MIN 0 0 1 1 4 1 2 3 4 2 3 4 3 4 4
Tiempo de Ejecución: El ciclo externo se ejecuta n veces para una lista de n elementos. Cada búsqueda requiere comparar todos los elementos no clasificados. Luego la complejidad es O(n2). Este algoritmo presenta un comportamiento constante independiente del orden de los datos.
Estabilidad: Puede que haya algo de discrepancia pero esta implementación parece ser estable, puede verificar esto ordenando un conjunto de datos que tenga un par de ellos con la misma clave, el orden relativo entre ellos es conservado, pero algunos autores dicen que no es estable.
Ventajas:
• Fácil implementación.
• No requiere memoria adicional.
• Realiza pocos intercambios.
• Rendimiento constante: poca diferencia entre el peor y el mejor caso.
Desventajas:
• Lento.
• Realiza numerosas comparaciones.
Algoritmo Shake
Conocido como doble ordenamiento de burbuja; recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo coloca en su posición y al mismo tiempo también coloca el elemento menor en su posición.
PSEUDOCÓDIGO
ALGORITMO SHAKE
INICIO
ENTERO I 0, ARREGLO[N]
ENTERO K N - 1
ENTERO MIN, MAX, J, AUX
MIENTRAS(I < K)
{
MIN I
MAX I
PARA(J I + 1, HASTA K, J J + 1)
{
SI(ARREGLO[J] < ARREGLO[MIN])
{
MIN J
}
SI(ARREGLO[J] > ARREGLO[MAX])
{
MAX J
}
}
AUX ARREGLO[MIN]
ARREGLO[MIN] ARREGLO[I]
ARREGLO[I] AUX
SI(MAX I)
{
AUX ARREGLO[MIN]
ARREGLO[MIN] ARREGLO[K]
ARREGLO[K] AUX
}
SI NO
{
AUX ARREGLO[MAX]
ARREGLO[MAX] ARREGLO[K]
ARREGLO[K] AUX
}
I I + 1;
K K - 1;
}
}
CÓDIGO EN C++
void shake(void)
{
int i = 0, ARREGLO[N];
int k = N - 1;
int min, max, j, aux;
while (i < k)
{
min = i;
max = i;
for(j = i + 1; j <= k; j++)
{
if (ARREGLO[j] < ARREGLO[min])
min = j;
if (ARREGLO[j] > ARREGLO[max])
max = j;
}
aux = ARREGLO[min];
ARREGLO[min] = ARREGLO[i];
ARREGLO[i] = aux;
if (max == i)
{
aux = ARREGLO[min];
ARREGLO [min] = ARREGLO[k];
ARREGLO[k] = aux;
}
else
{
aux = ARREGLO[max];
ARREGLO[max] = ARREGLO[k];
ARREGLO[k] = aux;
}
i++;
k--;
}
}
Ejemplo:
ResponderEliminar[0] 15 7 7
[1] 10 10 10
[2] 14 14 11
[3] 11 11 14
[4] 7 15 15
I 0 1 2
K 4 3 2
J 1 2 3 4 2 3 4 3
MIN 0 1 4 1 2
MAX 0 1 2 2
Tiempo de ejecución:
El bucle interno se efectuará ; el bucle interior se ejecutará entonces por la regla de la multiplicación tenemos O(n2)
Ventajas:
• Relativamente fácil de implementar.
• No requiere memoria adicional.
Estabilidad: Es inestable no mantiene el orden relativo de los registros.
Desventajas:
• Realiza numerosas comparaciones.
• Realiza numerosos intercambios.
El método de shell es una versión mejorada del método de inserción directa. Este método también se conoce con el nombre de inserción con incrementos decrecientes.
ResponderEliminarEn el método de ordenación por inserción directa cada elemento se compara para su ubicación correcta en el arreglo, con los elementos que se encuentran en la parte izquierda del mismo. Si el elemento a insertar es más pequeño que el grupo de elementos que se encuentran a su izquierda, es necesario efectuar entonces varias comparaciones antes de su ubicación.
Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño pero con incrementos decrecientes. Así, los elementos quedarán ordenados en el arreglo más rápidamente. Para comprender mejor este algoritmo analícese el siguiente caso.
Considérese un arreglo que contenga 16 elementos. En primer lugar se dividirían los elementos del arreglo en 8 grupos teniendo en cuenta los elementos que se encuentran a 8 posiciones de distancia entre si y se ordenan por separado. Quedarán en el primer grupo los elementos (A[1],A[9]); en el segundo (A[2],A[10]); en el tercero (A[3],A[1]); y así sucesivamente. Después de este primer paso se dividirán los elementos del arreglo en 4 grupos, teniendo en cuenta ahora los elementos que se encuentren a 4 posiciones de distancia entre sí y se los ordenará por separado. Quedarán en el primer grupo los elementos (A[1],A[5]), (A[9],A[13]), en el segundo. (A[2],A[6]), (A[10],A[14]), y así sucesivamente. En el tercer paso se dividirán los elementos del arreglo en grupos, tomando en cuenta los elementos que se encuentran ahora a dos posiciones de distancia entre sí y nuevamente se les ordenará por separado. En el primer grupo quedarán (A[1],A[3], A[5],A[7], A[9],A[11], A[13],A[15]) y en el segundo grupo (A[2], ],A[4], A[6],A[8], A[10],A[12], A[14],A[16]).
Quicksort
ResponderEliminarEl ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
Descripción del algoritmo
El algoritmo fundamental es el siguiente:
Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.
Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n•log n).
En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos esta ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.
En el caso promedio, el orden es O(n•log n).
No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.
Demostración
Podríamos probar el orden de ejecución en el mejor caso de la siguiente manera:
Vamos a suponer que el número total de elementos a ordenar es potencia de dos, es decir, n = 2k. de aquí podemos ver que k =log2(n), donde k es el número de divisiones que realizará el algoritmo.
En la primera fase del algoritmo habrán n comparaciones, en la segunda fase el algoritmo creará dos sublistas aproximadamente de tamaño n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n.
En conclusión, el número total de comparaciones que hace el algoritmo es:
n + n + n + ..... + n = kn, donde k = log2(n), por tanto el tiempo de ejecución del algoritmo en el mejor caso es O(n.log2n)
Optimización del algoritmo
Cabe destacar que de usarse en su versión recursiva las siguientes optimizaciones y sus desventajas no se ven vistas en el tiempo de ejecución del mismo manteniéndose, así el tiempo de ejecución planteado en un principio.
Finalmente se agruparán y ordenarán los elementos de manera normal, es decir, de uno en uno.
ResponderEliminarEl análisis de eficiencia del método de Shell es un problema muy complicado y aún no resuelto. No se ha podido establecer hasta el momento la mejor secuencia de incrementos cuando n es grande. Cabe recordar que cada vez que se propone una secuencia de intervalos es necesario “correr” el algoritmo para analizar el tiempo de ejecución del mismo.
En 1969 Pratt descubrió que el tiempo de ejecución del algoritmo es del orden de n*(log n)2. Unas pruebas exhaustivas realizadas para obtener la mejor secuencia de intervalos cuando el número de elementos del arreglo es igual a 8 arrojaron como resultado que la mejor secuencia corresponde a un intervalo de 1, que no es más que el método de inserción directa estudiado previamente. Estas pruebas también determinaron que el menor número de movimientos se registraba con la secuencia 3,2,1. Cabe aclarar que las pruebas exhaustivas corresponden al análisis de (8!) posibilidades, es decir, 40 320 casos diferentes.
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(n2) 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(nlog2 n) en el peor caso. Esto es mejor que las O(n2) 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 inserción, 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.
Considere un pequeño valor que está inicialmente almacenado en el final del vector. Usando un ordenamiento O(n2) como el ordenamiento de burbuja o el ordenamiento por inserción, tomará aproximadamente n comparaciones e intercambios para mover este valor hacia el otro extremo del vector. El Shell sort primero mueve los valores usando tamaños de espacio gigantes, de manera que un valor pequeño se moverá bastantes posiciones hacia su posición final, con sólo unas pocas comparaciones e intercambios.
Uno puede visualizar el algoritmo Shell sort de la siguiente manera: coloque la lista en una tabla y ordene las columnas (usando un ordenamiento por inserción). Repita este proceso, cada vez con un número menor de columnas más largas. Al final, la tabla tiene sólo una columna. Mientras que transformar la lista en una tabla hace más fácil visualizarlo, el algoritmo propiamente hace su ordenamiento en contexto (incrementando el índice por el tamaño de paso, esto es usando i += tamaño_de_paso en vez de i++).
Por ejemplo, considere una lista de números como [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas.
Cuando lo leemos de nuevo como una única lista de números, obtenemos [10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45]. Aquí, el 10 que estaba en el extremo final, se ha movido hasta el extremo inicial. Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de 3 posiciones, y después un ordenamiento con un espacio de 1 posición (ordenamiento por inserción simple).
ResponderEliminarEl Shell sort lleva este nombre en honor a su inventor, Donald Shell, que lo publicó en 1959. Algunos libros de texto y referencias antiguas le llaman ordenación "Shell-Metzner" por Marlene Metzner Norton, pero según Metzner, "No tengo nada que ver con el algoritmo de ordenamiento, y mi nombre nunca debe adjuntarse a éste."
Secuencia de espacios
La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la secuencia de espacios. Continua para realizar un ordenamiento por inserción con espacio para cada número en la secuencia, hasta que termina con un espacio de 1. Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada.
La secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar 1. Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción, se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento O(n2) del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice impar.
Quizás la propiedad más crucial del Shell sort es que los elementos permanecen k-ordenados incluso mientras el espacio disminuye. Se dice que un vector dividido en k sub-vectores esta k-ordenado si cada uno de esos sub-vectores esta ordenado en caso de considerarlo aislado. Por ejemplo, si una lista fue 5-ordenada y después 3-ordenada, la lista está ahora no sólo 3-ordenada, sino tanto 5-ordenada como 3-ordenada. Si esto no fuera cierto, el algoritmo desharía el trabajo que había hecho en iteraciones previas, y no conseguiría un tiempo de ejecución tan bajo.
Dependiendo de la elección de la secuencia de espacios, Shell sort tiene un tiempo de ejecución en el peor caso de O(n2) (usando los incrementos de Shell que comienzan con 1/2 del tamaño del vector y se dividen por 2 cada vez), O(n3 / 2) (usando los incrementos de Hibbard de 2k − 1), O(n4 / 3) (usando los incrementos de Sedgewick de 9(4i) − 9(2i) + 1, o 4i + 1 + 3(2i) + 1), o O(nlog2n), y posiblemente mejores tiempos de ejecución no comprobados. La existencia de una implementación O(nlogn) en el peor caso del Shell sort permanece como una pregunta por resolver.
El Shell sort se usa comúnmente en lenguajes de programación; esto es una implementación del algoritmo en C/C++ para ordenar un vector de enteros. La secuencia de incrementos usada en este ejemplo de código da un tiempo de ejecución O(n2) en el peor caso.
ResponderEliminarAlgoritmo Selección
El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición y así excluirlo de la lista. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo.
Es un algoritmo lento, a pesar que sólo realiza un intercambio en cada ejecución del ciclo externo, puede ser una buena elección para listas con registros grandes y claves pequeñas.
Tiempo de Ejecución: El ciclo externo se ejecuta n veces para una lista de n elementos. Cada búsqueda requiere comparar todos los elementos no clasificados. Luego la complejidad es O(n2). Este algoritmo presenta un comportamiento constante independiente del orden de los datos.
ResponderEliminarEstabilidad: Puede que haya algo de discrepancia pero esta implementación parece ser estable, puede verificar esto ordenando un conjunto de datos que tenga un par de ellos con la misma clave, el orden relativo entre ellos es conservado, pero algunos autores dicen que no es estable.
Ventajas:
• Fácil implementación.
• No requiere memoria adicional.
• Realiza pocos intercambios.
• Rendimiento constante: poca diferencia entre el peor y el mejor caso.
Desventajas:
• Lento.
• Realiza numerosas comparaciones.
Algoritmo Shake
Conocido como doble ordenamiento de burbuja; recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo coloca en su posición y al mismo tiempo también coloca el elemento menor en su posición.
Tiempo de ejecución:
El bucle interno se efectuará ; el bucle interior se ejecutará entonces por la regla de la multiplicación tenemos O(n2)
Ventajas:
• Relativamente fácil de implementar.
• No requiere memoria adicional.
Estabilidad: Es inestable no mantiene el orden relativo de los registros.
Desventajas:
• Realiza numerosas comparaciones.
• Realiza numerosos intercambios.
Quicksort
ResponderEliminarEl ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
Descripción del algoritmo
El algoritmo fundamental es el siguiente:
Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.
Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n•log n).
En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos esta ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.
• HeapSort :
ResponderEliminar- Este algoritmo no es estable, no mantiene el orden relativo inicial porque elementos iguales pueden terminar en distintos niveles del heap.
- Vemos claramente en el código que no requiere memoria adicional para ordenar ya que solo ocupa 1 o 2 variables temporales para hacer los “intercambie” o “exchange”.
- Funciona también claramente a base de comparación, Heapify ordena comparando al Padre con sus 2 hijos para luego ver si los cambia o no.
Además tenemos que el tiempo de ejecución de HEAPIFY para un heap de n nodos es O(log n).
Y además tenemos un FOR dentro de HeapSort, lo que nos dice que HEAPIFY se ejecuta N-1 veces.
- Los Casos Medio y Mejor son también O( ) ya que igual entran al Build-Heap y al FOR, y en Heapify su tiempo de ejecución sigue teniendo una complejidad de O(log n).
• Búsqueda secuencial.
ResponderEliminarEste método sirve para cualquier tipo de array. Consiste en ir recorriendo el contenido del array hasta que se encuentre el dato buscado o se llegue al final. Este método no es muy efectivo, puesto que al enfrentarse a un alto numero de información, si el dato buscado no se encuentra al principio, resulta muy lento.
Búsqueda binaria.
Este método de búsqueda solo puede utilizarse con un array ordenado. Es más eficaz que la búsqueda secuencial. Consiste en un procedimiento recursivo que compara el elemento buscado con el elemento que ocupe la posición media de un rango comprendido entre el principio y el final de la estructura. Si el elemento buscado es mayor que el comparado se redefinirá el rango entre el elemento que ocupa la posición media y el elemento que ocupa el final del rango, sí no, hace lo mismo pero entre la mitad del rango y el principio. Y así hasta dar con el dato buscado o no encontrarlo.
El algoritmo de búsqueda lineal es uno de los más utilizados en situaciones bastante comunes. Es también uno de los algoritmos más sencillos e intuitivos.
Sin embargo, resulta curioso comprobar cómo en gran cantidad de aplicaciones, muchas de ellas de ámbito altamente «profesional» se perpetran extrañas implementaciones que en algunos casos conllevan manifiestas ineficiencias y en otros peligros de salirse de los límites de los datos, por no hablar de situaciones en las que la programación estructurada se deja de lado.
En éste artículo vamos a reflexionar acerca de la búsqueda lineal y de sus posibles implementaciones defendiendo la bondad o no de cada una de ellas.
El escenario en el que se aplica el algoritmo es simple: tenemos una estructura de datos que es posible recorrer secuencialmente (aunque pueda ser recorrida de otra forma, por ejemplo, aleatoriamente, para este algoritmo basta con que se pueda hacer secuencialmente) y queremos saber si alguno de los datos de la estructura cumple algún predicado, y/o en qué posición está ese dato. Si hubiese varios datos que lo cumplen, basta con encontrar el primer dato que cumple dicho predicado. En este contexto, utilizamos predicado como una cualidad o condición del dato que sea comprobable mediante una expresión lógica booleana... es decir... que se pueda evaluar a verdadero o a falso para un determinado dato.
Esa formulación básica puede ser asimilada a otras muchas situaciones... una vez encontrado un algoritmo de búsqueda lineal genérico veremos que la misma estructura puede ser adaptada a otros problemas de búsqueda... pero ya hablaremos de ello en otros artículos.
Como hay que empezar por algún sitio, en éste artículo lo haremos razonando sobre un supuesto básico: saber si un elemento se encuentra en un array unidimensional, y si es así, conocer su posición.
Supongamos un array de enteros llamado A y un entero llamado x. Construiremos un método tal que dado el array A y el entero x nos diga si hay algún elemento en A cuyo valor sea x, y si es así, su posición.
Si hay algún entero en A que sea igual a x, nos devolverá su posición. Si no hay ninguno, utilizaremos el viejo truco de indicarlo devolviendo un "-1". Como las posiciones del array son números mayores o iguales a 0 y el tipo de retorno del método es un int, utilizamos un negativo (el -1) que es un valor que como posición del array no tiene sentido, para indicar que no se ha encontrado.
Una de las implemetaciones que se ven a menudo es la que sigue a continuación. Es muy común, sin embargo, muy ineficiente. En ella, se utiliza un bucle for, para recorrer todos los elementos del array, y una variable llamada posicion que va a contener la posición en la que se ha encontrado un elemento de A que es igual a x. Como inicialmente, cuando el algoritmo comienza, no se ha encontrado ningún elemento, se inicializa esa variable a "-1" directamente. A medida que avanza el bucle for, si encontramos un elemento que sea igual a x, cambiamos el valor de la variable posición.
El método de shell es una versión mejorada del método de inserción directa. Este método también se conoce con el nombre de inserción con incrementos decrecientes.
ResponderEliminarEn el método de ordenación por inserción directa cada elemento se compara para su ubicación correcta en el arreglo, con los elementos que se encuentran en la parte izquierda del mismo. Si el elemento a insertar es más pequeño que el grupo de elementos que se encuentran a su izquierda, es necesario efectuar entonces varias comparaciones antes de su ubicación.
Shell propone que las comparaciones entre elementos se efectúen con saltos de mayor tamaño pero con incrementos decrecientes. Así, los elementos quedarán ordenados en el arreglo más rápidamente. Para comprender mejor este algoritmo analícese el siguiente caso.
Considérese un arreglo que contenga 16 elementos. En primer lugar se dividirían los elementos del arreglo en 8 grupos teniendo en cuenta los elementos que se encuentran a 8 posiciones de distancia entre si y se ordenan por separado. Quedarán en el primer grupo los elementos (A[1],A[9]); en el segundo (A[2],A[10]); en el tercero (A[3],A[1]); y así sucesivamente. Después de este primer paso se dividirán los elementos del arreglo en 4 grupos, teniendo en cuenta ahora los elementos que se encuentren a 4 posiciones de distancia entre sí y se los ordenará por separado. Quedarán en el primer grupo los elementos (A[1],A[5]), (A[9],A[13]), en el segundo. (A[2],A[6]), (A[10],A[14]), y así sucesivamente. En el tercer paso se dividirán los elementos del arreglo en grupos, tomando en cuenta los elementos que se encuentran ahora a dos posiciones de distancia entre sí y nuevamente se les ordenará por separado.
Quicksort
ResponderEliminarEl ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
Descripción del algoritmo
El algoritmo fundamental es el siguiente:
Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.
Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n•log n).
En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos esta ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.
• HeapSort :
ResponderEliminar- Este algoritmo no es estable, no mantiene el orden relativo inicial porque elementos iguales pueden terminar en distintos niveles del heap.
- Vemos claramente en el código que no requiere memoria adicional para ordenar ya que solo ocupa 1 o 2 variables temporales para hacer los “intercambie” o “exchange”.
- Funciona también claramente a base de comparación, Heapify ordena comparando al Padre con sus 2 hijos para luego ver si los cambia o no.
Además tenemos que el tiempo de ejecución de HEAPIFY para un heap de n nodos es O(log n).
Y además tenemos un FOR dentro de HeapSort, lo que nos dice que HEAPIFY se ejecuta N-1 veces.
- Los Casos Medio y Mejor son también O( ) ya que igual entran al Build-Heap y al FOR, y en Heapify su tiempo de ejecución sigue teniendo una complejidad de O(log n).
• HeapSort :
- Este algoritmo no es estable, no mantiene el orden relativo inicial porque elementos iguales pueden terminar en distintos niveles del heap.
- Vemos claramente en el código que no requiere memoria adicional para ordenar ya que solo ocupa 1 o 2 variables temporales para hacer los “intercambie” o “exchange”.
- Funciona también claramente a base de comparación, Heapify ordena comparando al Padre con sus 2 hijos para luego ver si los cambia o no.
Además tenemos que el tiempo de ejecución de HEAPIFY para un heap de n nodos es O(log n).
Y además tenemos un FOR dentro de HeapSort, lo que nos dice que HEAPIFY se ejecuta N-1 veces.
- Los Casos Medio y Mejor son también O( ) ya que igual entran al Build-Heap y al FOR, y en Heapify su tiempo de ejecución sigue teniendo una complejidad de O(log n).
Complejidad de la búsqueda secuencial
ResponderEliminarLa complejidad de la búsqueda secuencial diferencia entre el comportamiento en el caso peor y mejor. El mejor caso se encuentra cuando aparece una coincidencia en el primer elemento de la lista y en ese caso el tiempo de ejecución es O (1). El caso peor se produce cuando el elemento no está en la lista o se encuentra al final de la lista. Esto requiere buscar en todos los n términos, lo que implica una complejidad de O(n).
El caso medio requiere un poco de razonamiento probabilista. Para el caso de una lista aleatoria es probable que una coincidencia ocurra en cualquier posición. Después de la ejecución de un número grande de búsquedas, la posición media para una coincidencia es el elemento central n/2. El elemento central ocurre después de n/2 comparaciones, que define el coste esperado de la búsqueda. Por esta razón, se dice que la prestación media de la búsqueda secuencial es O(n).
Comparación de la búsqueda binaria y secuencial
Búsqueda Secuencial: Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.
Búsqueda Binaria: El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.
Búsqueda Binaria: En cada comparación se puede eliminar la mitad de los elementos del array.
Primera comparación: array de n elementos
Segunda comparación: array de n/2 elementos
Tercera comparación: array de n/4 elementos
Cuarta comparación: array de n/8 elementos
C-ésima comparación: array de n/2C elementos
El método de shell es una versión mejorada del método de inserción directa. Este método también se conoce con el nombre de inserción con incrementos decrecientes.
ResponderEliminarEn el método de ordenación por inserción directa cada elemento se compara para su ubicación correcta en el arreglo, con los elementos que se encuentran en la parte izquierda del mismo. Si el elemento a insertar es más pequeño que el grupo de elementos que se encuentran a su izquierda, es necesario efectuar entonces varias comparaciones antes de su ubicación.
El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.
Descripción del algoritmo
El algoritmo fundamental es el siguiente:
Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.
Complejidad de la búsqueda secuencial
La complejidad de la búsqueda secuencial diferencia entre el comportamiento en el caso peor y mejor. El mejor caso se encuentra cuando aparece una coincidencia en el primer elemento de la lista y en ese caso el tiempo de ejecución es O (1). El caso peor se produce cuando el elemento no está en la lista o se encuentra al final de la lista. Esto requiere buscar en todos los n términos, lo que implica una complejidad de O(n).
• HeapSort :
- Este algoritmo no es estable, no mantiene el orden relativo inicial porque elementos iguales pueden terminar en distintos niveles del heap.
- Vemos claramente en el código que no requiere memoria adicional para ordenar ya que solo ocupa 1 o 2 variables temporales para hacer los “intercambie” o “exchange”.
- Funciona también claramente a base de comparación, Heapify ordena comparando al Padre con sus 2 hijos para luego ver si los cambia o no.
Además tenemos que el tiempo de ejecución de HEAPIFY para un heap de n nodos es O(log n).
Y además tenemos un FOR dentro de HeapSort, lo que nos dice que HEAPIFY se ejecuta N-1 veces.
- Los Casos Medio y Mejor son también O( ) ya que igual entran al Build-Heap y al FOR, y en Heapify su tiempo de ejecución sigue teniendo una complejidad de O(log n).
Complejidad de la búsqueda secuencial
ResponderEliminarLa complejidad de la búsqueda secuencial diferencia entre el comportamiento en el caso peor y mejor. El mejor caso se encuentra cuando aparece una coincidencia en el primer elemento de la lista y en ese caso el tiempo de ejecución es O (1). El caso peor se produce cuando el elemento no está en la lista o se encuentra al final de la lista. Esto requiere buscar en todos los n términos, lo que implica una complejidad de O(n).
El caso medio requiere un poco de razonamiento probabilista. Para el caso de una lista aleatoria es probable que una coincidencia ocurra en cualquier posición. Después de la ejecución de un número grande de búsquedas, la posición media para una coincidencia es el elemento central n/2. El elemento central ocurre después de n/2 comparaciones, que define el coste esperado de la búsqueda. Por esta razón, se dice que la prestación media de la búsqueda secuencial es O(n).
Comparación de la búsqueda binaria y secuencial
Búsqueda Secuencial: Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.
Búsqueda Binaria: El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.
Búsqueda Binaria: En cada comparación se puede eliminar la mitad de los elementos del array.
Primera comparación: array de n elementos
Segunda comparación: array de n/2 elementos
Tercera comparación: array de n/4 elementos
Cuarta comparación: array de n/8 elementos
C-ésima comparación: array de n/2C elementos