IP - AED I: Antes de empezar

▶ Sobre la primer semana de clases

Algoritmos y Estructuras de Datos I ▶ Hoy, teórica (en general, los lunes habrá laboratorios)
▶ Miércoles: Libre
▶ Jueves: Teórica
Primer cuatrimestre de 2024
▶ Turnos Comisiones
Departamento de Computación - FCEyN - UBA ▶ Revisen sus mails para ver si los reasignamos de turno o comisión
▶ No se pueden cambiar de comisión
Solucionando problemas con una computadora ▶ Casos particulares, con justificaciones, certificados, etc... avisen
cuanto antes
▶ Por mail: [email protected]
▶ Por campus

1 2

IP - AED I: Antes de empezar IP - AED I: Régimen de aprobación

▶ Con nota numérica
▶ Parcial individual de programación en Haskell en computadora.
▶ Parcial individual de programación en Python en computadora.
▶ Un TP grupal de programación en Haskell + Testing
▶ Todo se aprueba con nota igual o mayor a 6.
▶ Tienen que armar grupos ▶ Criterio de aprobación de la materia
▶ Grupos de 4 personas ▶ TP y notas en parciales mayor o igual que 8, sin recuperatorios:
▶ Todos deben estar en la misma comisión promoción directa, queda el promedio de notas
▶ ¿Cómo consigo compañeros de grupo? ▶ TP y notas en parciales mayor o igual que 8, con algún
▶ Hablando entre ustedes
recuperatorio: final oral (coloquio)
▶ ¿Puede haber grupos de 3? ▶ TP y notas en parciales mayor o igual que 7: final oral (coloquio)
▶ No. Sólo al final se permitirán excepciones en el caso de que no sea ▶ La instancia de Coloquio, sólo es válida hasta las mesas de finales de
posible que todos los grupos sean de 4 integrantes Julio y Agosto 2024. Luego de esas fechas, se deberá dar final escrito
▶ TP y notas en parciales mayor o igual que 6: final escrito
▶ Ambos parciales y el TP tienen instancias de recuperatorio
▶ Los recuperatorios son sólo para quienes no hayan aprobado la
instancia anterior (no se pueden presentar para levantar nota si
aprobaron)
▶ Cada nota, de cada instancia de evaluación, tiene que cumplir el
criterio
▶ Ej: Si el promedio de notas es 7.99: se debe rendir coloquio
3 4
Introducción a la Programación - AED I ¿Qué es una computadora?

Objetivo: Aprender a programar en lenguajes funcionales y en lenguajes

imperativos.

▶ Especificar problemas.
▶ Describirlos de manera tal que podemos construir y probar una
solución
▶ Pensar algoritmos para resolver los problemas.
▶ En esta materia nos concentramos en problemas para tratamiento de
secuencias principalmente.
▶ Empezar a Razonar acerca de estos algoritmos y programas. ▶ Una computadora es una máquina electrónica que procesa datos
▶ Veremos conceptos de testing. automáticamente de acuerdo con un programa almacenado en memoria.
▶ Escribir programas que implementen los algoritmos que pensamos. ▶ Es una máquina electrónica.
▶ Vamos a usar dos lenguajes de programación bien distintos para esto. ▶ Su función es procesar datos.
▶ El procesamiento se realiza en forma automática.
▶ El procesamiento se realiza siguiendo un programa.
▶ Este programa está almacenado en una memoria interna.
5 6

¿Qué es un algoritmo? Ejemplo: Un Algoritmo

▶ Problema: Encontrar todos los números primos menores que un número

natural dado n
▶ Un algoritmo es la descripción de los pasos precisos para resolver un
problema a partir de datos de entrada adecuados. ▶ Algoritmo: Criba de Eratóstenes (276 AC - 194 AC)
Escriba todos los númerosnaturales
√  desde 2 hasta a n
1. Es la descripción de los pasos a realizar. Para i ∈ Z desde 2 hasta n
2. Especifica una sucesión de instrucciones primitivas. Si i no ha sido tachado, entonces
3. El objetivo es resolver un problema. Para j ∈ Z desde i hasta ⌊ ni ⌋ haga lo siguiente:
4. Un algoritmo tı́picamente trabaja a partir de datos de entrada. Si no ha sido tachado, tachar el número i × j
▶ Resultado: Los números que no han sido tachados son los números
primos menores a n

7 8
¿Qué es un programa? Ejemplo: Un Programa (en Haskell)

Implementación de la Criba de Eratóstenes en el lenguaje de programación

Haskell
▶ Un programa es la descripción de un algoritmo en un lenguaje de
erastotenes : : Int → [ Int ]
programación. erastotenes n = erastotenes aux [ x | x ← [ 2 . . n ] ] 0

1. Corresponde a la implementación concreta del algoritmo para ser erastotenes aux : : [ Int ] → Int → [ Int ]
ejecutado en una computadora. erastotenes aux l i s t a n
2. Se describe en un lenguaje de programación. | n == length l i s t a−1 = l i s t a
| otherwise = erastotenes aux l i s t a f i l t r a d a (n+1)
where l i s t a f i l t r a d a = [ x | x ← l i s t a , ( x ‘mod‘ l i s t a ! ! n)/=0 | |
x==l i s t a ! ! n ]

9 10

Especificación, algoritmo, programa Problema, especificación, algoritmo, programa

1. Especificación: descripción del problema a resolver.

▶ ¿Qué problema tenemos?
▶ Habitualmente, dada en lenguaje formal.
▶ Es un contrato que da las propiedades de los datos de entrada y las
propiedades de la solución.

2. Algoritmo: descripción de la solución escrita para humanos.

Dado un problema a resolver (de la vida real), queremos:
▶ ¿Cómo resolvemos el problema?
▶ Poder describir de una manera clara y unı́voca (especificación)
▶ Puede existir sin una computadora.
▶ Esta descripción deberı́a poder ser validada contra el problema real
3. Programa: descripción de la solución para ser ejecutada en una ▶ Poder diseñar una solución acorde a dicha especificación
computadora. ▶ Este diseño deberı́a poder ser verificado con respecto a la
▶ También, ¿cómo resolvemos el problema? especificación
▶ Pero descripto en un lenguaje de programación. ▶ Poder implementar un programa acorde a dicho diseño
▶ Requiere una computadora para ejecutarse.
▶ Este programa deberı́a poder ser verificado con respecto a su
especificación y su diseño
▶ Este programa deberı́a ser la solución al problema planteado
11 12
También hablaremos de cómo encarar problemas... Diferenciaremos el QUÉ del CÓMO
O partir el problema en problemas más chicos...

Los conceptos de modularización y encapsulamiento siempre estarán

relacionados con los principios de diseño de software. La estrategia se puede
resumir en:
▶ Descomponer un problema grande en problemas más pequeños.
▶ Componerlos y obtener la solución al problema original. ▶ Dado un problema, será importante describirlo sin ambigüedades.
▶ Estrategias Top Down versus Bottom Up. ▶ Una buena descripción no deberı́a condicionarse con sus posibles
soluciones.
▶ Saber que dado un problema, hay muchas formas de describirlo y a su vez,
muchas formas de solucionar... y todas pueden ser válidas!

13 14

Especificación de problemas Lenguaje naturales y lenguajes formales

Lenguajes naturales
▶ Una especificación es un contrato que define qué se debe resolver y qué
▶ Idiomas (castellano)
propiedades debe tener la solución.
▶ Mucho poder expresivo (modos verbales –potencial, imperativo–, tiempos
▶ Define el qué y no el cómo. verbales –pasado, presente, futuro—, metáforas, etc. )
▶ Con un plus (conocimiento del contexto, suposiciones, etc)
▶ La especificación de un problema incluye un conjunto de parámetros: datos
▶ No se usan para especificar porque pueden ser ambiguos, y no tienen un
de entrada cuyos valores serán conocidos recién al ejecutar el programa.
cálculo formal.
▶ Además de cumplir un rol “contractual”, la especificación del problema es Lenguajes formales
insumo para las actividades de ... ▶ Sintaxis sencilla
▶ Testing, ▶ Limitan lo que se puede expresar
▶ Verificación formal de correctitud. ▶ Explicitan las suposiciones
▶ Derivación formal (construir un programa a partir de la
▶ Relación formal entre lo escrito (sintaxis) y su significado (semántica)
especificación).
▶ Tienen cálculo para transformar expresiones válidas en otras válidas

15 16
Lenguajes formales. Ejemplos: Contratos

▶ Una especificación es un contrato entre el programador de una función y

el usuario de esa función.
▶ Ejemplo: calcular la raı́z cuadrada de un número real.
Aritmética: es un lenguaje formal para los números y sus operaciones. Tiene ▶ ¿Cómo es la especificación (informalmente, por ahora) de este problema?
un cálculo asociado.
▶ Para hacer el cálculo, el programa debe recibir un número no negativo.
Lógicas: proposicional, de primer órden, modales, etc. ▶ Obligación del usuario: no puede proveer números negativos.
Lenguajes de especificación: sirven para describir formalmente un problema. ▶ Derecho del programador: puede suponer que el argumento recibido
no es negativo.
▶ El resultado va a ser la raı́z cuadrada del número recibido.
▶ Obligación del programador: debe calcular la raı́z, siempre y cuando
haya recibido un número no negativo
▶ Derecho del usuario: puede suponer que el resultado va a ser correcto

17 18

Partes de una especificación (contrato) Parámetros y tipos de datos

1. Encabezado ▶ La especificación de un problema incluye un conjunto de parámetros: datos

2. Precondiciones o cláusulas “requiere” de entrada cuyos valores serán conocidos recién al ejecutar el programa.
▶ Condición sobre los argumentos, que el programador da por cierta. ▶ Cada parámetro tiene un tipo de datos.
▶ Especifica lo que requiere la función para hacer su tarea. ▶ Tipo de datos: Conjunto de valores provisto de ciertas operaciones
▶ Por ejemplo: “el valor de entrada es un real no negativo” para trabajar con estos valores.
3. Postcondiciones o cláusulas “asegura” ▶ Ejemplo 1: parámetros de tipo fecha
▶ Condiciones sobre el resultado, que deben ser cumplidas por el ▶ valores: ternas de números enteros
programador siempre y cuando el usuario haya cumplido las ▶ operaciones: comparación, obtener el año, ...
precondiciones. ▶ Ejemplo 2: parámetros de tipo dinero
▶ Especifica lo que la función asegura que se va a cumplir después de
llamarla (si se cumplı́a la precondición). ▶ valores: números reales con dos decimales
▶ Por ejemplo: “la salida es la raı́z cuadrada del valor de entrada” ▶ operaciones: suma, resta, ...

19 20
¿Por qué escribir la especificación del problema? Algoritmos y programas

▶ El primer paso será especificar un problema

▶ Luego, el objetivo será escribir un algoritmo que cumpla esa especificación
▶ Nos ayuda a entender mejor el problema ▶ Secuencia de pasos que pueden llevarse a cabo mecánicamente
▶ Nos ayuda a construir el programa ▶ Puede haber varios algoritmos que cumplan una misma especificación
▶ Derivación (Automática) de Programas
▶ Nos ayuda a prevenir errores en el programa ▶ Una vez que se tiene el algoritmo, se escribirá el programa
▶ Testing ▶ Expresión formal de un algoritmo
▶ Verificación (Automática) de Programas ▶ Lenguajes de programación
▶ Sintaxis definida
▶ Semántica definida
▶ Qué hace una computadora cuando recibe ese programa
▶ Qué especificaciones cumple
▶ Ejemplos: Haskell, Python, C, C++, C#, Java, Smalltalk, Prolog.

21 22

Lenguajes de programación Lenguajes de programación

No es tema de la materia... pero demos algún contexto por si se ponen a googlear...

▶ Lenguaje Máquina: son lenguajes que están expresados en lenguajes

directamente inteligibles por la máquina, siendo sus instrucciones cadenas
de 0 y 1.
▶ Lenguaje de Bajo Nivel: son lenguajes que dependen de una máquina
▶ En palabras simples, es el conjunto de instrucciones a través del cual los (procesador) en particular (el más famoso probablemente sea Assembler)
humanos interactúan con las computadoras. ▶ Lenguaje de Alto Nivel (en la materia usaremos algunos de estos):
fueron diseñados para que las personas puedan escribir y entender más
▶ Permiten escribir programas que son ejecutados por computadoras. fácilmente los programas que escriben.

23 24
Código fuente, compiladores, intérpretes... IDE (Integrated Development Environment)
No es tema de la materia... pero demos algún contexto por si se ponen a googlear...

▶ Código Fuente: es el programa escrito en un lenguaje de programación

según sus reglas sintácticas y semánticas. Para escribir y ejecutar un programa alcanza con tener:
▶ Compiladores e Intérpretes: son programas traductores que toman un
código fuente y generan otro programa en otro lenguaje, por lo general, ▶ Un editor de texto para escribir programas (Ejemplos: notepad,
lenguaje de máquina notepad++, gedit, etc)
▶ Un compilador o intérprete (según el lenguaje a utilizar), para procesar y
ejecutar el programa

Pero un mundo mejor es posible...

25 26

IDE (Integrated Development Environment) IDE (Integrated Development Environment)

Algunos IDEs:
▶ Visual Studio (https://visualstudio.microsoft.com/es/)
Ventajas de utilizar algún IDE ▶ Eclipse (https://www.eclipse.org/)
▶ Un editor está orientado a editar archivos mientras que un IDE está ▶ IntelliJ IDEA (https://www.jetbrains.com/es-es/idea/)
orientado a trabajar con proyectos, que tienen un conjunto de archivos. ▶ Visual Code o Visual Studio Code (https://code.visualstudio.com/)
▶ Integran un editor con otras herramientas útiles para los desarrolladores: ▶ Es un editor que se “convierte” en IDE mediante extensions.
▶ Permiten hacer destacado (highlighting) de determinadas palabras y ▶ Lo utilizaremos para programar en Haskell y Python.
sı́mbolos dependiendo del lenguaje de programación.
▶ Son capaces de verificar la sintaxis de los programas escritos (linters)
▶ Generar vistas previas (previews) de cierto tipo de archivos (ej,
archivos HTML para desarrollos web)
▶ Suelen tener herramientas integradas (por ejemplo, el Android Studio
tiene emuladores integrados)
▶ Se pueden especializar según cada lenguaje particular
▶ Permiten hacer depuración o debugging!

27 28
Paradigmas Paradigmas

Existen diversos paradigmas de programación. Comunmente se los divide en

Cada grupo, se especializa según diferentes caracterı́sticas
dos grandes grupos:
▶ Programación Declarativa: describe un conjunto de condiciones,
proposiciones, afirmaciones, restricciones, ecuaciones o transformaciones
▶ Programación Declarativa
que describen el problema y detallan su solución.
▶ Son lenguajes donde el programador le indicará a la máquina lo que
quiere hacer y el resultado que desea, pero no necesariamente el ▶ Paradigma Lógico: los programas están construı́dos únicamente por
cómo hacerlo. expresiones lógicas (es decir, son Verdaderas o Falsas).
▶ Paradigma Funcional: está basado en el modelo matemático de
▶ Programación Imperativa composición funcional. El resultado de un cálculo es la entrada del
▶ Son lenguajes en los que el programador debe precisarle a la máquina siguente, y ası́ sucesivamente hasta que una composición produce el
valor deseado.
de forma exacta el proceso que quiere realizar.

29 30

Paradigmas Paradigmas

Cada grupo, se especializa según diferentes caracterı́sticas

Cada grupo, se especializa según diferentes caracterı́sticas ▶ Programación Declarativa
▶ Programación Imperativa: describe la programación como una secuencia
▶ Paradigma Lógico: PROLOG
de instrucciones o comandos que cambian el estado de un programa.
▶ Paradigma Funcional: LISP, GOFER, HASKELL.
▶ Paradigma Estructurado: los programas se dividen en bloques
(procedimientos y funciones), que pueden o no comunicarse entre sı́. ▶ Programación Imperativa
Existen estructuras de control, que dirigen el flujo de ejecución: IF,
▶ Paradigma Estructurado: PASCAL, C, FORTRAN, FOX, COBOL
GO TO, Ciclos, etc.
▶ Paradigma Orientado a Objetos: se basa en la idea de encapsular ▶ Paradigma Orientado a Objetos: SMALLTALK
estado y comportamiento en objetos. Los objetos son entidades que ▶ Lenguajes multiparadigma: lenguajes que soportan más de un paradigma
se comunican entre sı́ por medio de mensajes. de programación.
▶ JAVA, PYTHON, .NET, PHP

31 32
Paradigmas Paradigmas

Dado dos números, determinar si el segundo es el doble que el primero...

▶ Prolog:
En la materia resolveremos (programaremos) problemas utilizando estos dos
paradigmas:

▶ Paradigma Funcional
▶ Haskell:
▶ Utilizaremos Haskell

▶ Paradigma Imperativo
▶ Python:
▶ Utilizaremos Python

33 34

Resolviendo problemas con una computadora Utilizar nombres declarativos

▶ Usar nombres que revelen la intención de los elementos nombrados. El

Durante el cuatrimestre, además de resolver problemas, veremos algunos nombre de una variable/función deberı́a decir todo lo que hay que saber
aspectos sobre cómo resolverlos: sobre la variable/función

1. Los nombres deben referirse a conceptos del dominio del problema.

▶ Hablaremos de buenas prácticas
2. Una excepción suelen ser las variables con scopes pequeños. Es
▶ Utilizar nombres declarativos habitual usar i, j y k para las variables de control de los ciclos.
▶ Modularizar problemas 3. Si es complicado decidirse por un nombre o un nombre no parece
▶ Uso de comentarios natural, quizás es porque esa variable o función no representa un
▶ y más... concepto claro del problema a resolver.
▶ ¿De qué se trata esto?... veamos un adelanto 4. Usar nombres pronunciables! No es buena idea tener una variable
llamada cdcptdc para representar la “cantidad de cuentas por tipo
de cliente”.

35 36
Utilizar nombres declarativos Control de versiones
Ambos programas son el mismo... ¿Cuál se lee más claro?

int x = 0;
vector<double> y;
...
for(int i=0;i ≤ 4;i=i+1) {
x = x + y[i];
}

int totalAdeudado = 0;
vector<double> deudas;
...
for(int i=0;i ≤ conceptos;i=i+1) {
totalAdeudado = totalAdeudado + deudas[i];
}

37 38

Version Control Systems (CVSs) Ejemplo: Git

▶ Sistema de control de versiones distribuido, orientado a repositorios y con

▶ Permite organizar el trabajo en equipo énfasis en la eficiencia.

▶ Guarda un historial de versiones de los distintos archivos que se usaron 1. Se tiene un servidor que permite el intercambio de los repositorios
▶ Existen distintas aplicaciones: svn, cvs, hg, git entre los usuarios.
2. Cada usuario tiene una copia local del repositorio completo.
▶ Acciones: checkout, add, remove, commit, push, pull, status

39 40
Git: Workflow Otros conceptos
Git básico: pull, push, commit, checkout... Git básico: branches y tags

▶ Tag: Nombre asignado a una versión particular, habitualmente para

releases de versiones a usuarios.

▶ Branch: Lı́nea paralela de desarrollo, para corregir un bug (error en el

programa), trabajar en una nueva versión o experimentar con el código.

▶ Master
▶ Develop
▶ Hotfixes

41 42

Master/Main-develop Hotfixes
Convenciones Convenciones

43 44
Nuevas features Todo junto...
Convenciones

45 46

Consejos Un ejemplo
En el repositorio está toda la historia de lo que pasó con cada lı́nea de código...

▶ Hacer commits pequeños y puntuales, con la mayor frecuencia posible.

▶ Mantener actualizada la copia local del repositorio, para estar
sincronizados con el resto del equipo.
▶ Commitear los archivos fuente, nunca los archivos derivados!
▶ Manejar inmediatamente los conflictos.

47 48
Links útiles ¿Preguntas?

▶ Repos hosts
▶ Bitbucket: https://bitbucket.org
▶ GitHub: https://github.com
▶ GitLab: https://gitlab.com
▶ GitLab Exactas: https://git.exactas.uba.ar

▶ Bibliografı́a
▶ Git - la guı́a sencilla:
http://rogerdudler.github.io/git-guide/index.es.html
▶ Pro Git book:
https://git-scm.com/book/en/v2
▶ Try git:
https://try.github.io

49 50