Módulo 1

ALGORITMOS Y ESTRUCTURA DE DATOS

PROFESOR: SIRACUSA EMILIANO

MARTÍN

Página Web: www.esiracusa.jimdo.com

Representación de problemas

• Abstracción: es la técnica que permite encontrar un plano más conciso del problema.

El objetivo de la abstracción es construir un modelo de la realidad.

Un modelo es una representación simplificada de la realidad

En el modelo sólo son considerados los elementos relevantes.

Representación del problema. Abstracción

• Transformar el enunciado original en uno tan simple como sea posible.

• Identificar los objetos relevantes y las relaciones entre esos objetos.

• Agrupar los objetos en clases.• Nombrar los objetos o clases según alguna notación.• Definir las operaciones que pueden aplicarse sobre

los objetos• Utilizar una notación más abstracta que la verbal.

Notaciones útiles para representar problemas

Descripción verbal.

Diagramas.

Matemáticas:

Ecuaciones

Grafos

Lógica

Geométrica

Conjunto

Descripción verbal Elaboración de un enunciado equivalente más

simple. Es una ayuda para otras técnicas de representación.

Ejemplo: Algunos meses tienen 31 días, otros solo 30. ¿Cuantos tienen 28 días?

¿Qué significa que un mes tenga 28 días? ¿Cuantos meses cumples con esa condición?

Diagramas

Representación gráfica de los datos, las relaciones entre los datos y de las inferencias que se realicen.

Es de ayuda en la fase inicial de representación y puede ser complemento de otras técnicas.

También puede direccionarnos a elegir otra representación.

Ejemplo de Diagrama 1

Un hombre y una mujer caminan juntos. En el momento inicial sus pies derechos están apoyados en el suelo. El hombre da dos pasos por cada 3 de la mujer. Cuántos pasos debe dar cada uno antes que los pies izquierdos de ambos pisen el suelo al mismo tiempo. SoluciónSolución

Ejemplo de Diagrama 2

Un gato se cayo a un pozo de siete metros de profundidad. Si sube tres metros por día y se cae un metro durante la noche. ¿Cuántos días tarda en llegar a la superficie?

SoluciónSolución

Tres hombres tienen tres trabajos cada uno. El chofer tiene problemas con el músico por su pelo largo. El músico y el jardinero acostumbran a ir de pesca con Juan. El pintor le compro una botella de ginebra al jardinero. El chofer corteja a la hermana del pintor. Jorge debe 100 pesos al pintor. Javier venció a Jorge y al pintor jugando a las cartas. Uno de ellos es peluquero, y no hay dos que tengan el mismo trabajo. ¿Que hace cada uno?

Ejemplo de Diagrama 3

Datos explícitos

Dos trabajos cada uno

MúsicoJardineroPintorChoferAscensorPeluquero

JuanJorge Javier

Representación Matemática

Se logra independencia del enunciado original.

Es una herramienta basada en una sólida teoría.

Ecuaciones: Se basa en una serie de incógnitas que representan valores (operandos) y de una serie de símbolos que establecen relaciones entre las incógnitas (Operadores)

Ecuaciones Ejemplo: Juan es ahora tres veces más viejo de lo

que era Pedro hace 10 años y pedro tiene ahora la mitad de la edad que tendrá Juan dentro de 5 años. ¿Cuanto mas viejo es Juan que pedro?

J: Edad de Juan.

P: Edad de pedro

J=3(P-10)

Planteo de ecuaciones P=(J+5)/2

SoluciónSolución

Grafos

Los grafos son representaciones pictóricas que consisten en una serie de puntos o nodos y una serie de arcos que vinculan los nodos. Los arcos pueden estar etiquetados y dirigidos de manera de saber como pasar de un nodo a otro

N2

N1

Va Hacia

Ejemplo de Grafo:Tres parejas vienen caminando desde tres direcciones distintas y se encuentran en una esquina. Comienzan a saludarse y en determinado momento uno de los integrantes del grupo, juan, suspende los saludos y pregunta a cada uno de los demás a cuantos saludo hasta el momento. Todos contestaron un número distinto.¿ A cuántos amigos saludó Juan hasta ese momento?

A

B

C

D

E

Juan

SoluciónSolución

Geometría

Geometría: Es una teoría sólida, con leyes y teoremas y una gran aplicación visual.

Ejemplo de GeometríaUna cabra se encuentra atada con un lazo de 6m de largo al vértice exterior de un corral rectangular de 5m largo por 4m ancho. ¿Qué superficie del terreno está al alcance de la cabra?

SoluciónSolución

Conjuntos

Un conjunto ofrece una representación por medio de diagramas de Vehn para problemas. Sabemos que un conjuntos es una colección de elementos distintos entre sí. Y que sobre los conjuntos se pueden aplicar operaciones como la unión, intersección, diferencia, etc.

Ejemplo de Conjunto

Se desea saber la cantidad de alumnos que estudian solo Ingles. Nueve estudian ingles y castellano, 5 estudian castellano y francés, 11 estudian francés e ingles y 5 tres idiomas. Ninguno estudia solamente castellano y uno solamente francés. Hay un total de 35 alumnos.

SoluciónSolución

LógicaSe Establecen proposiciones cuyo significado admite dos valores posibles, verdadero o falso. Y algunos conectivos como y, o, no, si->entonces, etc.

Estas proposiciones pueden ser simples o compuestas.

A partir de valores de verdad de las preposiciones y de las operaciones que se realicen con ellas se obtienen los valores de verdad de las proposiciones compuestas.

Ejemplo de Lógica

P1: Emiliano es profesor. Verdadero

P2: Emiliano Juega al futbol. Verdadero

P1 y P2 : Emiliano es profesor y Emiliano Juega al futbol Verdadero

(A>0) o (A<-3) es falso sólo si a está en el intervalo

[-3,0]

Operaciones MatemáticasPara resolver los problemas computacionales generalmente se utilizan operaciones matemáticas que distinguiremos en:

Operaciones unitarias: Son aquellas en que el operador afecta solo a un operando.

Tienen la forma general

Operador Operando

- 214

| | -12

Operaciones binarias: Aquellas en que el operador afecta a dos operandos.

Tienen la forma

Operando Operador Operando

25 + 5

Suma, resta, multiplicación, división,

División entera (/e)Operación cuyos componentes deben ser números enteros.

Q=M /e N

15/e3=5 16/e3=5

Resto o Módulo //Operación cuyos componentes deben ser números enteros.

R=//NRepresenta el resto de realizar el cociente entero entre M y N.

15//3=0 16//3=1

Factorial

Operación unitaria cuyo operando debe ser un numero entero mayor o igual que cero.

Representa el producto de todos los números enteros positivos menores e iguales N.

Símbolo: !

1, si N=0

N!

N*(N-1)*(N-2)*,,,*2*1, si N>0

Operadores Lógicos

Los valores lógicos son: Verdadero y falso

Los operadores lógicos fundamentales son:

Símbolo Operador Tipo de operación

Y , ^, and Conjunción Binaria

O, v, or Disyunción Binaria

No, -, not Negación Unitaria

Las operaciones lógicas se pueden definir mediante tablas de verdad que muestran explícitamente el resultado de aplicar el operador correspondiente

Operadores LógicosNegación: No,-Considerando a ‘a’ un valor lógico, la tabla de verdad de la negación es la siguiente

a No a

Verdadero Falso

Falso Verdadero

Conjunción: Y, ^,andConsiderando a ‘a’ y ‘b’ como valores de verdad

a b a ^ b

Verdadero Verdadero Verdadero

Verdadero Falso Falso

Falso Verdadero Falso

Falso Falso Falso

Operadores Lógicos

Disyunción: O, v, orConsiderando a ‘a’ y ‘b’ como valores de verdad

a b a v b

Verdadero Verdadero Verdadero

Verdadero Falso Verdadero

Falso Verdadero Verdadero

Falso Falso Falso

Construir una tabla de verdad considerando ‘a’ y ‘b’ con valores de verdad para las siguientes expresiones lógicas:I.no(a^b)II.(no a) v (no b)Que conclusión puede realizar si compara los resultados de I y II

Operadores Lógicos

La procedencia de los operadores lógicos es como sigue: 1º No 2º Y, O

Una expresión lógica es una combinación de operando y operadores lógicos. Ejemplo: -a v b ^ c

El resultado de evaluar una expresión lógica es un valor lógico.

La evaluación se realiza de izquierda a derecha teniendo en cuenta la procedencia de los operadores

El orden de la evaluación puede ser afectado por la incorporación de paréntesis, corchetes y llaves.Ejemplo: (-a)v[(a ^ c)^(a v b)]

Operadores Lógicos

Una expresión lógica es la representación formal de proposiciones que tienen un valor de verdad.Ejemplo:

Messi es jugador de futbol y Alejandro Dolina es cantante.

Se pude representar lógicamente de la siguiente manera:M: Messi es jugador de futbol.A: Alejandro Dolina es cantante.

M^A Como ambas proposiciones son verdaderas la conjunción es verdadera

Expresiones Lógicas

Equivalencia: Dos expresiones lógicas son equivalentes cuando ambas tienen la misma tabla de verdad.Ejemplos1)–(a v b)= (-a)^(-b)2)–(a ^ b)= (-a)v(-b)

Realizar tabla de verdad y comprobar

Compuestas: Son las que combinan expresiones lógicas y aritméticas.EjemplosI.((a + c)<0)v(b>0)II.Un número es múltiplo de 6 cuando es múltiplo de 3 y 2.

(N//2=0)^(N//3=0)

SucesionesUna sucesión es una secuencia de números que cumplen una propiedad determinada. Cada número es un elemento. Cada elemento está relacionado con un número natural.

Ejemplo:I.Sucesión de números naturales

(N)=1 2 3 4 5 6 7…

II. Sucesión de pares(2N)=2 4 6 8 10 12 …

III. Factorial (N!)= 1! 2! 3! …

Natural Elemento

1--------- 1

2--------- 2

3--------- 3

4--------- 4

Natural Elemento

1--------- 2

2--------- 4

3--------- 6

4--------- 8

Natural Elemento

1--------- 1

2--------- 2

3--------- 6=3*2*3*1

4--------- 24=4*3*2*1

SucesionesSi tenemos los elementos podemos determinar la fórmula de la sucesión:

Ejemplo: 1/1 -2/2 3/4 -4/9 5/16 -6/25 7/36

Natural Elemento

1--------- 1/1=1

2--------- -2/2=-1

3--------- 3/4 =3/22

4--------- -4/9=4/32

5--------- 5/16=5/42

6--------- -6/25=6/52

7--------- 7/36=7/62

n--------- (-1n)*n/(n-1) 2

SucesionesSi tenemos la fórmula de la sucesión podemos determinar los elementos:

Ejemplo: (n+1)*n 2

2 12 24 80 150 252 392 …

Natural Elemento

1--------- 2=(1+1)*1 2

2--------- 12=(2+1)*2 2

3--------- 24=(3+1)*3 2

4--------- 80=(4+1)*4 2

5--------- 150=(5+1)*5 2

6--------- 252=(6+1)*6 2

7--------- 392=(7+1)*7 2

n--------- (n+1)*n 2

Serie

Una serie es la suma de los elementos de una sucesión. Como las sucesiones tienen infinitos elementos, las series tienen infinitos términos. Cada término de una serie es un elemento de la sucesión. Ejemplo: La sucesión: 1! 2! 3! 4!... La serie: 1!+2!+3!34!+… El término general de la serie es: n! La forma general de la serie es:

FechasEn nuestros problemas trabajamos con datos que representan fechas.

Una fecha es una terna que está compuesta por día, mes y año.

Un día es un valor natural comprendido entre 1 y 31 dependiendo del mes y el año.Un mes es un valor natural entre 1 y 12 .Un año es un valor entero. Pero trabajaremos con valores naturales.Considerando los meses según la cantidad de días que tenga.

. 31 Enero-1 Marzo-3 Mayo -5 Julio-7 Agosto-8

Octubre-10 Disiembre-12

30 Abril-4 Junio-6 Septiembre-9 Noviembre-11

28 Febrero-2 Si el año no es bisiesto

29 Febrero-2 Si el año no es bisiesto

Fechas

¿Cuándo un año es bisiesto?

Un año es bisiesto cuando su valor es múltiplo de cuatro y no múltiplo de cien o bien cuando es múltiplo de cuatrocientos.

Como una expresión lógica:4^(-100)v400

Como no reconocemos la operación múltiplo, pero si la operación módulo, podemos escribirlo como:(Año//4=0)^(Año//100<>0)v(Año//400=0).

BIBLIOGRAFÍA

López García, Guillermo (ed.) (2005). El ecosistema digital: Modelos de comunicación, nuevos medios y público en Internet. Valencia: Servei de Publicacions de la Universitat de València. Disp.

Snyder, Ilana –compiladora (2004): Alfabetismos digitales. Comunicación,innovación y educación en la era electrónica. Málaga: Aljibe Stallman, Richard M. (2004) Software libre para una sociedad libre. Introducción de Lawrence Lessig.

Curso Nivelación 2011 - Universidad Nacional de Chilecito Lic. en Sistemas - Ing. En Sistemas – Tecnicatura Univ. Desarrollo Aplic. WEB.

Agustin Fonseca- Juegos de mente – Memoria, Cálculo, Memoria, Agilidad Mental. Martín Sierra, Abel Martín Álvarez, Ángel Aguirre Pérez- Aula Matemática digital 2. Ing. Gábor loerines, ing. Francisco Chaves-Micro computación Tomo 2- Nahel

Ediciones. Adrián Paenza- Matemática... ¿Estás Ahí? Adrián Paenza- Matemática... ¿Estás Ahí? Episodio 2 Adrián Paenza- Matemática... ¿Estás Ahí? Episodio 3,14. Moroni Norma-Apunte de R.P.A (2003) –U.N.S.