Ingeniería del software

Enviado por jpgiraldo

Partes: 1, 2

(Una aproximación a la medición de la calidad)

Objetivos

Se diferencien claramente los diferentes aspectos que están vinculados con la calidad del software.
Se entreguen las herramientas teóricas y practicas para realizar una correcta evaluación (medición) y adecuación de un proyecto.

Estrategias metodológicas

Clase magistral, para los temas correspondientes a fundamentación teórica.
Ejercicios desarrollados en clase, para comprensión y aplicación de los temas.
Lecturas de elementos teóricos que permitan la crítica y generen la duda acerca de las formas de evaluación.

Estrategias evaluativas

A través de tareas de aplicación y medición de algoritmos.
Elaboración de casos de medición para un modelo desarrollado.
Aplicación de los aspectos de calidad (ISO), para la dar fiabilidad en el producto terminado.
Consultas de elementos adicionales y algoritmos de alto desempeño para cubrir aspectos necesarios en la calidad del software.

Conceptos básicos.

Sin importar cualquiera que sea el tipo de software a ser desarrollado sea de sistemas (Son programas que sirven a otros programas en el trabajo de desarrollo como compiladores, editores, ..), tiempo real (Software encargado de analizar datos del mundo en forma real tales como análisis de datos, control automatizado, monitoreo de datos), gestión (a esta categoría se incluye el software comercial a nivel empresarial nominas, inventarios), ingeniería y científico (es software que posee un amplio manejo numérico usado en biología, astronomía, CAD, …), empotrado (software que se encuentra residente en memoria, tales como : controles automáticos en los vehículos, sistemas de background, partes del sistema operativo, …), computación personal (software comercial de uso local como procesadores de texto, hojas electrónicas, navegadores web, calendarios, agendas, recetarios, …), inteligencia artificial (software de procesamiento especial sistemas expertos, sistemas basados en el conocimiento, generalmente no usan algoritmos numéricos). Todos los tipos de software mencionados requieren que los analistas, diseñadores y desarrolladores apliquen características y elementos de calidad para que se logren productos a las necesidades del usuario, estas necesidades se comienzan a encontrar un camino de solución a través de la aplicación de elementos de calidad, así se presentan dos de los más valiosos como son la eficiencia y la eficacia.

El uso eficiente y eficaz de la tecnología de los computadores es un objetivo que aún está distante. Para representar lo anterior, sólo basta señalar los reportes de fracasos y dificultades de muchos proyectos en los que se pretende involucrar a la tecnología de los computadores.

La ingeniería del software pretende utilizar los recursos computacionales de tal manera que se produzcan soluciones eficientes y eficaces a los problemas informáticos, el éxito de un proyecto involucra elementos como la planeación, la administración y la utilización de metodologías de desarrollo de software.

A través de la planeación se determinan los recursos necesarios para el desarrollo del proyecto, la factibilidad del mismo y el tiempo estimado de desarrollo; unido a ello con la administración se controla, evalúa y corrige la dirección de acuerdo a las contingencias y demás elementos que se vayan presentando durante el desarrollo; finalmente, a través del uso de una metodología se busca lograr el acople de los participantes y la garantía de una determinada calidad. Debe notarse que las metodologías de desarrollote software sólo constituyen uno de los mecanismos que actualmente se utilizan para alcanzar software de calidad; no debemos dejar de lado aspectos de la dirección de proyectos que también buscan calidad en el proceso de desarrollo y en el producto final.

Considerando que la calidad es un término bastante impreciso se ha decidido establecer este tema como punto de partida. Como complemento se trata el tema del manejo de la complejidad puesto que es un tópico fundamental dentro de una metodología, que es la herramienta fundamental con la que se pretende guiar el proceso de elaboración de un producto software de alta calidad.

Calidad en la ingeniería del software. En una versión sucinta la calidad en la ingeniería del software es un grupo de características que representa la efectividad y la eficiencia de un sistema de información. Es importante enfatizar en dos puntos :

Un software de calidad debe ser eficaz, es decir, que debe realizar las funciones establecidas, debe ser amigable. Un usuario debe utilizar el software porque produce resultados confiables, realiza todas las operaciones que se requieren, ejecuta las operaciones en un tiempo aceptado y es fácilmente usado por el grupo de usuarios a quien este dirigido.
Un software de calidad debe ser eficiente, es decir el costo de su desarrollo tomando todos los recursos y el costo de su operación debe ser tal que las organizaciones involucradas en su desarrollo y uso obtengan el máximo beneficio o por lo menos un beneficio aceptable en un período de tiempo establecido.

Para ilustrar el concepto de calidad de manera más profunda, es necesario considerar algunos aspectos fundamentales que caracterizan al software de calidad como son : solidez, exactitud, completitud, mantenibilidad, reutilizabilidad, claridad en la documentación, entre otros que serán descritos a continuación.

Aspectos básicos de calidad de software.

La descripción que se hace de los factores que influyen en un software de calidad se basan principalmente en las ideas presentadas por Robert Dunn, Philip Crosby y Roger S. Pressman. Sin embargo, también se han tomado algunos aportes de Bertrand Meyer y Mauricio Fernando Alba.

Robert Dunn presenta la calidad en el software tomando dos puntos de vista : la calidad en el proceso de desarrollo y la calidad en el producto final, estos dos grupos principales los agrupa en los siguiente aspectos de calidad : confiabilidad, utilizabilidad, mantenibilidad, y adaptabilidad.

Roger Pressman describe similares factores de calidad agrupados en tres grupos : calidad en operación, calidad en revisión y calidad en transición.

A continuación se presentan los factores de calidad de acuerdo al orden dado por Dunn.

Confiabilidad. Este termino es necesario sea separado en varios elementos que permiten darle al software el matiz de fiable. Sus componente son :

Completitud
Consistencia y precisión
Solidez
Simplicidad
Calidad en los procesos de desarrollo
Seguridad y Verificabilidad, estas dos últimas que se determinan con el sistema en uso.

Usabilidad. Si bien es cierto que la confiabilidad es un factor muy importante en la calidad del software también lo es el hecho de que es necesario considerar otros factores como los que se mencionan en esta sección puesto que de nada sirve un software que funcione correcta y confiablemente si el usuario prefiere no utilizarlo.

Exactitud de los procesos
Claridad y exactitud de la documentación
Completitud
Eficiencia y verificabilidad del software
Claridad y amigabilidad de la interfaz

Mantenibilidad. Este aspecto de calidad involucra los elementos que simplifican la labor de prevención, corrección o ampliación del código del programa. Retomar un código escrito meses antes es un trabajo dispendioso y agobiante, en especial cuando las aplicaciones no cuentan con la característica a la cual aquí se hace referencia. Se pueden considerar como atributos de este aspecto :

Exactitud y claridad en la documentación
Modularidad acoplamiento
Facilidad de lectura
Simplicidad

Portabilidad. Es la capacidad que posee un sistema de información que le permite funcionar en diferentes plataformas ya sean hardware o de software.

A continuación se describen cada uno de los aspectos de calidad mencionados:

Calidad en los procesos de desarrollo. Se resume en la frase "bien planeado y cuidadosamente ejecutado". Este aspecto asegura la confiabilidad, puesto que el plan que se realice para desarrollar el sistema, debe incluir pruebas bien seleccionadas que evalúen la confiabilidad del programa en cualquier situación.

Claridad y amigabilidad de la interfaz. De igual forma la interfaz debe ser clara y agradable al usuario, las interfaces complejas son causa de la no utilización de los sistemas de información.

Claridad y exactitud de la documentación. Hay que anotar que toda aplicación requiere de una documentación suficientemente clara con el fin de que cualquier persona con conocimientos básicos en computación pueda aprender la forma de operación sin que requiera la asesoría de los desarrolladores o conocedores de la herramienta, a menos que se trate de eventualidades donde realmente sea necesario consultar al proveedor.

Completitud o adecuación. Se refiere a que los resultados de operaciones sean acordes al comportamiento del mundo real desde todos los estados y condiciones permitidos por la aplicación, es decir, el programa debe reflejar la realidad. Un programa es inconsistente si presenta respuestas erróneas en algunos casos. Una mala especificación de rangos en un dominio sobre los cuales realizan diferentes operaciones matemáticas puede llevar a que algunos cálculos se realicen dentro de límites inapropiados, obteniéndose resultados erróneos. Otro caso de inconsistencia se presenta cuando ocurren eventos que paran abruptamente la ejecución del programa, sólo un sistema de calidad podrá conservar datos consistentes después de una falla.

Eficiencia y verificabilidad del software. Otro aspecto que no debe pasar por alto es el de la verificablidad, puesto que es imprescindible contar con los requerimientos, y sobretodo en aquellos sistemas donde se obtengan resultados que no sean visibles.

Exactitud de los procesos. Un programa no será utilizado por un usuario si sus resultados no son exactos. Tampoco se puede garantizar el uso de un programa que no presta las utilidades que el usuario requiere, es decir, que sea incompleto. Además, un programa ineficiente que no cumpla con los requerimientos de tiempo, memoria o flexibilidad no podrá satisfacer las expectativas de quienes lo utilizan.

Robustez o solidez. Se refiere a la capacidad del software de defenderse de las acciones anormales que llevan al sistema a un estado no deseado o por lo menos no previsto, causando un comportamiento inesperado, indeseado y posiblemente erróneo. El software de hoy, debe estar en capacidad de analizar los datos que recibe para hacer cumplir requerimientos o condiciones del software y enfrentar de la mejor manera los errores cometidos por un usuario al utilizar la aplicación. Es importante resaltar, que la solidez no siempre es generada por la digitación inapropiada del usuario, sino también por un mal procesamiento o un mal encadenamiento de procesos. El resultado de un proceso, aunque sea correcto, puede estar fuera de los límites permitidos en los parámetros del módulo que lo recibe y si este módulo no controla los parámetros que le entran caerá en un estado inesperado.

Seguridad y auditabilidad. Son importantes, puesto que un usuario no puede confiar en los datos de un sistema que no le ayude a controlar el acceso de personas no autorizadas o a detectar errores de operación en los que se introducen y generan datos erróneos.

Simplicidad. Promueve la utilización de estructuras de fácil manipulación con el fin de evitar que el programador se aleje del problema que desea resolver. Además, se reduce la probabilidad de cometer errores. Así que, no es aconsejable hacer uso de estructuras complejas a menos que se necesite cumplir con requerimientos de vital importancia tales como tiempos máximos de proceso u otros similares.

Calidad de software. Se define la calidad de software como la ausencia de errores de funcionamiento, la adecuación a las necesidades del usuario, y el alcance de un desempeño apropiado (tiempo, volumen, espacio), además del cumplimiento de los estándares. Los objetivos que la calidad persigue son : La aceptación (utilización real por parte del usuario) y la Mantenibilidad (posibilidad y facilidad de corrección, ajuste y modificación durante largo tiempo). Para alcanzar estos objetivos, es necesaria una actitud y compromiso de todo el personal que se encuentre en el desarrollo del proyecto, y en todas y cada una de las etapas (en general, planeación, análisis, diseño, programación, pruebas, mantenimiento) correspondientes al ciclo de vida que se hubiese seleccionado para el proyecto. En forma adicional durante el proceso de aplicación de las metodologías se requiere tener en cuenta :

Realización de Revisiones Técnicas Formales durante cada etapa.
Realización de pruebas y revisiones por personas "externas" al proyecto.
Elaboración de la adecuada documentación del software, y de los cambios.
Verificación del cumplimiento de los estándares de desarrollo
Medición permanente de la productividad del proceso y de la calidad de los resultados.
Desarrollo y ajustes de modelos estadísticos de calidad y productividad.
Control de la desviación de los promedios de calidad y productividad.

Uno de los elementos que permite dar garantía acerca de la calidad del software es la aplicación de métricas, estas son medidas estadísticas aplicadas a un software determinado, garantizando calidad así como lo afirma Pressman: "La garantía de calidad del software, es una "Actividad de protección" que se aplica a lo largo de todo el proceso de ingeniería del software"

Todos los elementos anteriormente enumerados indican herramientas que se deben tener en cuenta al momento de desarrollar un software, agrupando en una definición estos elementos se afirma que : Un software debe estar desarrollado "En concordancia con los requisitos funcionales y de rendimiento explícitamente establecidos, con los estándares de desarrollo explícitamente documentados y con las características implícitas que se espera de todo software" , si cumple los aspectos señalados se puede afirmar que se posee un software de calidad. Teniendo en cuenta esto, se puede afirmar

Los requisitos del software son la base de las medidas de la calidad.
Los estándares especificados definen un conjunto de criterios de desarrollo que guían la forma en que se aplica la ingeniería del software, Si no se distinguen esos criterios no habrá calidad del software.
Existe un conjunto de requisitos implícitos que a menudo no se mencionan, si no se alcanzan estos requerimientos podría la calidad quedar en entredicho. Los requisitos son llamados por los usuarios finales llaman elementos obvios, los cuales el diseñador no debe dejar pasar sin explicación.

Para estar seguros de las anteriores afirmaciones se tienen en cuenta factores que se pueden medir estos son llamados factores de calidad. Los factores de calidad se agrupan en dos bloque así :

Factores que pueden ser medidos directamente (errores, líneas, tiempo, …)
Factores que sólo pueden ser medidos indirectamente (facilidad de uso, mantenimiento, …)

Otro autor que contribuye con el aspecto de las medidas en el software es McCall, él y sus colegas proponen tres factores de calidad y sus partes así :

Factor 1. Características operativas, relacionadas con las operaciones del producto.

Corrección
Fiabilidad
Eficiencia
Integridad
Facilidad de uso

Factor 2. Capacidad de soportar cambios, relacionado con la revisión del producto.

Facilidad de mantenimiento
Flexibilidad
Facilidad de prueba

Factor 3. Adaptabilidad, relacionado con la transición del producto.

Portabilidad
Reusabilidad – Reutilizabilidad
Interoperabilidad

McCall propone para las métricas asociadas al software un nivel de evaluación entro cero (0) y diez (10) como medidas. Además, aclara que las métricas y la evaluación son procesos subjetivos. Los elementos que se pueden tener en cuenta para la evaluación son :

Autodocumentación – Que el archivo ejecutable entregue documentación significativa.
Completitud – Se han implementado las funciones requeridas.
Concisión – Compacto en líneas de código.
Consistencia – Uso de métodos de diseño, técnicas de documentación a través del desarrollo.
Eficiencia en la ejecución – Medida del tiempo de ejecución.
Estandarización de los datos – Manejar tipos abstractos de datos (TAD) a través del programa.
Exactitud – Preciso en cálculos y control.
Facilidad de auditoria – Comprobar la conformidad con los estándares.
Facilidad de expansión– Facilidad de ampliar diseños arquitectónicos, de datos, o procedimiento.
Facilidad de operación –
Facilidad de traza – Realizar ingeniería en reversa. Que tan fácil es devolverme a los requerimientos.
Formación – Debe poseer un buen sistema de ayudas para que los nuevos usuarios apliquen el sistema.
Generalidad – Amplitud de aplicación potencial de los componentes del programa. Es decir, los módulos creados pueden ser útiles en otras aplicaciones del mismo tipo, o aplicaciones que manejen tipos de datos semejantes.
Independencia del hardware – Que los diseños sean independientes de la máquina o máquinas que se tienen destinadas para el software. A calidad. pero no a implantación
Independencia del sistema software – Hasta donde el programa es independiente de la plataforma de desarrollo.
Instrumentación – En que grado el programa muestra funcionamiento e identifica errores,
Modularidad – División del programa en componentes funcionales. Acoplamiento, cohesión.
Normalización de las comunicaciones – Que tanto se usan estándares, interfaces, protocolos, entre otros elementos que pueden ser de importancia.
Seguridad –
Simplicidad – El sistema de información debe ser fácil de entender.
Tolerancia de errores– Que tanto se pierde al ocurrir un daño grave.
Metodologías de desarrollo. Una metodología de desarrollo de software permite producir organizada y económicamente software de alta calidad, siguiendo una serie de pasos donde se utilizan un conjunto de técnicas, notación y normas de documentación preestablecidas.

El análisis y diseño, como elementos esenciales del proceso de desarrollo, obligan a tener especial atención y por tal motivo se han ido creando metodologías que sirven de base para tomar las decisiones que afectarán el producto final. Con el advenimiento de la disciplina de la ingeniería del software se inicial el proceso de desarrollo de metodologías las primeras de ellas fueron las estructuradas, y en forma posterior aparecen las metodologías orientadas a objetos, siendo estas últimas las mas difundidas actualmente en el medio.

Una metodología de desarrollo de software presenta una forma de modelar el mundo real con el fin de llevarlo al dominio del computador, a través del modelo se puede obtener una visión global del sistema, para facilitar la especificación de los requerimientos, las restricciones del sistema, y de la solución del problema.

Mostow sugiere que el propósito de diseñar es construir un sistema que :

Satisfaga una especificación funcional dada.
Este de acuerdo con las limitaciones del mundo real.
Encuentre los requerimientos implícitos o explícitos sobre la ejecución y uso de recursos.
Satisfaga las restricciones sobre el proceso de desarrollo mismo, tales como tiempo, costo de las herramientas disponibles para hacer el diseño, entre otras.

La construcción de modelos en ingeniería tienen gran aceptación por tomar los conceptos de descomposición, abstracción y jerarquía. Cada modelo en un diseño describe un aspecto específico del sistema que esta en consideración.

"Un método de diseño de renombre está basado en fundamentos teóricos sólidos y ofrece grados de libertad para innovación artística"

Como elementos principales de los métodos se han considerado : la notación (Es el lenguaje para expresar las especificaciones del sistema) y el proceso (Son los pasos generales para la construcción del sistema). Estos pasos son complementados con procedimientos específicos o técnicas que sirven para construir modelos. Entre estas técnicas se pueden mencionar : Modelo entidad-relación, diagramas de flujos de datos, modelos objetos, diagramas de actores, diagramas de transición, entre otros.

Un tercer elemento que se relaciona con los anteriores y día a día es más esencial agrupa a las herramientas (CASE) o instrumentos que eliminan el tedio de construir modelos. Gracias a ellos se obliga a hacer uso de las reglas de los modelos y por ende los errores y las inconsistencias pueden ser expuestos para que sean eliminados por el diseñador.

El enfoque estructurado. Presentar las características de las metodologías orientadas a objetos.

El enfoque orientado a objetos. El paradigma orientado a objetos se caracteriza por la solución de problemas a través del estudio y representación de los objetos del mundo real y las interacciones entre sí.

Yourdon representa la orientación a objetos en la ecuación :

Orientado_Objeto = Clases y objetos + Herencia + Comunicación con mensajes cohesión

Coad y Yourdon consideran las siguientes razones para hacer uso del enfoque orientado a objetos :

Toda la información está basada en los datos y estos conforman la parte más estable de un sistema y por ende le dan estabilidad a la aplicación. Las estructuras se especifican de forma que sean flexibles al cambio, esto implica que las modificaciones a los requerimientos no afectan la estabilidad del sistema ya que no provocan alteraciones traumáticas a menos que se trate de cambios significativos.
Los resultados del análisis,(modelo de análisis RIP) diseño e implementación son reutilizables. La representación del mundo real a través del Análisis Orientado a Objetos (AOO) lleva a una modularidad formada por paquetes de clases y objetos. Estos a su vez conforman subsistemas reutilizables en futuros proyectos. Es de anotar que la Modularidad aquí llega más allá de dividir un programa en funciones como se hace en las metodologías estructuradas.
Mejora el análisis y la interacción expertos-dominio "Casos de Uso" del problema. A través del enfoque orientado a objetos se construye un modelo desde la visión del experto que representa el problema en forma más natural, haciendo prevalecer el pensamiento de los usuarios directos del futuro sistema.
La manera como se agrupan los elementos del mundo con sus operaciones como un todo, incrementa la consistencia entre el modelo y el mundo real.
Representa explícitamente los elementos comunes. AOO utiliza la herencia para identificar y capitalizar los atributos y servicios comunes.
Promociona la utilizabilidad usabilidad.

Otras razones del uso del enfoque orientado a objetos son las siguientes :

- De acuerdo con la experiencia de algunos, se ha notado que se produce menos código y por ende es más fácil de mantener favoreciendo la relación costo beneficio.
- Muchas de las personas que no trabajan con computador encuentran el enfoque orientado a objetos muy natural.
Ejercicio practico 1. Indicar que características básicas de las métricas apoyan a los aspectos de calidad de software. (Justificar) Trabajo a ser desarrollado en grupos preferiblemente en clase para que se desarrolle discusión abierta, cada grupo tomará uno o varios aspectos dependiendo de la cantidad de grupos.
Ejercicio practico 2. Con base en las metodologías descritas, indicar como la metodología en sus procesos y pasos apoya los factores de calidad, justifique. Trabajo a ser desarrollado en grupos. Al igual que el anterior los aspectos de calidad deben ser entregados a los grupos de trabajo.

Medidas de los algoritmos.

En los procesos de calidad de software uno de los elementos que más puede inquietar a los diseñadores es el adecuado manejo de los algoritmos y su eficiencia, para que el resultado sea óptimo al momento de ser implementado, para eliminar esta preocupación por parte del diseñador aparece en la disciplina de la ingeniería del software un tema que es el análisis de algoritmos, en este tema aparecen elementos como la complejidad computacional, verificación de programas, entre otros.

Complejidad computacional – La complejidad computacional estudia los costos de cómputo necesarios para resolver un problema; entendiéndose por costos los recursos de espacio de almacenamiento y de, principalmente, tiempo de cómputo. La complejidad temporal tiene que ver con el tiempo que tarda un programa para ejecutarse, la complejidad espacial estudia la cantidad de almacenamiento que es necesario para una operación. Al analizar la complejidad de un algoritmo, el tiempo está expresado en términos de pasos de computación elementales (asignaciones, comparaciones, operaciones matemáticas básicas, etc), por ejemplo, una operación de asignación ocupa una unidad de tiempo para ejecutarse, un ciclo ocupa el número de iteraciones en que está definido, etc.

Para cualquier tiempo de ejecución que se desea determinar siempre se asumirá el peor de los casos.

Sea el siguiente ejemplo :

(1) suma = 0

(2) for (i=1; i<= n; i++)

(3) suma += i;

La instrucción (1) ocupa una unidad de tiempo.

La instrucción (3) ocupa dos unidades de tiempo, una para la suma y otra para la asignación, y es ejecutada N veces, por lo que ocupa 2N unidades de tiempo.

La instrucción (2) tiene involucrada una asignación que utiliza una unidad de tiempo, N+1 comparaciones y N incrementos, por lo que ocupa 2N+2 unidades de tiempo.

El tiempo total del algoritmo es T(N) = 1+2N+2+2N, esto es : T(N) = 4N + 3

De otra forma se podría ver como la existencia de tiempos para cada una de las posibles operaciones individuales, así : Ta – Tiempo de asignación, Tc – Tiempo de comparación, To – Tiempo de operación, Ti – Tiempo de incremento.

La instrucción (1) posee Ta

La instrucción (3) posee un Ta y un To.

La instrucción (2) posee un Ta para i=1, Tc para i<=n, Ti para i++

Con base en estas valoraciones los tiempos serían así para el ciclo for las instrucciones internas se hacen la cantidad de veces que indique el ciclo, la instrucción interna tarda (Ta + To) el ciclo se realiza n-veces, lo cual indica un tiempo de n(Ta+To), ahora el ciclo realiza n veces el incremento de i++ es decir n(Ti) y las comparaciones son n+1 ya que el ciclo debe llegar hasta n+1 para que el ciclo pueda terminar, es por ello que es (n+1)Tc, y falta la asignación de i=1 es decir Ta, el tiempo total del algoritmo es : T(n) = n(Ta + To) + n(Ti) + (n+1)Tc + Ta + Ta, el total eliminando las agrupaciones es : n(Ta) + n(To) + n(Ti) + n(Tc) + Tc + Ta + Ta, factorizando n(Ta + To + Ti + Tc) + Tc + Ta + Ta, se aplica que cada uno de los tipos de operación tarda una unidad de tiempo, esta difiere en cada computador, por ello se toma general para este caso lo asumimos con valor 1, por ello sería el total final n(4) + 3, es decir el tiempo

T(n) = 4n + 3.

La pretensión de la segunda forma de evaluación es que se determine cuanto tiempo se tarda en cada uno de los tipos de operación, en caso de ser necesario.

Orden de un algoritmo – La función que define el tiempo de ejecución de un programa proporciona información interesante para clasificar los diferentes algoritmos que existen para resolver problemas. Con esta función es posible comparar el desempeño de diferentes algoritmos desarrollados para un problema en particular.

Para simplificar el estudio de la complejidad, se han adoptado ciertas convenciones en su notación, una de ellas es el concepto de orden, que indica, de forma simple, el grado de complejidad de un algoritmo sin considerar por completo la función de tiempo.

Sea el siguiente algoritmo :

for (i=1; i<n; i++)

for (j=i+1; j<=n; j++)

if (vec[i] <= vec[j])

{

temp = vec[i];

vec[i] = vec[j];

vec[j] = temp;

}

El anterior algoritmo lo pueden reconocer como el ordenamiento de burbuja, el cual posee una función de tiempo de n(n-1)/2, la demostración de este valor se deja como ejercicio para el lector, esto es igual a (n2 – n)/2, y se dice que es de orden n2 , o simplemente O(n2). Para determinar el orden un algoritmo, a partir de su función de tiempo, se eliminan todos los términos excepto el de mayor grado y se eliminan todos los coeficientes del término mayor.

Existen algunas reglas que son útiles para determinar el orden de un algoritmo:

Regla 1 (Ciclos FOR) : El tiempo de ejecución de un ciclo FOR es al menos el tiempo de ejecución de las instrucciones dentro de él multiplicado por el número de iteraciones.

Ejemplo : Para orden O(n).

for (i=1; i<=n; i++)

suma += i;

La función de tiempo para el algoritmo es T(N) = 4N+2, ya que ciclo ocupa 2n+2 y la sumas 2n, por lo que tiene un orden O(n).

Regla 2 (Ciclos FOR anidados) : Se analiza desde dentro hacia fuera. El tiempo de una instrucción dentro de un conjunto de ciclos anidados es igual al tiempo de ejecución de las instrucciones internas multiplicado por el producto del tamaño de los ciclos.

Ejemplo : Para orden O(n2)

for (i=1; i<=n; i++)

for (j=1; j<=n; j++)

suma += i*j;

Regla 3 (Condicional) : El tiempo de ejecución nunca es mayor que el tiempo de ejecución de la condicional más el mayor de los tiempos de ejecución de las alternativas.

Ejemplo : Algoritmo es O(n2)

If (i==j)

for (i=1; i<=n; i++)

suma += i;

else

for (i=1; i<=n; i++)

for (j=1; j<=n; j++)

suma += i*j;

Debido a que el tiempo de ejecución de la condición es de orden O(1) más el mayor tiempo de ejecución de las alternativas : cuando se cumple la condición es o(n) y cuando no se cumple es O(n2), por lo cual el orden es O(1) + O(n) + O(n2), pero, como ya se ha dicho, solo se toma el mayor, quedando el orden del programa en O(n2).

A los algoritmos de orden n se les llama de orden lineal, los de n2 de orden cuadrado, etc.

A continuación una gráfica muestra la características de orden de los algoritmos.

Se puede decir que un algoritmo tiene complejidad polinomial, o se ejecuta en tiempo polinomial, si tiene un orden O(nx). Estos algoritmos se dice que son algoritmos eficientes y los problemas que se resuelven con estos algoritmos se dice son problemas tratables.

Un algoritmo tiene complejidad exponencial si la función de tiempo T(n) tiene un orden O(xn). Los problemas que se resuelven usando algoritmos de tiempo exponencial se conocen como problemas intratables y a los algoritmos como algoritmos ineficientes.

Ejemplo : El problema de las Torres de Hanoi tiene complejidad exponencial de orden 2n. El algoritmo es el siguiente :

void Hanoi(int N, int A, int B, int C)

{

if (n==1)

MueveAnillo(A,B);

else{

Hanoi(n-1,A,C,B);

MueveAnillo(A,B);

Hanoi(n-1,C,B,A);

}

Debido a que el algoritmo es recursivo, el tiempo de ejecución puede ser descrito por la función T(n) = 2t(n-1) + constante, al aumentar el tamaño de la entrada, el tiempo se duplica (factor de dos), por lo que se puede deducir que el orden del algoritmo es O(2n).

Matemáticas de los algoritmos. (Para el caso de medición en el peor de los casos y para la media)

Sea M(n) el valor medio del tiempo de ejecución de todas las entradas de tamaño n. Para este caso se define los siguientes elementos :

Dn – conjunto de entradas de tamaño n.

T(i) – número de operaciones básicas correspondientes a la entrada I <- Di

P(n) – Tiempo de ejecución en el peor de los casos

P(n) = Max(T(i), V I є Dn)

M(n) = Media del número de operaciones básicas

En la practica casi siempre es más difícil determinar el tiempo de ejecución promedio que el del peor caso, pues si las p(i) no son iguales, cosa que normalmente ocurre, el análisis se hace intratable en matemáticas, y la noción de entrada "promedio" puede carecer de un significado claro.

Para el caso de la búsqueda secuencial.

i=1

mientras ((i=n) and (A[i] <> x)) haga

i = i + 1

fin mientras

En forma general P(n) es n si se toma como operación la comparación de elementos del arreglo.

Vector A.

I – Entrada iesima

1 n

Con base en la medida del valor medio, se tiene

Sea q la probabilidad de x estar en el vector, significando con la entrada I – iesima que el elemento x ocupa la posición iesima.

Los valores de p(I) son iguales :

q (probabilidad de que el elemento este en la lista) en (i) número de iteraciones realizadas para encontrar (x).

(1-q) (probabilidad de que el elemento no este en la lista) en (n) número de iteraciones posibles en el vector. Este valor de determina por el principio básico de la estadística de un valor máximo (100%) corresponde a uno (1).

Es por ello que aparece la siguiente ecuación : (1-q)*n + q*i, este valor me representa el 100% de efectividad, en el proceso. Luego se aplican los elementos que componen la ecuación de la media y se reemplazan

Factorizando

Asumiendo que q sea 1 el resultado es : M(n) = (n+1)/2

Trabajo practico ( Ejercicio : Medición de los tiempos de asignación, operación, comparación e incremento)

Partes: 1, 2

Página siguiente