Portafolio - SimonFV/Portafolio GitHub Wiki

Algoritmos y Estructuras de Datos

31/07

Programación Orientada a Objetos

• Java es un lenguaje de programación orientado a objetos.
• Se rige con la filosofía write once, run anywhere. Es decir, es portable.
• Al compilar el código, no se genera lenguaje máquina, sino un código intermedio conocido como Bytecode.
• La única máquina capaz de ejecutar Bytecode es la Java Virtual Machine (JVM).
• JVM es especificada por Oracle y es implementada por varias empresas (existen varias JVM: Oracle, IBM, etc.).
• En una computadora se pueden correr varias instancias de JVM.
• Cada proceso Java se ejecuta en una JVM aparte.
• Java + JVM + Utilidades para programar conforman una plataforma de software para el desarrollo de aplicaciones de usuario final.
• Existen varias plataformas en Java:

1. SE (Standard Edition): Aplicaciones de escritorio.
2. ME (Mobile Edition): Dispositivos móviles.
3. EE (Enterprise Edition): Aplicaciones servidor.

• Se distribuye de varias formas:

1. JRE: mínimo para ejecutar programas.
2. JDK: JRE + SE.
3. Servidores de aplicaciones: Implementaciones de EE

02/08

Paradigmas de Programación

• En general, es una forma de ver/entender/modelar el mundo.
• En el ámbito del software, es un estilo fundamental de programación. Determina como el programa ve el mundo.
• Determina como debe ser utilizado el lenguaje por el programador.
• Algunos lenguajes son multiparadigma (no se hace una selección explicita en el código).
• Hay 4 paradigmas principales: Funcional, Lógico, Imperativo, Orientado a Objetos.

Paradigma Lógico

• El mundo se modela mediante predicados lógicos.
• Se aplica directamente principios de matemática discreta.
• Para utilizarlo en aplicaciones comerciales.
• Prolog es el principal lenguaje.

Paradigma Funcional

• El mundo se modela como funciones matemáticas.
• Lenguajes 100% funcionales: Lisp, Scheme.
• Permite declarar funciones, pasar funciones por parámetro, retornar funciones, entre otros.
• Muchos lenguajes modernos, han incorporado este paradigma por conveniencia.

Paradigma Imperativo

• El mundo se modela con instrucciones, pasos, procedimientos.
• Ampliamente utilizados en aplicaciones comerciales.
• Tienden a ser muy eficientes (generalmente compilan en lenguaje máquina).
• Gramaticalmente simples.
• Se consideran como de nivel de abstracción bajo.
• Ejemplos: C, C++;

Paradigma Orientado a Objetos

El mundo se modela como objetos del mundo real con su interacción. Muy naturales para el ser humano. Facilitan la reutilización de código. Mayoritariamente no generan lenguaje máquina. Poseen muchas estructuras sintácticas. Ejemplos: Java, C++, Python, JavaScript.

Tipos primarios: int, float, double, char, short, byte.

Tipos referentes: String, Object.

07/08

ORIENTACION A OBJETOS

Los objetos se componen de atributos y comportamientos (métodos). Es abstracto. Abstracción: Expresar algo en mis propios términos.

CLASES: Todos los objetos son referencias a una clase.

Es recomendable definir los atributos de un objeto como privados, y acceder a ellos con get y set.

Overload: 2 métodos con el mismo nombre; pero reciben distintos parámetros. “private (accedido solo por la misma clase), protected (accedido por las clases hijas), public(accedido por todas las clases)”

14/08

HERENCIA Una clase principal puede heredar atributos a sus “hijos”, al igual que puede tener atributos únicos. Override: “Sobreescribir, o agregar nuevas entradas a un método de la clase padre desde una hija. Polimorfismos: Habilidad de tratar un objeto “hijo” como si fuera su padre, y de poder sobreescribir comportamientos del padre como un hijo. “En una relación de tipo herencia, un objeto de la superclase puede almacenar cualquiera de sus subclases.”

UML Y PAQUETES DE DISEÑO

UML: Conjunto de diagramas estándar.

SDLS: Software Development Lifecycle

1. Recopilación de requerimiento.
2. Análisis de requerimientos.
3. Diseño de software.
4. Implementación.
5. Pruebas.
6. Instalación y mantenimiento.

Ingeniería de software: Producir software de calidad: correcto funcionamiento, mantenible, reusable, ajustado al tiempo/presupuesto del proyecto.

Tutelada por el SEI. ISO es otra organización encargada de esta tarea.

Modelo de cascada / Waterfall: Método ineficiente. Útil en proyectos muy estrictos.

Modelo en espiral: El proyecto se compone de mini-proyectos, estos se van desarrollando con feedback.

Implementado por Rational Unigied Process, donde luego nacería UML.

Nuevos métodos: Agile, Scrom, XP.

21/8/2019

UML y Patrones de diseño

Diseño orientado a objetos:

• Modelo para guiar al programa durante el proceso de diseño de software bajo el paradigma de OO.
• Provee un conjunto de principios para calificar que tan bien esta el diseño de software.

Primera fase: Modelo Conceptual:

• Entender el dominio del problema y crear un modelo conceptual. Este modelo se puede hacer a criterio del diseñador.
• Debe ser fácil de entender.
• Story Board.
• ¿Cómo calza el software en el cuadro completo?

Segunda fase: Análisis:

• Construir historias de usuario / requerimientos.
• User Stories siguen un formato. “Yo como ____ quiero ser capaz de _____ con el fin de _____”
• Se pueden crear prototipos para entender mejor el problema.

Tercera fase: Arquitectura:

• Definir la estructura de la solución para cumplir los requerimientos funcionales y de calidad.
• Documentar las decisiones.

Cuarta fase: Diseño Detallado:

• Construir de forma iterativa, un diseño detallado del sistema por consultar.
• Paso 1: Identificar las clases:

1. Busque los sustantivos en las historias de usuario.
2. Algunos sustantivos se convertirán en clases. Otros se eliminan y otros se unen.
3. Las clases deben tener una sola responsabilidad.

• Paso 2: Identifique asociaciones:

1. Identificar cómo interactúan las clases entre sí.
2. Una asociación tiende a convertirse en un atributo.

• Paso 3: Identifique atributos y métodos.

PATRONES DE DISEÑO

• Un patrón es una regularidad.
• En el software hay regularidades o problemas recurrentes.
• Reutilizar buenas soluciones es una buena práctica conocida por los ingenieros de software.
• Basar nuevas soluciones en experiencias previas.

Patrón de diseño:

• Solución general para un problema común en un contexto dado.
• Es una buena práctica.
• Son conocidos por muchos profesionales a nivel mundial.

23/08/19

Hay 3 patrones de diseño:

1. Creacionales: Determinan como crear objetos.
2. Estructurales: Cómo usar objetos entre sí mediante composición.
3. De comportamiento: Cómo comunicar objetos sin componerlos directamente.

Creacionales:

• Factory
• Builder
• Singleton
• Prototype

Estructurales:

• Adapter
• Abstract Factory
• Bridge
• Composite
• Decorator
• Facade
• Proxy

De comportamiento:

• Intérprete
• Cadena de responsabilidad
• Comando
• Iterador
• Memento
• Observer

Patrón Factory: Crea una clase factory que crea objetos concretos mediante un selector. El caller no conoce las clases concretas.

Interface Dog {
	Void bark ( );
}
class Rottweiller implements Dog {
        void bark( ){
        ---
        }
}
class Poodle implements Dog{
        void bark( ){
        ---
        }
}

class Dog_Factory{
	public static Dog getDog(DogType d){  **
		If(d==DogType.BIG){
                        return new Rottweiller();
		}else if(d==DogType.SMALL){
			return new Poodle();
		}else{
			throw new Exception (“Unknown Oog type”);
		}
	}
        enum DogType{
                SMALL;
                BIG;
        }
}

Facade: Crea una clase que funcione como “fachada” para un subsistema complejo. El caller interactúa con el facade y no con el subsistema directamente.

28/08/19

Singleton: Patrón que permite restringir la instanciación de una clase. Únicamente se puede instanciar una sola clase:

public class Singleton{
	private static Singleton instance=null;
	private Singleton(){
	___
	}
	public void doSomething(){
	___
	public static Singleton getInstance(){
		if(instance==null){
			instance=new Singleton();
		}
		return instance;
	}
}

//Main:
Singleton.getInstance().doSomething();
Singleton var = Singleton.getInstance();

Builder: Delega la construcción de una clase compleja a una clase complementaria.

public class Phone{
	Cámara;
	Radio;
	touchID;
	waterproof;
	private Phone(Builder builder){
		this.Camara = builder.Camara;
                ----
	}
	
public static class Builder{
	Cámara;
	Radio;
	touchID;
	waterproof;
	public Builder withCamara(pCamara){
		this.Camara=pCamara
		return this;
	}

//Main:
Pone p1 = new Builder()
	.whithName(---);
	.withCamara(---);
	.build();
public pone build(){
	Return new Phone(this);
}

30/08/19

ESTRUCTURAS DE DATOS LINEALES

TDA: Tipos de datos abstractos. Poseen fundamentos matemáticos.

• Listas enlazadas: conjunto de elementos List.(add, addFirst, addLast, remove, removeFirst).
• Árboles.
• Grafos.
• Set/Conjuntos.
• Maps/Diccionarios.
• Colas/Pilas.

Arrays: Colección finita y bien definida de elemento de x tipo. Cada elemento esta contiguo uno al otro en memoria. Pros: lectura/escritura rápida. Cons: Eliminación/Inserción en posiciones aleatorias si no hay espacio, no puede crecer/decrecer por demanda.

int[] a = new int[8];
a[0] = 10;
a[7] = 20;
int x = a[0];

Matrices: Arrays multidimensionales (filas y columnas). No todos los elementos están contiguos.

int[][] m = new int[2][2];}

List: ArrayList / LinkedList

LISTAS ENLAZADAS

• Estructura de datos dinámica.
• Crece o decrece por demanda.
• No esta contigua en memoria.
• Lista secuencial de elementos.
• Cada elemento es un nodo.
• Un nodo es un objeto compuesto por dos elementos:

1. El valor que guarda o dato.
2. Referencia al siguiente elemento de la lista.

• La lista tiene una referencia al primer elemento.
• La referencia al primero debe protegerse.
• El último nodo apunta a null.
• Pros: Crece y decrece, inserción en posiciones aleatorias.
• Cons: Lectura/búsqueda es lenta.

04/09/19

Listas Simples: Los nodos solo referencian a otro único nodo.

Listas Dobles:

• Permite navegar hacia atrás.
• Puede tener un first y un last.
• Los nodos poseen dos referencias: next y prev.

06/9/19

Listas Circulares: Cada nodo tiene un sucesor y un predecesor.

• El sucesor del “último” es el “primero” y viceversa.
• Iniciando en cualquier nodo se puede recorrer la lista completa.
• El “first” apunta al último elemento.
• Son útiles cuando se necesita acceder rápidamente el inicio/fin de la lista.
• El recorrido se detiene cuando el “current” es igual al “first”.

Pilas

• Conjunto de elementos colocados uno sobre el otro.
• Únicamente se puede acceder al último elemento insertado.
• Siempre se inserta al final (el final se llama tope).
• Naturaleza LIFO (last input, first output).
• Tiene 3 operaciones:

1. Push: insertar un elemento en el tope.
2. Pop: eliminar un elemento en el tope.
3. Peek: se puede ver el elemento en el tope.

• Se puede implementar con listas o con arrays.

Queue: Conjunto de elementos diseñado para almacenar elementos en prioridad al almacenamiento.

• Naturaleza FIFO (first input, first output).
• Tiene 3 tipos de operaciones:

1. Inserción: add(e) / offer(e)
2. Remover: remove() / poll()
3. Examinar: element() / peek()

13/9/19

Algoritmos de ordenamiento

• Mantener listas de elementos ordenadas e importante para facilitar las búsquedas.
• Una lista de elementos desordenados no permite realizar búsquedas de manera eficiente.
• Hay muchos algoritmos de ordenamiento.
• La meta es encontrar algoritmos cada vez más eficientes.

Selection Sort: Consiste en buscar el menor elemento, sacarlo de la lista, ponerlo en otra y repetir hasta que la lista origina este vacía. Este enfoque es costoso en términos de espacio. Se puede mejorar.

Bubble Sort: Consiste en empujar el mayor hacia el final de la lista. Únicamente se comparan elementos adyacentes.

18/9/19

Insertion Sort: La lista se divide en dos partes: Elementos ordenados y elementos desordenados. El algoritmo saca el primer elemento de la lista desordenada y lo inserta en la lista ordenada. No existen dos listas aparte, la división es lógica. Al insertar en la lista ordenada se van corriendo los elementos hasta encontrar la posición que le corresponde al elemento por insertar.

Merge Sort: Parte el array en dos. Llama recursivamente en cada mitad. Cuando la recursión llega a array de un elemento, se devuelve y empieza a unir un orden subarray.

20/9/2019

QuickSort: El más popular de los algoritmos de ordenamiento. El más rápido en la mayoría de los casos. Parte el arreglo en dos y se llama recursivamente.

• El paso inicial es calcular el pivote.
• El pivote es el elemento central del arreglo.
• Internamente compara los elementos previos y posteriores al pivote contra el valor del pivote.
• Hace swap de los elementos para colocarlos en la mitad que les corresponde.
• Cuando los índices se recruzan, se recurre en cada mitad.

25/9/2019

Radix Sort: Utiliza un enfoque distinto al resto de algoritmos de ordenamiento vistos hasta el momento. Los elementos vistos consideran la llave (el elemento de la lista) como una unidad indivisible.

• Por ejemplo, 100 se considera como el número 100. Sin embargo, Rdix Sort divide la llave en cada uno de sus dígitos y ordena por cada uno de estos.

Radix = base/raíz del sistema numérico:

• Si se ordenan números en base 10: radix = 10.
• Si se ordenan números en base 2: radix = 2.

Binary Search: Buscan un elemento en una lista/ array ordenado. Compara el elemento central del array contra el elemento buscado.

Si el central == buscado, termina, sino:

• Central > buscado, se busca en la mitad inferior.
• Central < buscado, se busca en la mitad superior.

2/10/2019

Árboles binarios: Un árbol es una estructura de datos jerárquica, es decir, la forma en la que se conectan los elementos, permite identificar niveles de importancia.

• Los árboles se componen de nodos. Cada nodo contiene un dato y una o más referencias a otros nodos.
• En un árbol binario, cada nodo tiene a lo sumo dos nodos.
• Existen árboles n-arios, en los que los nodos pueden tener más de dos nodos.
• Estructura básica de un árbol binario:

Un árbol binario de búsqueda (BST) cumple la condición:

• El hijo derecho es mayor que la raíz.
• El hijo izquierdo es menor que la raíz.
• Estas condiciones se cumplen en cualquier parte del árbol.

Un BTS provee búsquedas rápidas y eliminaciones / inserciones eficientes.

¿Cómo se define un nodo en Java?

class Nodo {
	int element;
	Nodo right;
	Nodo left;
}

¿Cómo se define el árbol?

class BST {
	Nodo root = null;
	boolean isEmpty(){
		return root==null;
	}
}

¿Cómo se busca en el árbol?

boolean contains (int e){
	return this.contains(e,root);
}
private boolean contains (int e, Nodo current){
	if(current == null){
		return false;
	}else if(e < current.element){
		return contains(e,current.left);
	}else if(e > current.element){
		return contains(e,current.right);
	}else{
		return true;
	}
}

¿Cómo encontrar el menor?

public Nodo findMin(){
	return this.findMin(this.root);
}
private Nodo findMin(Nodo current){
	if(current == null){
		return null;
	}else if(current.left == null){
		return current;
	}else{
		return find(current.left);
	}
}

¿Cómo se inserta en un árbol?

public void insert(int e){
	root = this.insert(e, this.root);
}
private Nodo insert (int e, Nodo current){
	if(current == null){
		return new Nodo(e);
	}else if(e < current.element){
		current.left = insert (e, current.left);
	} else if(e > current.element){
		current.left = insert (e, current.right);
	}else {
		return current;
	}
}

9/10/19

Árboles binarios de búsqueda

¿Cómo se elimina un elemento?

Hay 3 posibles escenarios:

• Si el nodo por eliminar es una hoja: En este casi simplemente se corta la referencia.
• Si el nodo por eliminar tiene un solo hijo: En este caso se salta el nodo por eliminar y su hijo lo reemplaza.
• Si el nodo por eliminar tiene dos hijos. En este caso:

1. Se busca el elemento menor en el subárbol derecho o el mayor en el subárbol izquierdo.
2. Se copia el elemento encontrado en el 1, en el nodo por eliminar.
3. Se ejecuta el proceso de eliminación a partir de la posición en la que se copió el elemento encontrado en 1.

Árboles AVL

Uno de los supuestos de los árboles es que proveen búsquedas rápidas. Dependiendo del orden de inserción se puede obtener un árbol como: Nodo –> Nodo –> Nodo –> Nodo

En este caso se pierde la rapidez para buscar y se reduce a una búsqueda secuencial. AVL significa Adelson-Velskii y Landis. Es un árbol binario de búsqueda con una condición de balance para asegurar que la profundidad sea óptima:

• La altura a la izquierda no puede diferir en más de 1 con respecto a la derecha.

Niveles de un árbol: La altura de un árbol es el nivel máximo + 1.

Cada nodo tiene el factor de balance como atributo.

¿Cómo se inserta en un AVL?

• Igual que en un BTS.
• Puede resultar en una violación del balance.
• En caso de violación, se aplica una rotación.
• Hay varios casos.
• II – DD: se resuelven con una rotación sencilla.
• ID – DI: se resuelven con rotaciones dobles.

11/10/19

Árboles B

Son árboles n-arios (pueden tener más de dos hijos). Optimizados para estar almacenados en el disco Los árboles vistos hasta el momento asumen que están en memoria completamente:

• No es factible si hay muchos datos. El problema de tener una estructura en disco es la latencia asociada a estos. Los discos son sumamente lentos en comparación a la memoria principal. Los B-trees están optimizados para no tener tantas operaciones en el disco. Un B-tree gráficamente:

• Los B-trees reducen la profundidad del árbol.
• Siempre está balanceado.
• Los nidos se llaman páginas.
• A excepción de la raíz, los nodos siempre están medio llenos. Un B-tree orden m tiene las siguientes características:
• Todas las hojas están en el mismo nivel.
• Todos los nodos tienen a lo sumo m ramas (y m-1 llaves).
• Como mínimo cada nodo (excepto la raíz) tiene al menos m/z ramas.

18/10/19

Árboles de expansión:

23/10/19

Estructuras de datos generales:

Los grafos son estructuras de datos generales aplicables a muchas áreas como:

• Sociología
• Química
• Geografía
• Criminología

Un grafo G agrupa entidades que representan conceptos. Se compone de vértices/nodos que representan cada entidad. Y de aristas/arcos que representan relaciones entre los nodos.

G = {V, A}

V = {1, 2, 6}

A = {(1, 2), (2, 1), (2, 6), (6, 2), (1, 6), (6, 1)}

Un grupo puede ser dirigido o no dirigido.

Los arcos pueden tener magnitudes creando un grafo con peso. El grado de un nodo es la cantidad de conexiones en las que participa. En un grado dirigido hay un grafo saliente y uno entrante.

Un camino P = {v0, v1, …, vn} es el conjunto de vértices que conectan v0 -> vn.

Un ciclo es un camino que empieza y termina en el mismo nodo.

Un grafo es ácido si no tienen ciclos.

Un DAG (Directed acyclic graph) es un nodo dirigido sin ciclos.

¿Cómo se implementa un grafo?

Hay dos formas: matriz de adyacencia y Listas de adyacencia.

Matriz de adyacencia:

Dado un grafo de n vértices, se construye una matriz de nxn donde cada elemento aij tiene uno de los elementos de los siguientes valores:

aij { 1 si hay arco de vi – vj, 0 en caso contrario.

Si el grafo tiene pesos, en vez de 1 se pondría el peso, y en vez de 0 se pondría infinito.

Lista de adyacencia:

Una lista de adyacencia es una lista enlazada donde cada elemento es un nodo de un grafo. Cada elemento tiene una lista con sus conexiones.

Elegir entre una y otra forma depende de:

• Algoritmos por aplicar.
• Densidad del grafo. Alta: matriz, baja: lista.

¿Cómo se recorre un grafo?

Se recorre desde un nodo específico y hasta recorrer todos los nodos alcanzables. Recorrido por anchura (FIFO):

Cola / Visitados:

• D / _
• BC / D
• CH / B
• HR / C
• RAT / H
• AT / R
• T / A
• _ / T

Por profundidad (LIFO):

Pila / Visitados:

• D / _
• BC / D
• BR / C
• BH / R
• BAT / H
• BA / T
• B / A
• _ / B

1/11/19

La ruta mas corta entre un nodo y el resto: es uno de los problemas más comunes de grafos. Edgar Dijsktra propone un algoritmo que calcula la ruta más corta.

• Grafo con peso
• Grafo dirigido

Pasos:

Asignar a todos los nodos infinito, menos al inicial.

A: 0

B: ∞

C: ∞

D: ∞

E: ∞

Calcular el valor a todos los nodos a partir de A.

A: 0

B: 50

C: ∞

D: 80

E: ∞

Selecciona el nodo menor y nos movemos a este. Se recalculan las distancias usando el nuevo nodo como “puente”.

A: 0

B: 50

C: 60

---------------> ¿Qué es menor, la distancia A-D o A-B-D? En este caso A-D, entonces D=80.

D: 80

E: ∞

Se sigue seleccionando el menor no visitado y se recalcula.

6/11/19

Algoritmo de Warshall (Cierre transitivo)

• Permite determinar si hay camino entre cualquier par de nodos del grafo.
• Calcula la matriz de caminos de un grafo G de n vértices representado por la matriz de adyacencia A.
• Define una secuencia de matrices P0, P1, …, Pn. Los elementos de cada matriz Pk[i, j] tiene un cero si no hay camino, o 1 si hay camino de Vi a Vj a través de Vk.
• Algoritmo más corto para todos los vértices.
• Se podría aplicar Dijkstra para todos los vértices, pero sería ineficiente.
• El algoritmo de Floyd-Warshall es más directo para calcular las rutas óptimas para todos los vértices.
• El grafo se representa con la matriz de peso. Si no hay arco/arista se considera infinito.
• La diagonal es infinito.
• Al igual que Warshall, genera n matrices de nxn. En cada paso, se incorpora un nuevo vértice y se evalúan las rutas.
• De igual forma, se generan n matrices predecesores.