CPM_Investigacion De Operaciones

Proyecto

A mayo 13, 2012

Integrantes:

Hernández Rivas Sergio Mauricio

Mitchel Alberto Alvarez Alcaraz

Introducción

Una manera de comparar dos algoritmos cualesquiera es mediante la comparación del tiem-po de ejecución. Este depende del tamaño del programa, sus características, la calidad del código generado por el compilador, y sobre todo la complejidad del algoritmo.

Esto se mide de acuerdo a la cantidad de instrucciones ejecutadas como son saltos, llama-das a funciones, etc.

Descripción del Proyecto

De la solución y código fuente correspondiente al proyecto intermedio es necesario el

análisis del código para determinar la función de su complejidad en términos de la

entrada. Después determinar el orden de magnitud de dicho algoritmo en Notacion O.

Código del problema:

/***********************************************************************************************

* Programa que representa el autómata de los vagones que se desplazan de izquierda a derecha cuando presionemos el interruptor 'M' *

* *

* Integrantes: Mitchel Alberto Alvarez *

* Sergio Mauricio Hernández Rivas *

* ********************************************************************************************/

class Vagones {

static private boolean automata(String string) {

int counter = 0;

char state = 'R';

if (string.isEmpty())

return true;

while (counter < string.length()) {

switch (state) {

case 'R':

if (string.charAt(counter) != 'm')

return false;

else

state = 'D';

break;

case 'D':

if (

string.charAt(counter) != 'b' &&

string.charAt(counter) != 'd'

)

return false;

else

state = 'I';

break;

case 'I':

if (

string.charAt(counter) != 'a' &&

string.charAt(counter) != 'c'

)

return false;

else

state = 'R';

break;

}

++counter;

}

if (state == 'R') return true;

else return false;

}

static public void main(String[] args) {

if(automata("mba"))

System.out.println("la cadena es valida");

else System.out.println("La cadena es invalida");

}

}

Función que determina la complejidad del algoritmo

Gráfica de la función

Orden de magnitud y gráfica identificando ‘c’ y ‘n0’

...