Clase 1

Vista previa del material en texto

Algoritmos y Estructuras de 
Datos
Departamento de Informática
LAS - TUP
Clase 1
Unidad 1: Introducción a la teoría de las estructuras 
discretas
Matemática discreta: definiciones previas. Conjuntos numéricos: operaciones 
fundamentales.
Teoría de números: introducción, divisibilidad, teorema de la división, algoritmo de 
Euclides, máximo común divisor, números primos. Aritmética modular. 
Congruencia. Introducción a la teoría de grupos.
Matemática Discreta
Definición: Es el área de la matemática encargada del estudio de los conjuntos 
discretos finitos o infinitos numerables tales como: los números enteros, la lógica 
proposicional y los grafos.
Son fundamentales para la ciencia de la computación, porque sólo son 
computables las funciones de conjuntos numerables.
Definición - Teorema - Demostraciones
Lógica - Métodos de demostración
Matemáticas Discretas - Edward Scheinerman (Capítulo 1).
Matemáticas Discretas - Richard Johnsonbaugh (Capítulo 1).
Teoría de Números
Es una de las ramas de la matemática discreta que estudia a los números enteros y 
sus propiedades.
Se relaciona con la aritmética, el álgebra y geometría.
Es decir que vamos a trabajar con los números enteros, sus operaciones, usando 
símbolos y tomando medidas.
Divisibilidad - Primos
La teoría de números estudia las propiedades de la divisibilidad de los números 
enteros.
Vamos a establecer conceptos de divisivilidad y a partir de ellos conceptos de primo. 
Dos de los temas más importantes y sobre los que trabajaremos en el TP 1
Cociente exacto
Al dividir un número entero por otro número entero (distinto de 0) produce un 
cociente que puede o no ser entero.
18/3 = 6 cociente exacto
13/3 = 3.3333 cociente no exacto
Se llama Cociente exacto de dos números naturales D dividendo y d≠ 0 divisor, al número 
natural q cuyo producto por el divisor reproduce el dividendo. La operación realizada para 
calcular el cociente exacto, se llama división exacta.
Por lo tanto, la división exacta exige que el dividendo sea múltiplo que el divisor
Múltiplos
Múltiplos
Los productos de un número entero a por 1,2,3,...se denominan múltiplos de a. 
Adicionalmente, se considera al 0 también como múltiplo de a.
b = a * r donde r ∈ Z
b=a b es múltiplo de a
a / b a es un divisor de b - a divide a b - b es divisible por a
Como se denominan a los que son múltiplos de 2? y los que no?
Ejemplos: 4/20 puedo decir que 4 es divisor de 20 y que 20 es múltiplo de 4
5/9 esta bien? No. Entonces 9 no es múltiplo de 5
¿Quiero saber 5 números que sean divisores de 100… 2,4,5,10,20
Propiedades
1) si a/b ⟹ a/b*s
Si a es divisor de b también lo será de cualquier múltiplo de b
b = a* r donde r es un entero
llamamos d a los múltiplos de b, entonces d = b * s donde s es un entero
Si reemplazamos b en d
d = a * r * s podemos decir que a * (r * s) = a
Entonces d es múltiplo de a y a es divisor de d
Propiedades
2) si a/b y a/c ⟹ a/(b+c) y a/(b-c) si b>=c
Si a divide a b y también a c entonces también divide a b+c y a b-c 
b = a * r y c = a * s
Si sumamos y restamos
b+c = a*r + a*s = a (r+s) = a => a / (b+c)
b-c = a*r - a*s = a (r-s) = a => a / (b-c)
Cociente por defecto y cociente por exceso
Definición: Sean D y d dos números naturales y sea q natural tal que se cumpla la 
relacion q x d <=D<= (q+1 ) x d
q es el cociente por defecto y q+1 es el cociente por exceso
Múltiplos de d: 0xd, 1xd, 2xd, …, qxd, (q+1)xd,...
En general D no es múltiplo de d
Existirán consecutivos q x d y (q+1) x d entre los que se encontrará D
 
Cociente por defecto y cociente por exceso
Ejemplo: Sea D = 21 y d=4 entonces 5 x 4 <= 21 <= (5+1) x 4
 
Resto entero por defecto y por exceso
Definición: Sean D y d dos números naturales y sea q natural tal que se cumpla la 
relacion q x d <=D<= (q+1 ) x d
resto entero por defecto = r = D - q x d
resto entero por exceso r’ = (q+1) x d - D = q x d + d - D = D - r + d - D = d - r
Ejemplo: Sea D = 19 y d=2 entonces: resto por defecto = r = 19 - 2 x 9 = 1
 resto por exceso = r’ = (9+1) x 2 - 19 = 1
Coinciden! Otro Ejemplo: D=25 y d=4 
Definición: División Entera
Se denomina división entera entre dos enteros positivos D y d al cálculo aritmético 
de los cocientes y restos enteros.
¿Resto si?
Si D es múltiplo de d:
Si D < d:
Propiedades de la división entera
1) El dividendo es igual a la suma del divisor por el cociente más el resto.
2) La suma de los restos enteros por defecto y por exceso es igual al divisor. 
3) Si el dividendo y divisor se multiplica por un mismo número el cociente no 
varía y el resto resulta multiplicado por ese número.
Propiedades de la división entera
4) Si al dividir D por d, q es el cociente y r es el resto, entonces el cociente entre 
D+h (h natural) y d, será q+q’, siendo q’ el cociente entre (r+h) y d
División Euclídea
Sean D y d dos números enteros, con d ≠ 0. La distancias entre los valores es |d|.
En general D no será múltiplo de d
a) D sea múltiplo de d
D = q x d + r , r = 0 y q ∈ Z
b) D no sea múltiplo de d 
D = q x d + r , 0 < r < |d| y q ∈ Z
Teorema de la división
Sean D, d ∈ N con d > 0 existe un único par de enteros q, r tal que
D = q x d + r con 0 ≤ r < d
Si D y d son dos enteros con d ≠ 0 existe un único par de enteros q y r ∈ Z tales que 
D = q x d + r con 0 ≤ r < |d| 
Teorema de la división
Existencia: 
Basta con tomar un número q entero tal que d x q sea el mayor de los múltiplos de d menor o igual que D, es decir 
tal que q x d ≤D.
Una vez obtenido el cociente q, podemos calcular el resto r =D−q x d
Por otro lado, si q x d ≤D<(q+1) x d
Entonces q x d ≤ D < (q+1) x d 
 q x d − q x d ≤D − q x d < (q+1) x d − q x d
0 ≤ D−q x d < d
0 ≤ r < d
Por lo que existen enteros tales que, D = q x d +r ,con 0 ≤ r < d
Teorema de la división
Unicidad: 
Suponemos que no son únicos. Por lo tanto existen r1, r2, q1 y q2 tal que verifican el teorema.
D = d x q1 + r1 con 0 ≤ r1 < |d|
D = d x q2 + r2 con 0 ≤ r2 < |d| suponemos r2>=r1
Entonces d x q1 +r1 = d x q2 +r2 => d(q1-q2) = r2- r1 => d x |q1−q2|=|r2−r1| (1)
Como 0 ≤ r1,r2 < |d| => 0≤|r2−r1| < |d| 0≤|r2−r1|/|d| < 1 (2)
de (2) r2=r1
reemplazando en (1) q1=q2 
Una vez obtenido el cociente q, podemos calcular el resto r =D−q x d
Por otro lado, si q x d ≤D<(q+1) x d
Entonces q x d ≤ D < (q+1) x d 
 q x d − q x d ≤D − q x d < (q+1) x d − q x d
0 ≤ D−q x d < d
0 ≤ r < d
Por lo que existen enteros tales que, D = q x d +r ,con 0 ≤ r < d
Ejemplos
● D=39 y d=4 tenemos que 39 = 9 x 4 +3 por lo que q=9 y r=3
● D=39 y d=-4 tenemos que 39 = (-9) x (-4) + 3 por lo que q=-9 y r=3
● D=-39 y d=4 tenemos que -39 = -10 x 4 +1 por lo que q=-10 y r=1
● D=-39 y d=-4 tenemos que -39 = 10 x (-4) +1 por lo que q=10 y r=1