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