IWI131 Programación


Introducción a la Programación



Departamento de Informática
Universidad Técnica Federico Santa María

Algoritmos

Un algoritmo es una secuencia finita y precisa de pasos para resolver un problema.

Entonces, ¿qué es un problema?

Problemas

Un problema es la necesidad de transformar un estado inicial en un estado final, respetando ciertas restricciones.

Los problemas involucran datos de entrada en el estado inical y la solución contiene datos de salida en el estado final. Además, probablemente involucre otros datos intermedios que son relevantes.

Ejemplos de Problemas

  • Dado un conjunto de números, determinar los números ordenados de menor a mayor
  • Dado un conjunto de ciudades, encontrar el camino más corto que recorre las ciudades.
  • Dado un mensaje email, encontrar la probabilidad de que sea spam
  • ...

El problema de la ambigüedad

Mi madre dice:
''Cariño, anda al súper y me traes una botella de leche, y si tienen huevos, compra seis"

Cuando vuelvo me pregunta
"¿Por qué trajiste seis botellas de leche?"

Respondo
"Porque había huevos"

Comprensión del Problema

Para poder resolver un problema se debe comprenderlo bien, y ser capaces de formalizarlo de alguna manera. De lo contrario, corremos el riesgo de terminar resolviendo el problema equivocado.

Formalización del Problema

En este proceso se debe definir el estado final al que se quiere llegar. Esto se logra pensando cómo se vería una solución.

En esta etapa es importante concentrarse en el qué y no en el cómo.

Volviendo a los algoritmos...
Un algoritmo es una secuencia finita y precisa de pasos para resolver un problema.

Una vez especificado el problema, hay que tratar de resoverlo pero ¿de qué manera se puede expresar la secuencia de instrucciones?

  • Lenguaje natural
  • Pseudocódigo
  • Diagramas de Flujo
  • Lenguajes de Bloques

Problema Ejemplo:

Determine si un número es primo o compuesto.

Definición: un número natural n es primo si tiene solamente como divisores a 1 y a si mismo. En caso contrario es un número compuesto.

Lenguaje natural

Buscar algún valor d que esté entre 2 y n-1 que sea divisor de n.

Si existe por lo menos uno de estos valores, entonces n es compuesto; en caso contrario, es primo.

Pseudocódigo

leer n
es_primo = verdadero
d = 2
mientras d sea menor que n:
    si n es divisible por d:
        es_primo = falso
    d = d + 1
si es_primo es verdadero:
    escribir "n es primo"
si no:
    escribir "n es compuesto"

Diagramas de Flujo

Lenguajes de Bloques

In [14]:
from IPython.display import HTML
HTML('<iframe src="https://trinket.io/embed/blocks/f1d62613e6?hideGeneratedCode=true" width="100%" height="500" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe>')
Out[14]:

Estructura de un algoritmo

Las instrucciones del algoritmo pueden expresarse:

  • Secuencialmente
  • Tomando decisiones
  • En repeticiones o ciclos

Usando un Lenguaje de Bloques

Trinket

Dos bloques de Trinket:

  • move (mover)
  • turn (girar)

Bloque move (mover)

  • Permite mover un cursor tantas unidades como sean indicadas por un valor numérico.
  • Puede mover hacia adelante (move forward) o mover hacia atrás (move backward).

move forward (mover hacia adelante)

In [15]:
HTML('<iframe src="https://trinket.io/embed/blocks/b4a39cddbc?hideGeneratedCode=true" width="100%" height="270" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe>')
Out[15]:

move backward (mover hacia atrás)

In [16]:
HTML('<iframe src="https://trinket.io/embed/blocks/279df10e32?hideGeneratedCode=true" width="100%" height="270" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe>')
Out[16]:

Bloque turn (girar)

  • Permite girar un cursor en tantos grados como sean indicados por un valor numérico.
  • Se puede girar hacia la derecha (turn right by) o en sentido horario.
  • Se puede girar hacia la izquierda (turn left by) o en sentido anti-horario.

turn right by (girar hacia la derecha)

In [17]:
HTML('<iframe src="https://trinket.io/embed/blocks/5cf7060afb?hideGeneratedCode=true" width="100%" height="270" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe>')
Out[17]:

turn left by (girar hacia la izquierda)

In [18]:
HTML('<iframe src="https://trinket.io/embed/blocks/e5b38d7418?hideGeneratedCode=true" width="100%" height="270" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe>')
Out[18]:

Usando un Lenguaje de Bloques

La idea de un leguaje de bloques es poder conectar los bloques para diseñar un algoritmo que resuelva un problema. ¿Qué ocurre en el siguiente ejemplo?

In [19]:
HTML('<iframe src="https://trinket.io/embed/blocks/d798803a77?hideGeneratedCode=true" width="100%" height="270" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe>')
Out[19]:

Ejercicio 1

Diseñar un algoritmo que dibuje un cuadrado.

In [7]:
HTML('<iframe src="https://trinket.io/embed/blocks/9cf6545f91?hideGeneratedCode=true" width="100%" height="400" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe>')
Out[7]:

Ejercicio 2

Diseñar un algoritmo que dibuje otra figura geométrica distinta al cuadrado.

In [8]:
HTML('<iframe src="https://trinket.io/embed/blocks/1a30d7cc2a?hideGeneratedCode=true" width="100%" height="400" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe>')
Out[8]:
In [ ]: