PDF de programación - Introducción a la Computación

Introducción a la Computación

Pedro Corcuera

Dpto. Matemática Aplicada y
Ciencias de la Computación
Universidad de Cantabria

[email protected]

Indice

• Computación
• Algoritmos
• Lenguajes de programación
• Técnicas generales de resolución de problemas.

Computación

2

Objetivos

• Introducir los conceptos básicos de

computación, algoritmos, complejidad
computacional, lenguajes de programación y
técnicas generales de resolución de problemas.

Computación

3

Computación

Computación

4

Definición

• Computación: tiene su origen en el vocablo en latín
computatio. Actividad orientada al estudio y análisis
de métodos, técnicas, procesos, desarrollos
(algoritmos) con el fin de almacenar, procesar,
transmitir y hacer uso de información y datos.
• Herramienta: computadora. Formato: digital.
• Nota: Computer science is no more about computers than

astronomy is about telescopes, biology is about microscopes
or chemistry is about beakers and test tubes. Science is not
about tools. It is about how we use them and what we find out
when we do.

Computación

5

Áreas de la Computación

• Arquitectura de computadoras (Computer engineering)
• Ingeniería de programación (Software engineering)
• Ciencias de la computación (Computer science)
• Sistemas de Información (Information systems)
• Tecnologías de la información (Information technology)

Computación

6

Tipos de Computación

• Computación personal

– Escritorio, portátiles, móviles. Se utiliza lenguajes de

programación para el desarrollo de aplicaciones.

– Virtualización. Permite crear, a través de software, de una
versión virtual de algún recurso tecnológico (p.e. sistema
operativo, dispositivo de almacenamiento).

• Computación grid, distribuída, cluster
• Computación en la nube (Cloud Computing):
paradigma que permite ofrecer servicios de
computación a través de una red (mayor uso Internet)

Computación

7

Modelo de computación

• Un modelo de computación define un conjunto de

operaciones permitidas usadas en el cómputo y sus
respectivos costos.

• Permite analizar los recursos de cómputo requeridos:

tiempo de ejecución y espacio de memoria, así
como las limitaciones de algoritmos o computadores.
Ejemplos: máquinas de Turing, funciones recursivas.

• El modelo de computación explica cómo el

comportamiento del sistema entero es el resultado
del comportamiento de cada uno de sus
componentes en la ingeniería dirigida por modelos.

Computación

8

Programas soporte para computación

• Sistemas operativos

– Ordenadores personales: MS Windows, Linux, OS X
– Móviles, tabletas: Android, iOS, Windows Mobile

• Lenguajes de programación

– Compilados: Fortran, C, C++, C#, Visual Basic
– Interpretados: Java (JVM), JavaScript, Python, Matlab,

Mathematica

• Entornos integrados de desarrollo (IDE)

– Microsoft Visual Studio, Xcode, Eclipse, NetBeans

Computación

9

Sistema Operativo

• Un sistema operativo es un programa (o conjunto de
programas) de control que actúa como interfaz entre
el usuario y el ordenador con objeto de facilitar su uso
de manera eficiente.
• Objetivos y funciones:

– Control
– Facilidad
– Eficiencia

• Ejemplo de uso de un SO con comandos:

Disk Operating System

Computación

10

Algoritmos

Computación

11

Definición

• Algoritmo es una secuencia ordenada de

instrucciones que resuelve un problema concreto

• Ejemplos:

– Algoritmo de la media aritmética de N valores.
– Algoritmo para la resolución de una ecuación de segundo

grado.

• Niveles de detalle de los algoritmos:

– Alto nivel: no se dan detalles.
– Bajo nivel: muchos detalles.

Computación

12

Algoritmos en la vida diaria1

• Receta (Algoritmo) de cocina: Camarones con

mayonesa de albahaca.

• Ingredientes - Input (datos de entrada o iniciales)
• Resultado u Output

Computación

13

Algoritmos en la vida diaria2

Ingredientes - Input (datos de entrada o iniciales)

2 tazas de camarones medianos, sin caparazón y desvenados
1 cucharadita de sal

•
Ingredientes (para 4 porciones):
•
2 cucharadas de aceite de oliva
• ½ cucharadita de ajo picado fino
•
•
• ½ cucharadita de pimienta
•
Mayonesa de albahaca:
•
•
•
• ½ limón, el jugo
Guarnición:
•
•
•
•
•

2 aguacates grandes, maduros en rebanadas
1 limón en cuartos
4 hojas de lechuga escarola
8 jitomates cherry partidos por la mitad
Salsa picante al gusto

2 cucharadas de albahaca picada

1 taza de mayonesa baja en grasa
4 cucharadas de albahaca
3 pimientas negras molidas

Computación

14

Algoritmos en la vida diaria3

• Preparación (Algoritmo):
1. En una sartén caliente agrega el aceite de oliva, agrega el

ajo, camarones, sal, pimienta y albahaca. Cocínalos 1
minuto. Apaga el fuego y deja los camarones un minuto
más. Pasa los camarones a un tazón que esté sobre agua
con hielo, déjalos dentro solamente el tiempo necesario
para que se enfríen.

2. En un tazón mezcla todos los ingredientes de la mayonesa

albahaca.

3. Corta los aguacates en rebanadas y acompaña los
camarones. Sirve en un plato decorado con hojas de
lechuga, tomates cherry, limón y si lo deseas agrega un
poco de salsa picante.

Computación

15

Propiedades

Necesarias o básicas:
• Corrección (sin errores).
• Validez (resuelve el problema pedido)
• Precisión (no puede haber ambigüedad).
• Repetitividad (en las mismas condiciones, al ejecutarlo, siempre

se obtiene el mismo resultado).

• Finitud (termina en algún momento). Número finito de órdenes

no implica finitud.

• Eficiencia (lo hace en un tiempo aceptable)
Deseables:
• Generalidad
• Fácil de usar
• Robustez

Computación

16

Algoritmos: Métodos de Representación

• Verbal
• Diagramas de flujo
• Diagramas de Bloques, Cajas o de Nassi-

Shneiderman

• Gráficos
• Pseudocódigo
• Representaciones algebraicas (fórmulas y

expresiones)

Computación

17

Modificación de algoritmos

• Generalización y extensibilidad: proceso de aplicar

el algoritmo a más casos y de incluir más casos
dentro del algoritmo

• Robustez: proceso de hacer un algoritmo mas fiable

o robusto (se recupera de errores), anticipando
errores de entrada u otras dificultades.

Computación

18

Algoritmos alternativos y equivalentes

• Pueden haber muchas formas de llevar a cabo un

algoritmo.

• En esos casos la elección se basa en la eficiencia

(memoria y velocidad).

• El análisis de algoritmos estudia la cantidad de

recursos que demanda la ejecución de un algoritmo.

• Preocupa más el tiempo de ejecución de un

algoritmo: Complejidad del algoritmo

Computación

19

Programación estructurada

• Método para construir algoritmos a partir de un

número pequeño de bloques básicos.

• Formas fundamentales:

– Secuencia: indica secuencia temporal lineal de las

– Selección: especifica una condición que determina la

acciones a realizarse.
A
B

acción a realizarse.
if C
else

D
E

Computación

20

Programación estructurada

– Repetición: indica que una o más acciones deben

repetirse un determinado número de veces.

while G do
H

– Invocación: corresponde al grupo de acciones agrupadas

bajo un nombre.
Calcula_promedio

Computación

21

Pseudocódigo

• Lectura o entrada de datos

Input

• Repetición
while expr
instrucción
endwhile

for i = 1 to m
instrucción
endfor

do
instrucción
while expr

Computación

22

Pseudocódigo

• Decisión
if expr
instrucción
endif

• Escritura o salida de datos

Output

Computación

23

Análisis de Algoritmos: Complejidad

• Para comparar algoritmos se pueden estudiar desde

dos puntos de vista:
– el tiempo que consume un algoritmo para resolver un

problema (complejidad temporal) más interés
– la memoria que necesita el algoritmo (complejidad

espacial).

• Para analizar la complejidad se cuentan los pasos del

algoritmo en función del tamaño de los datos y se
expresa en unidades de tiempo utilizando la notación
asíntotica “O- Grande” (complejidad en el peor caso).

Computación

24

Análisis de Algoritmos: Complejidad

Problema: Buscar el mayor valor en una lista de

números desordenados (array)

Algoritmo: (n = número de elementos)
1
2
3
4
5
6
7

if si > max then
max = si
i = i + 1

max = s1
i = 2
while i <= n

endwhile

Computación

25

Análisis de Algoritmos: Complejidad

Número de operaciones realizadas (unid):
Línea Operaciones Tiempo
1 indexado y asignación 2
2 asignación 1
3 comparación 1
4,5,6 2 indexado, comparación, 6

2 asignación, suma

Tiempo total:
t(n) = 2 + 1 + (n – 1) + 6·(n – 1) = 3 + 7·(n – 1) = 7n – 4

Computación

26

Notación asintótica

• Es útil concentrarse en la tasa de crecimiento del tiempo de

ejecución t como función del tamaño de la entrada n.

• Se usa la notación Big O (O grande cota superior al ritmo de

crecimiento de un algoritmo):
Sean f(n) y g(n) funciones no negativas, f(n) es O(g(n)) si hay
un valor c > 0 y
n0 ≥ 1 tal que f(n) ≤ cg(n) para n ≥ n0

• Se dice que f(n) es de orden g(n)
Ej: 7n – 4 es O(n) si c=7 y n0 = 1

• Generalmente para cualquier polinomio

aknk + ak-1nk-1 +...+ a0 es O(nk)

Computación

27

Eficiencia de un algoritmo

• Proposed Definition of Efficiency: An algorithm is efficient if it
has a polynomial running time. (Kleinberg, Tardos. Algorithm
design).
The running times (rounded up) of different algorithms on inputs of increasing size, for
a processor performing a million high-level instructions per second. In cases where the
running time exceeds 1025 years, we simply record the algorithm as taking a very long time.

•

Computación

28

Desarrollo de algoritmos

• Análisis del problema
– Dominio del problema
– Modelo

• Diseño del algoritmo

– Cuánto tarda en dar una solución? Se puede modificar

– Refinamiento sucesivo
– Top down o botton up
• Análisis del algoritmo

para aumentar la eficiencia?
– Análisis de la Complejida