Módulo 1
ALGORITMOS Y
ESTRUCTURA DE DATOS
PROFESOR: SIRACUSA EMILIANO
MARTÍN
Página Web:
[Link]
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ó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ón
Ejemplo de Diagrama 3
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?
Datos explícitos
Dos trabajos Músico Juan
cada uno Jardinero Jorge
Pintor Javier
Chofer
Ascensor
Peluquero
Jóvenes
Juan Jorge Javier
Chofer
--- --- X
Pintor
X --- ---
Trabajos
Ascensor
--- X ---
Jardinero
--- --- X
Músico
--- X ---
Peluquero
X --- ---
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. Solución
P: Edad de Pedro
J=3(P-10)
Planteo de ecuaciones
P=(J+5)/2
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
ia
Va Hac
N2
N1
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 Solución
C
B
D
E
Juan
Geometría
Geometría: Es una teoría sólida, con leyes y teoremas y
una gran aplicación visual.
Solución
Ejemplo de Geometría
Una 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?
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ón
Lógica
Se 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áticas
Para 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=//N
Representa 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ógicos
Negació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, ^,and
Considerando 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, or
Considerando a ‘a’ y ‘b’ como valores de verdad
a b avb
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.
Ejemplos
1) –(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.
Ejemplos
I. ((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)
Sucesiones
Una 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: Natural Elemento
I. Sucesión de números naturales 1--------- 1
2--------- 2
3--------- 3
(N)=1 2 3 4 5 6 7… 4--------- 4
Natural Elemento
1--------- 2
II. Sucesión de pares 2--------- 4
3--------- 6
(2N)=2 4 6 8 10 12 … 4--------- 8
Natural Elemento
1--------- 1
III. Factorial 2--------- 2
(N!)= 1! 2! 3! … 3--------- 6=3*2*3*1
4--------- 24=4*3*2*1
Sucesiones
Si 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
Sucesiones
Si tenemos la fórmula de la sucesión podemos determinar los
elementos:
Ejemplo: (n+1)*n 2 Natural Elemento
1--------- 2=(1+1)*1 2
2--------- 12=(2+1)*2 2
2 12 24 80 150 252 392 … 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:
Fechas
En 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
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.