Discretas 1

1. Qu es un algoritmo?
R= Un algoritmo es una serie de pasos para dar solucin o resolver un

problema planteado.
2. Describa las siguientes propiedades que por lo general tiene un algoritmo:
Entrada= lectura de datos dada por el usuario.
Salida= Resultado obtenido de las operaciones realizadas en el
algoritmo.
Precisin=pasos bien definidos para resolver el problema planteado.
Determinismo=Resultados parciales antes de concluir el proceso de
resolucin del problema.
Carcter finito= El ciclo de ejecucin debe ser repetitivo pero debe
terminar en algn momento.
Correccin= Obtener al final un resultado verdadero; es decir ; que la
respuesta obtenida cumpla satisfactoriamente.
Generalidad=Las entradas dadas se deben procesar por el algoritmo
para obtener los resultados deseados.
3. Qu es el seguimiento (o rastreo) de un algoritmo?
R=Es la prueba de escritorio, se realiza para detectar si existen errores
en los pasos establecidos.
4. Cules son las ventajas del seudocdigo sobre el texto comn a escribir un
algoritmo?
R=Para el entendimiento general del procedimiento pues el
pseudocdigo es preciso, estructurado y universal.
5. Cmo se relacionan los algoritmos con las funciones del pseudocdigo?
R=Estructura los pasos en un orden entendible sin establecer necesariamente
el cdigo real.
EJERCICIOS.
1. Consulte en el directorio telefnico las instrucciones para llamar de larga
distancia. Qu propiedades de un algoritmo (entrada, salida, precisin,
determinismo, carcter finito, correccin, generalidad)estn presentes? Qu
propiedades faltan:
R= entrada de datos con los nmeros de telfono, salida deseada al
escuchar el tono de llamada y la llamada entrante, precisin al digitar
los nmeros en el momento que se nos piden,carcter finito en cuanto
terminamos la conversacin o entra el tono termina el procedimiento,
generalidad solo para un proceso especifico.
2. La conjetura de Goldbach establece que todo nmero par mayor que 2 es la
suma de dos nmeros primos. El siguiente es un algoritmo propuesto para
verificar si la conjetura de Goldbach es verdadera:
a) Sea n = 4.
b) Si n no es la suma de dos primos, la salida es no y se detiene.
c) De otra manera, se aumenta n en 2 y se sigue al paso 2.
d) La salida es s y se detiene.
Qu propiedades de un algoritmo (entrada, salida, precisin,

determinismo, carcter finito, correccin, generalidad) tiene este
algoritmo propuesto? Depende alguna de ellas de la verdad de la
conjetura de Goldbach (que todava no resuelven los matemticos)?
R=Entrada de datos al incrementar el numero inicial de 2 en 2, salida
no tiene pues no se almacena en algn punto, no tiene precisin
pues no necesariamente se cumple el postulado al faltar un punto
donde se identifique si es primo o no lo es, determinismo si tiene en
los valores intermedios obtenidos, carcter finito no cuenta pues la
serie numrica es infinita.
3. Escriba un algoritmo que encuentre el elemento menor entre a, b y c.
R=
min(a,b,c){
Pequeo=a
Si (b<pequeo)
Pequeo=b
Si (c<pequeo)
Pequeo=b
Regresa pequeo
}
4. Escriba un algoritmo que encuentre el segundo elemento ms pequeo entre
a, b y c. Suponga que los valores de a, b y c son diferentes.
R=segundo_pequeo(a,b,c){
X=a, Y=B, Z=C
Si (X>Y){
Temp=X
Y=Temp
}
Si (Y>Z)
{ Temp=Y
Y=Z
Z=Temp
}
Si (X>Y)
{ Temp=X
X=Y
Y=Temp
}
Regresa Y
}
5. Escriba un algoritmo que regrese el valor ms pequeo en la sucesin
s1, . . . , sn.
menorSucesion(S,s,n,Peque)
{ peque=S
para s=1 hasta s=n
{
If (Peque>Ss)
{ Peque=Ss
}
}regresa Peque
}
6. Escriba un algoritmo que regrese el valor ms grande y el segundo elemento
ms grande en la sucesin s1, . . . , sn. Suponga que n > 1 y que los valores
de la sucesin son diferentes.
Encuentra_GRANDE_y_segundoGRANDE(s,n,grande,segundo_grande){
if(s1<s2){ grande=s2 segundo_grande=s1
}
Else
{
grande=s1
Segundo_grande=s2
}
For i=3 to n
If(si>Segundo_grande)
If (si>grande)
segundo_grande=grande
grande = si
else
segundo_grande=si
}
7. Escriba un algoritmo que regrese el valor ms pequeo y el segundo
elemento ms pequeo en la sucesin s1, . . . , sn. Suponga que n > 1
y que los valores de la sucesin son diferentes.
Encuentra_MENOR_y_segundoMENOR(s,n,min,segundo_min){
if(s1<s2){ min=s2 segundo_min=s1
}
Else
{
min=s1
Segundo_min=s2
}
For i=3 to n
If(si>Segundo_min)
If (si>grande)
segundo_min=min
min = si
else
segundo_min=si
}
8. Escriba un algoritmo cuya salida sea el valor menor y mayor en la
sucesin s1, . . . , sn.
MAYOR_MENOR(min,max,n,s)
min=s1 max=s1
for i=2 to n{ if
(min >si)
min=si
if (max<si)
max=si
}
Return max,min
}
9. Escriba un algoritmo que regrese el ndice de la primera ocurrencia del
elemento ms grande en la sucesin s, . . . , sn. Ejemplo: Si la sucesin
es : 6.2 8.9 4.2 8.9, el algoritmo regresa el valor 2.
encontrar_grande_elemento(s,n,grande,ndice_grande){
grande=s1 ndice_grande=1
For i =2 to n
If (si>grande)
{ grande=si
indice_grande=i
}
Return ndice_grande
}
10.Escriba un algoritmo que regrese el ndice de la ltima ocurrencia del
elemento ms grande en la sucesin s1, . . . , sn. Ejemplo: Si la
sucesin es: 6.2 8.9 4.2 8.9, el algoritmo regresa el valor 4.
encuentre_elemento(s,n){
grande=s1
ndice_grande=1 for i =2
to n if (si >grande){
grande=si
indice_grande=i }
Return ndice_grande
}
11.Escriba un algoritmo que produzca la suma de la sucesin de nmeros
s1, . . . , sn.
suma_sucesion(s,n,suma)
{ suma=0;
for i =1 to n
suma=si+suma
return suma
}
12.Escriba un algoritmo que regrese el ndice del primer elemento que es
menor que su predecesor en la sucesin s1, . . . , sn. Si s est en orden
no decreciente, el algoritmo regresa el valor 0. Ejemplo: Si la sucesin
es AMY BRUNO ELIE DAN ZEKE, el algoritmo proporciona el valor 4.
encontrar_fuera_de_orden(s,n){ for i =2 to n if (si<si-1) return i
return 0
}
13.Escriba un algoritmo que regrese el ndice del primer elemento que es
menor que su predecesor en la sucesin s1, . . . , sn. Si s est en orden
no decreciente, el algoritmo regresa el valor 0. Ejemplo: Si la sucesin
es AMY BRUNO ELIE DAN ZEKE, el algoritmo proporciona el valor 2.
encontrar_fuera_de_orden2(s,n){ for i =2 to n if (s i > si-1) return i
return 0
}
14.Escriba un algoritmo que invierta la sucesin s1, . . . , sn. Ejemplo: Si
la sucesin es
AMY BRUNO ELIE, la sucesin invertida es ELIE
BRUNO AMY.
encontrar_fuera_de_orden2(s,n){
for i =2 to n if (s i > si-1)
return i
return 0
}
15.Escriba un mtodo estndar para sumar dos enteros decimales positivos,
que se ensea en primaria, como un algoritmo. suma(s,t,u,n){ c=0;
for i = 1 to n { obtenga xy sea la representacion decimal de la
suma c+si+ti
(donde la sucesin de sn,sn-1,s1 y tn,tn-1,t1 son la
representacin decimal de los dos nmeros a ser sumados)
ui=y (un+1,un u1 son las salidas)

c=x }
un+1=c
}
16.Escriba un algoritmo que recibe como entrada la matriz A de n n y
produce la transpuesta AT.
Transpuesta_matriz(A,n)
{ for i=1 to n-1 for
j=i+1
to
n
swap(Aij,Aji)
}
17.Escriba un algoritmo que recibe como entrada la matriz de una
relacin R y prueba si R es reflexiva. transpuesta AT.
Transpuesta_matriz(A,n)
{ for i=1 to n-1 for j=i+1
to n swap(Aij,Aji) }
18.Escriba un algoritmo que recibe como entrada la matriz de una relacin

R y prueba si R es simtrica.
Simtrica(A,n){ for i= 1 to
n-1
for j = i +1
to n if(Aij=Aji)
return false
return true
}
relacin R y prueba si R es transitiva. es_transitiva(A,n){
// primero hacer que B=A2
for i=1 to n
for j=1 to n{
Bij=0
for k= 1 to n
Bij= Bij + Aik*Akj

// si la entrada en A2 es no cero , pero la correspondiente entry en A es cero, la
relacin es no transitiva.
for
i=1 to n for j=1 to n {

if
(Bij = 0 ^ Aij ==0)
return false
return true
}
}
R y prueba si R es anti simtrica.
for
i=1 to n for j=1 to n {

(Bij = 0 ^ Aij ==0)
return false
return true
}
}
if

relacin R y prueba si R es una funcin. es_funcion(A,m,n){ for i=1 to
m{
sum=0
for j = 1 to n
sum = sum +Aij
if (sum=1)
return false
}
Return true
}
R y produce como salida la matriz de la relacin inversa R1.
es_funcion(A,m,n)
{ for i=1 to m{
sum=0
for j = 1 to n
sum = sum +Aij
if (sum=1)
return false
}
Return true
}
23.Escriba un algoritmo que recibe como entrada las matrices de las
relaciones R1 y R2 y produce como salida la matriz de la composicin R1
R2.
es_funcion(A,m,n)
{ for i=1 to m{
sum=0
for j = 1 to n
sum = sum +Aij
if (sum=1)
return false
}
Return true
}
24.Escriba un algoritmo cuya entrada sea una sucesin s1, . . . , sn y un
valor x. (Suponga que todos los valores son nmeros reales.) El
algoritmo regresa verdadero si Si + Sj =x , para alguna i j, y falso
de otra manera. Ejemplo: Si la sucesin de entrada es
2, 12, 6, 14 y x = 26, el algoritmo regresa verdadero porque 12 + 14
= 26. Si la sucesin de entrada es 2, 12, 6, 14 y x = 4, el algoritmo
regresa falso porque ningn par de trminos distintos en la sucesin
suma 4.
es_funcion(A,m,n)
{ for i=1 to
m{
sum=0
for j = 1 to n
sum = sum +Aij
if (sum=1)
return false
}
Return true
}

Discretas 1

Cargado por

Copyright:

Formatos disponibles

Discretas 1

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Discretas 1

Cargado por

Copyright:

Formatos disponibles

1. Qu es un algoritmo?

R= Un algoritmo es una serie de pasos para dar solucin o resolver un

Qu propiedades de un algoritmo (entrada, salida, precisin,

ui=y (un+1,un u1 son las salidas)

18.Escriba un algoritmo que recibe como entrada la matriz de una relacin

Bij= Bij + Aik*Akj

i=1 to n for j=1 to n {

i=1 to n for j=1 to n {

21.Escriba un algoritmo que recibe como entrada la matriz de una

También podría gustarte