Description

Objetivos: Materia
Resolver problemas m´as grandes. Para ello aprenderemos las siguientes herramientas:
I TADs
I M´odulos
I An´alisis de complejidad I Estructuras de datos avanzadas
I T´ecnicas algoritmicas
I Divide y Triunfar´as / Divide and Conquer I Sorting
Objetivos: Labo
I Entrenar separar problemas en partes
I Aprender a representar estas partes con m´odulos
I Escribir nuestras representaciones en C++
I Aprender a implementar los contenidos vistos en el resto de la materia (estructuras de datos y t´ecnicas algoritmicas).
Estructura labo
Clases
I Presentaci´on de temas en aula (2hs)
I Resoluci´on de ejercicios en labo (3hs)
Ejercitaciones
I Gu´ıas de ejercicios para resolver en clase
I 3 TPs: Especificaci´on, Disen˜o e Implementaci´on
I Talleres optativos
I Talleres obligatorios (∼4)
Clases: descripcio´n template <class T> class vector<T> { public:
// Interfaz de la clase vector(); // Constructor
void push_back(T elem); // Agrega un elemento T operator[](int idx); // i-esimo elemento int size(); // Tama~no del vector T front(); // Elemento del principio
T back(); // Elemento del principio
};
Clases: uso
#include <vector> using namespace std;
int main() {
vector<int> vi; cout << v1.size() << endl; // 0 v1.push_back(1); v1.push_back(2); cout << v1.size() << endl; // 2 cout << v1[0] << endl; // 1 cout << v1[1] << endl; // 2
vector<string> vs = vector<string>(); vs.push_back(“Hola”); vs.push_back(“mundo”);
cout << vs[0] << ” ” << vs[1] << endl; // “Hola mundo”
};
TAD Secuencia
TAD Secuencia(α)
par´ametros formales
g´eneros α
observadores b´asicos
vac´ıa? : secu(α) −→ bool prim : secu(α) s −→ α {¬ vac´ıa?(s)} fin : secu(α) s −→ secu(α) {¬ vac´ıa?(s)} generadores
<> : −→ secu(α)
••• : α × secu(α) −→ secu(α)
otras operaciones
•◦• : secu(α) × α −→ secu(α)
• & • : secu(α) × secu(α) −→ secu(α)
ult : secu(α) s −→ α {¬ vac´ıa?(s)} com : secu(α) s −→ secu(α) {¬ vac´ıa?(s)} long : secu(α) −→ nat
Fin TAD
TAD Secuencia
¡No tiene iesimo!… Lo agregamos:
• [• ] : secu(α) s × Nat i −→ α {i < long(s)}
s[i] ≡ if i == 0 then prim(s) else fin(s)[i-1] fi
Problema: especificacio´n
pares e impares(secu(α) s) → res : tupla(secu(α), secu(α)) Pre ≡{true} Post ≡{
I primera secu pares:
(∀ i : Nat) (i < long(π1(res)) ⇒ π1(res)[i] mod 2 == 0) I segunda secu impares:
(∀ i : Nat) (i < long(π2(res)) ⇒ π2(res)[i] mod 2 == 1) I est´an todos los elementos:
(∀ i : Nat)
(i < long(s) ⇒ pertenece(s[i],π1(res)) ∨ pertenece(s[i],π2(res))) I no sobra ninguno:
(∀ i : Nat) (i < long(π1(res)) ⇒ pertenece(π1(res)[i],s)) ∧
(∀ i : Nat) (i < long(π2(res)) ⇒ pertenece(π2(res)[i],s))
}
Descripci´on: Separa los elementos de la secuencia en dos secuencias de elementos pares e impares

pertenece(x, s) ≡ (∃i : Nat) (i < long(s) ∧ s[i] == x)
Problema: implementacion
#include <vector> using namespace std; pair<vector<int>, vector<int>> pares_e_impares(vector<int> s)
Problema: implementacion
#include <vector> using namespace std;
pair<vector<int>, vector<int>> pares_e_impares(vector<int> s) {
vector<int> pares; vector<int> impares;
for (int i = 0; i < s.size(); i++) {
if (s[i] % 2 == 0) {
pares.push_back(s[i]);
} else {
impares.push_back(s[i]);
} } return pair<vector<int>, vector<int>>(pares, impares);
}

https://es.cppreference.com/w/cpp/container/vector

Alternativamente:
http://www.cplusplus.com/reference/vector/vector/

Conjunto
Almacena elementos y permite revisar pertenencia.
TAD Conjunto(α)
par´ametros formales
g´eneros
observadores b´asicos α
•∈• : α× conj(α)
generadores −→ bool
∅ : −→ conj(α)
Ag : α× conj(α)
otras operaciones −→ conj(α)
∅? : conj(α) −→ bool
# : conj(α) −→ nat
dameUno : conj(α) c −→ α {¬∅?(c)}
sinUno : conj(α) c −→ conj(α) {¬∅?(c)}
Fin TAD
Conjunto (c++)
template<class T> class set<T> { public:
set(); // Construye un conjunto vac´ıo void insert(T elem); // Inserta elem int count(T elem); // Devuelve la cantidad de
,→ apariciones de elem (0 o 1) int size(); // Devuelve el tama~no del conjunto
};
interseccion(secu(α) a, secu(α) b) → res : secu(α)
Pre ≡{true}
Post ≡{(∀x : α)
(pertenece(x,res) ⇐⇒ (pertenece(x,a) ∧ pertenece(x,b))) }
Descripci´on: Devuelve un conjunto con los elementos en comu´n de a y b

vector<int> interseccion(vector<int> a, vector<int> b)
vector<int> interseccion(vector<int> a, vector<int> b) {
set<int> set_a; for (int i = 0; i < a.size(); i++) { set_a.insert(a[i]);
} vector<int> res; for (int i = 0; i < b.size(); i++) { if (set_a.count(b[i])) { res.push_back(b[i]);
} } return res;
}
Diccionario
Almacena asociaciones.
TAD Diccionario(κ, σ)
par´ametros formales
g´eneros
observadores b´asicos κ, σ
def? : κ× dicc(κ, σ) −→ bool
obtener : κ c × dicc(κ, σ) d
generadores −→ σ {def?(c, d)}
vac´ıo : −→ dicc(κ, σ)
definir : κ×σ × dicc(κ, σ)
otras operaciones −→ dicc(κ, σ)
claves : dicc(κ, σ) −→ conj(κ)
Fin TAD

Diccionario (c++)
template<class K, class S> class map<K, S> { public:
map(); // Crea un diccionario vac´ıo
// Obtiene el valor asociado a la clave. Se puede
,→ sobreescribir para definir (ver ejemplo). S operator[](K clave);
int count(K clave); // 1 si la clave est´a definida, 0
,→ sino.
};
Diccionario (ejemplo)
#include <map> using namespace std;
int main() {
map<char, int> m; cout << m.count(’a’) << endl; // 0 m[’a’] = 5; m[’c’] = 10; cout << m[’a’] << endl; // 5 cout << m[’c’] << endl; // 10 m[’a’] = 200; cout << m[’a’] << endl; // 200 cout << m.count(’a’) << endl; // 1 cout << m.count(’b’) << endl; // 0
}
Para recorrer colecciones
Las colecciones son abstracciones que contienen elementos.
¿C´omo recorremos una colecci´on?
I En TADs
I Arreglo. Taman˜o y acceder al i-´esimo (operator[]).
I Secuencia. prim y fin.
I Conjunto. dameUno y sinUno. I Diccionario. claves y obtener.
I En C++
I Iteradores (Proximamente…)
for-range
#include <vector>
#include <set>
#include <map> #include <string> using namespace std;
int main() { vector<int> vi = {1, 2, 5, 6, 7}; for (int n : vi) { cout << n << endl;
} set<string> s = {“Bienvenidos/as”, “a”, “algoritmos”, “2”}; for (string x : s) { cout << x << endl;
} map<int, string> m; m[2] = “Hola”; m[1] = “mundo”; for (pair<int, string> p : m) { cout << p.first << ” -> ” << p.second << endl;
}
};
Ejercitacion hoy
Taller para practicar usar colecciones y m´odulos.
Ambiente de desarrollo
CLion

CLion en casa
Bajar trial en: https://www.jetbrains.com/clion/download/
Crear una cuenta de estudiante con cuenta @dc.uba.ar
Licenciarlo con c´odigo de activaci´on una vez loggeado con la cuenta en www.jetbrains.com
Alternativa
I Editar c´odigo: atom, sublime, vim
I Compilar: CMake + Makefile
I Ejecutar: consola
I Debuggear: gdb (valgrind)

CLion en los labos
En los labos el directorio de usuario (/home/{user}) suele llenarse hasta su capacidad (1GB) y las cosas dejan de andar. Recomendamos los siguientes pasos antes de arrancar:
I Correr $> du -h -d1 | sort -h para listar los directorios ordenados crecientemente por taman˜o. Si el taman˜o final (el del directorio .) es mayor a 700MB, borrar directorios no importantes. Priorizar los que m´as ocupan. Los candidatos suelen ser .cache o .CLion201*. .cache tiene los caches de Google Chrome y Mozzila Firefox. .Clion201* tiene las configuraciones de CLion
I Usar $> rm -r {directorio} para borrar el directorio donde {directorio} se reemplaza con el directorio a borrar. Ej: $> rm -f .cache
Luego, si al correr CLion pide validarlo, no es necesario usar la licencia propia, sino que se puede usar el servidor de licencias del departamento. Suele ser necesario refrescar la lista de servidores m´as de una vez para que lo encuentre.
Abrir CLion en los Labos
A veces CLion no aparece en la lista de aplicaciones de Ubuntu en los labos. En ese caso, se lo puede abrir corriendo $> clion.sh en la terminal (ctrl+alt+t). En caso de faltar actualizar la licencia, se debe usar la opci´on License Server y hacer Discover server hasta que aparezca el servidor de la facu.
Abrir la ejercitacio´n en CLion
En las ejercitaciones, uno de los directorios va a contener un archivo CMakeLists.txt. Para trabajar en CLion se importa este directorio. Este archivo es el que define como se compila el projecto. En el mismo se pueden declarar varios targets que son los archivos ejecutables finales que vamos a tener despu´es de compilar.

(b) Buscamos la carpeta con el
CMakeLists.txt
Abrir la ejercitacio´n en CLion

(c) IMPORTANTE: No sobreescribir el CMakeLists.txt. Elegir Open Project.

(d) Arriba a la derecha aparecer´a al lado del ´ıcono de compilar, la lista de targets