Algoritmos - La palabra que los informáticos no quieren

>>> Algoritmos>>> La palabra que los informáticos no quieren que sepas

Name: David DavóDate: 1543679854Mail: david@ddavo.me

[~]$ _ [1/40]

>>> Índice

1. ¿Algo...ritmo?

2. Recursividad

3. Divide et Impera

4. La «vida» universitaria

[~]$ _ [2/40]

>>> Historia de los algortimos I

La palabra «algoritmo» vienedel matemático persa Muḥammadibn Mūsā al-Khwārizmī

(S. VIII-IX)

Escribió el libro al-Kitābal-mukhtaṣar fī ḥisāb al-jabrwal-muqābala

[1. ¿Algo...ritmo?]$ _ [3/40]

>>> Historia de los algortimos I

La palabra «algoritmo» vienedel matemático persa Muḥammadibn Mūsā al-Khwārizmī

(S. VIII-IX)Escribió el libro al-Kitābal-mukhtaṣar fī ḥisāb al-jabrwal-muqābala

[1. ¿Algo...ritmo?]$ _ [3/40]

>>> Historia de los algoritmos II

Campesinos egipciosCampesinos rusos

[1. ¿Algo...ritmo?]$ _ [4/40]

>>> Historia de los algoritmos II

Campesinos egipciosCampesinos rusos

[1. ¿Algo...ritmo?]$ _ [4/40]

>>> Definición de algoritmo

Algoritmo:1. Conjunto ordenado yfinito de operaciones quepermite hallar la soluciónde un problema.

0. Precondición1. Hacer cosas2. Poscondición «{P}C{Q}»

—C.A.R. Hoare

[1. ¿Algo...ritmo?]$ _ [5/40]

0. Precondición

1. Hacer cosas2. Poscondición «{P}C{Q}»

—C.A.R. Hoare

[1. ¿Algo...ritmo?]$ _ [5/40]

0. Precondición1. Hacer cosas

2. Poscondición «{P}C{Q}»

—C.A.R. Hoare

[1. ¿Algo...ritmo?]$ _ [5/40]

0. Precondición1. Hacer cosas2. Poscondición

«{P}C{Q}»

—C.A.R. Hoare

[1. ¿Algo...ritmo?]$ _ [5/40]

0. Precondición1. Hacer cosas2. Poscondición «{P}C{Q}»

—C.A.R. Hoare

[1. ¿Algo...ritmo?]$ _ [5/40]

>>> Ejemplo de algoritmo

Precondición

200 g de espaguetis1 cebollaAceite de olivaSal

[1. ¿Algo...ritmo?]$ _ [6/40]

0. Corta la cebolla y saltéala con un poco de aceite.1. Añade sofrito de tomate y verduras y un poco de

pimienta.2. Comienza a cocinar a fuego lento3. Espera 10 minutos4. Finaliza de cocinar a fuego lento5. Cocer pasta6. Saltear pasta en sartén

[1. ¿Algo...ritmo?]$ _ [7/40]

Poscondición:

Los espaguetis están cocidosEs comestibleEstá rico

[1. ¿Algo...ritmo?]$ _ [8/40]

>>> Rubik

R R L L U U D D

[1. ¿Algo...ritmo?]$ _ [9/40]

>>> Rubik

R R L L U U D D

[1. ¿Algo...ritmo?]$ _ [9/40]

>>> Rubik

R R L L U U D D

[1. ¿Algo...ritmo?]$ _ [9/40]

>>> YAPA: ¿Que es una variable?

x = x+ 3

x ⇐ x+ 3

¡NO ES UNA ECUACIÓN!x = 2; y = 3

z = x + y

x = x + 7

x: 9 y: 3 z: 5

[1. ¿Algo...ritmo?]$ _ [10/40]

x ⇐ x+ 3

¡NO ES UNA ECUACIÓN!

x = 2; y = 3

z = x + y

x = x + 7

x: 9 y: 3 z: 5

[1. ¿Algo...ritmo?]$ _ [10/40]

x ⇐ x+ 3

z = x + y

x = x + 7

x: 9 y: 3 z: 5

[1. ¿Algo...ritmo?]$ _ [10/40]

x ⇐ x+ 3

z = x + y

x = x + 7

x: 9 y: 3 z: 5

[1. ¿Algo...ritmo?]$ _ [10/40]

x ⇐ x+ 3

z = x + y

x = x + 7

x: 9 y: 3 z: 5

[1. ¿Algo...ritmo?]$ _ [10/40]

x ⇐ x+ 3

z = x + y

x = x + 7

x: 9 y: 3 z: 5

[1. ¿Algo...ritmo?]$ _ [10/40]

>>> Potencia

i<b∏i=0

a = a · a · a · ... · a

Precondición:

a ∈ R ∧ b ∈ N

Poscondición:

r = ab

[1. ¿Algo...ritmo?]$ _ [11/40]

>>> Potencia

i<b∏i=0

a = a · a · a · ... · a

Precondición:

a ∈ R ∧ b ∈ N

Poscondición:

r = ab

[1. ¿Algo...ritmo?]$ _ [11/40]

>>> Potencia

i<b∏i=0

a = a · a · a · ... · a

Precondición:

a ∈ R ∧ b ∈ N

Poscondición:

r = ab

[1. ¿Algo...ritmo?]$ _ [11/40]

>>> Potencia

Algoritmo:

i = 0;r = 1;

¿i < b?

i = i + 1;r = r * a;Cést fini

a = 3; b = 4;

i = 0; r = 1;i = 1; r = 3;i = 2; r = 9;i = 3; r = 27;i = 4; r = 81;

[1. ¿Algo...ritmo?]$ _ [12/40]

>>> Potencia

Algoritmo:

i = 0;r = 1;

¿i < b?

a = 3; b = 4;

i = 0; r = 1;

i = 1; r = 3;i = 2; r = 9;i = 3; r = 27;i = 4; r = 81;

[1. ¿Algo...ritmo?]$ _ [12/40]

>>> Potencia

Algoritmo:

i = 0;r = 1;

¿i < b?

a = 3; b = 4;

i = 0; r = 1;i = 1; r = 3;

i = 2; r = 9;i = 3; r = 27;i = 4; r = 81;

[1. ¿Algo...ritmo?]$ _ [12/40]

>>> Potencia

Algoritmo:

i = 0;r = 1;

¿i < b?

a = 3; b = 4;

i = 0; r = 1;i = 1; r = 3;i = 2; r = 9;

i = 3; r = 27;i = 4; r = 81;

[1. ¿Algo...ritmo?]$ _ [12/40]

>>> Potencia

Algoritmo:

i = 0;r = 1;

¿i < b?

a = 3; b = 4;

i = 0; r = 1;i = 1; r = 3;i = 2; r = 9;i = 3; r = 27;

i = 4; r = 81;

[1. ¿Algo...ritmo?]$ _ [12/40]

>>> Potencia

Algoritmo:

i = 0;r = 1;

¿i < b?

a = 3; b = 4;

i = 0; r = 1;i = 1; r = 3;i = 2; r = 9;i = 3; r = 27;i = 4; r = 81;

[1. ¿Algo...ritmo?]$ _ [12/40]

>>> Máximo

Encontrar el máximo:

maxi = 0;i = 0;

¿i < n? SíNo

vi > vmaxiSí No

El máximoes vmaxi

maxi = i

i = i+1

v = {5, 17, 3, 12, 19, 6};n = |v| = 6;

i vi maxi vmaxi

0 5 0 51 17 1 172 3 1 173 12 1 174 19 4 195 6 4 19

[1. ¿Algo...ritmo?]$ _ [13/40]

>>> Definición de recursividad

Para entender la recursividad, primero tienes queentender la recursividad

- Anónimo

DefiniciónDefinir algo usando su propia definición

[2. Recursividad]$ _ [14/40]

>>> Definición de recursividad

Para entender la recursividad, primero tienes queentender la recursividad

- Anónimo

DefiniciónDefinir algo usando su propia definición

>>> Ejemplos matemáticos de recursividad

Fibonacci

f(n) =

{1 1 ≤ n ≤ 2

f(n− 1) + f(n− 2) 2 < nn ∈ N

Factorial

n! = n · (n− 1)!

>>> Ejemplos matemáticos de recursividad

Fibonacci

f(n) =

{1 1 ≤ n ≤ 2

f(n− 1) + f(n− 2) 2 < nn ∈ N

Factorial

n! = n · (n− 1)!

>>> Ejemplos de acrónimos recursivos

GNU's not UnixPHP Hipertext PreprocessorPNG's not GIF

>>> Estructura de un algoritmo recursivo

Uno o varios casos base (solución directa)Uno o varios casos recursivos (usamos el algoritmo)

>>> Potencia

Precondicióna ∈ R ∧ b ∈ N

Poscondiciónr = ab

Caso recursivor = ab = a · ab−1

Caso base¡Nos lo da la propiadefinición de potencia!a0 = 1

Matemáticas

pow(a, b) =

{1 b = 0

a ∗ pow(a, b− 1) eoc

>>> YAPA: La instrucción return

Cuando queremos que un algoritmo devuelva un resultadocomo lo haría una función matemática, usaremos«return» seguido del valor a devolverf(x) = 2x+ 3 ⇒ return 2x+3Al retornar un valor, el algoritmo 'para'

>>> Potencia

Diagrama de flujo

Inicio

¿b = 0?

return 1;return a*pow(a,b-1)

>>> Algoritmo de Euclides

>>> Máximo Común Divisor

Precondición

a, b ∈ N

Poscondición

r = mcd (a, b)

Caso recursivo

mcd (a, b) = mcd (b, a mod b)

Caso base

mcd (a, 0) = a

>>> Máximo Común Divisor

Inicio

return a; return mcd(b, a %b);

>>> Divide et impera

«Divide et impera»- Cayo Julio C#

El emperador Julio CésarRubens

[3. Divide et Impera]$ _ [24/40]

>>> Adivina el número

>>> Potencia otra vez

Precondición

a ∈ R ∧ b ∈ N

Postcondición

r = ab

r = ab/2+b/2 = ab/2 · ab/2

Problema¡Dividir un número impar entre dos deja resto!

b/2 ∈ N ⇔ b es par

>>> Solución al problema anterior

Si b es parr = ab/2 · ab/2

Si b es imparComo b

2 = b−12 ⇒ r = ab/2 · ab/2 · a

>>> Diagrama del problema anterior

Inicio

b=0Sí No

return 1;

r = pow(a,b/2);r = r*r;

¿b par?

r = r*a;

return r;

>>> Búsqueda binaria

PrecondiciónLa lista está ordenada:

∀i∀j(0 ≤ i < j < n ∧ vi < vj)

PoscondiciónRetornamos la posición del elemento que buscamos

EjemploBuscar el 37 en una lista de 16 elementos

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

10 11 16 28 36 37 40 41 44 56 58 64 72 84 95 98

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

10 11 16 28 36 37 40 41 44 56 58 64 72 84 95 98

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

10 11 16 28 36 37 40 41 44 56 58 64 72 84 95 98

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

10 11 16 28 36 37 40 41 44 56 58 64 72 84 95 98

>>> Bachillerato

InvProy α: Un simulador de redes por y para alumnos

[4. La «vida» universitaria]$ _ [31/40]

>>> Universidad

Facultad de Informática

>>> Universidad

Museo de Informática García Santesmases

>>> Universidad: OTEA

Penguin On Tour: Facultad de Físicas

>>> Universidad: OTEA

>>> FDIst

FDIST: FDI Security Team & #HackTheCern

>>> Cryptoparty

CryptoParty Madrid

>>> Cryptoparty

CryptoParty Madrid[4. La «vida» universitaria]$ _ [37/40]

>>> ASCII

>>> Bibliografía recomendada I

Alfredo Deaño.Introducción a la Lógica Formal.Alianza, Madrid, 1983.

Brian Christian & Tom Griffiths.Algorithms to Live By: The Computer Science of HumanDecisions.Henry Holt & Co., 2016.

Marcus du Sautoy, David Briggs.The Secret Rules of Modern Living Algorithms, 2015.BBC Four.

[5. ]$ _ [39/40]

>>> Q&A

1. ¿Algo...ritmo?Historia de los algoritmosDefinición de algoritmoLógica de HoareEjemplos de algoritmo: Potencia y máximo

2. RecursividadDefinición de recursividadEjemplos de recursividadAlgoritmo de Euclides (MCD)

3. Divide et ImperaAdivina el númeroPotencia otra vezBúsqueda binaria

4. La «vida» universitariaEste documento esta realizado bajo licencia Creative Commons “Reconocimiento 4.0Internacional”.

[5. ]$ _ [40/40]

Algoritmos - La palabra que los informáticos no quieren

Documents

Gestión de Recursos Informáticos Unidad Nº 4: Proyectos Informáticos

Marcas que te quieren

PROGRAMACIÓNS POR AVALIACIÓN 2018-19...Realiza operacións numéricas con eficacia, empregando cálculo mental, algoritmos de lapis e papel, calculadora ou programas informáticos,

algoritmos - personales.unican.espersonales.unican.es/corcuerp/Java/Slides/algoritmos.pdf · • Algoritmos alternativos y equivalentes • Programación estructurada ... Algoritmos

MEJORAS EN EFICIENCIA Y EFICACIA...MEJORAS EN EFICIENCIA Y EFICACIA DE ALGORITMOS EVOLUTIVOS PARA APRENDIZAJE SUPERVISADO DEPARTAMENTO DE LENGUAJES Y SISTEMAS INFORMÁTICOS Memoria

QUIEREN CONTINUAR EL SAQUEO

VIRUS INFORMÁTICOS Por Hugo Zumaeta. Virus informáticos Video motivacional

Personas que te quieren

Que quieren los ninos

EPIDAT 4 - SERGAS...epidemiólogos, estatísticos e informáticos de Galicia, OPS, Cuba e Colombia, que seguiu un protocolo de traballo definido para a selección dos algoritmos, a

Algoritmos paralelos básicos Algoritmos paralelos Glen Rodríguez

Las enfermeras quieren asegurar su futuro.. Quieren su plaza

Técnicas de diseño de algoritmos Algoritmos voraces:Algoritmos voraces Algoritmos paralelos:Algoritmos paralelos

Análisis de algoritmos - Complejidad de los Algoritmos

TODOS QUIEREN HABLAR POCOS QUIEREN ESCUCHAR

(³¡No quieren ser menos!)

Lo Que Ellas Quieren

RFID -Cómo quieren etiquetarnos-

Lo Que Quieren Ellas

LENGUAJE DE PROGRAMACION sistema de escritura para la descripción precisa de algoritmos o programas informáticos. sistema de escritura para la descripción