{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"provenance": []
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
},
"language_info": {
"name": "python"
}
},
"cells": [
{
"cell_type": "markdown",
"source": [
"# **Pauta Auxiliar 2: Invariantes**\n",
"\n",
"### Profesores: Nelson Baloian, Benjamín Bustos, Sebastian Ferrada, Patricio Poblete\n",
"### Auxiliares: Sebastián Acuña, Valentina Aravena, Vicente Olivares, Ricardo Valdivia"
],
"metadata": {
"id": "mVGi8o8m6CW_"
}
},
{
"cell_type": "markdown",
"source": [
"## **Introducción**\n",
"\n",
"En este auxiliar veremos 3 diferentes problemas, cada uno se resolverá mediante el uso de invariantes. Recordemos que el invariante es una propiedad que se debe cumplir siempre, es la lógica detrás de nuestro algoritmo que nos permitirá decir que estamos resolviendo bien el problema.\n",
"\n",
"Es crucial poder entender bien cual será el invariante y como nos ayudar a resolver el probema. Con ello también tendremos que saber las condiciones iniciales que el invariante debe cumplir y la condición de término del algoritmo.\n",
"\n",
"Mucho OJO porque el invariante no quiere decir que la variable no cambie, sino que es una propiedad que siempre debe cumplirse en la estructura que estemos analizando.\n",
"\n"
],
"metadata": {
"id": "kYRYD4iUrrZK"
}
},
{
"cell_type": "markdown",
"source": [
"\n",
"## **P1. Contar Vocales**\n",
"
\n",
"\n",
"**El invariante:** en este caso será la cantidad de vocales que posee cada string, notemos que esta propiedad siempre se cumplirá porque independiente de como sea el string siempre podremos asociarle un número que represente la cantidad de vocales que posee.\n",
"\n",
"Para que el invariante se cumpla antes de comenzar el primer ciclo tendremos que darnos cuenta que pasa cuando todavía no hemos leído ni una sola letra de la palabra, en este caso podemos notar que la cantidad de vocales tendrá que partir en 0.\n",
"\n",
"
\n",
"\n",
"**La condición de termino:** sabemos que para la iteración tendremos que revisar todas las letras del string para saber si son vocales o no, por lo que la condición de término será cuando revisemos la última última letra, en el algoritmo que se diseña más abajo se muestra que iremos recorriendo la palabra de izquierda a derecha, por lo que la condición de término será cuando ya revisamos la última letra del string.\n",
"\n",
"
\n",
"\n",
"PD: Asumimos que los textos que recibe nuestra función sólo contienen letras en minúsculas.\n",
"\n",
"
\n",
"\n",
"A continuación se muestra la función iterativa que se nos pide para resolver el problema:\n",
"\n",
"
"
],
"metadata": {
"id": "Ihg8PrOU6Rf-"
}
},
{
"cell_type": "code",
"source": [
"def countVowels(word): #La función recibe la variable word que será el string con el que trabajaremos\n",
" vowels = 0 #vowels será nuestro invariante, es una variable que indica la cantidad de vocales que tiene el string.\n",
" index = 0 #esta variable llamada index nos ayudará a realizar la iteración.\n",
" while index < len(word): #aquí estamos definiendo la condición de término de la iteración.\n",
" letter = word[index] #letter será la variable que almacene el valor de la letra que queremos revisar, su valor se actualizará en cada iteración\n",
" if letter in \"aeiouáéíóú\": #aquí preguntamos si la letra pertenece al string: \"aeiouáéíóú\", que son todas las vocales que queremos contabilizar\n",
" vowels += 1 #en el caso que la letra era una vocal sumamos 1 al invariante para actualizar la cuenta\n",
" index += 1 #aumentamos 1 a index para revisar la siguiente letra (independiente de si la letra que acabamos de revisar era una vocal o no)\n",
" return vowels #retornamos la cantidad de vocales que contamos."
],
"metadata": {
"id": "qaMsZsyBrx29"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "markdown",
"source": [
"## **P2. Partición de Lomuto**\n",
"\n",
"#### Ejercicio 1.2 del apunte\n",
"\n",
"Existe un algoritmo alternativo a Hoare, que resulta en una codificación más sencilla.\n",
"\n",
"En este algoritmo, en cada iteración, si $a[j]p)\n",
" else \"Error\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"id": "7hnYf3Pg7Bl9",
"colab": {
"base_uri": "https://localhost:8080/"
},
"outputId": "9b226162-e914-4899-dd4c-4247c648b57c"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"[21, 34, 37, 15, 36] 50 [73, 77, 65, 82, 98, 56]\n",
"Partición OK\n"
]
}
],
"source": [
"verifica_particion(particionLomuto([73,21,34,98,56,37,77,65,82,15,36],50))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"id": "Qju8mXa27Bl9",
"colab": {
"base_uri": "https://localhost:8080/"
},
"outputId": "69ddc62c-670e-4ff6-a9a4-1a494e44ec1a"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"[] 0 [73, 21, 34, 98, 56, 37, 77, 65, 82, 15, 36]\n",
"Partición OK\n"
]
}
],
"source": [
"verifica_particion(particionLomuto([73,21,34,98,56,37,77,65,82,15,36],0))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"id": "cPKy8KYG7Bl9",
"colab": {
"base_uri": "https://localhost:8080/"
},
"outputId": "0a43bf93-c88d-4f53-c40a-c2f7c5a0aefe"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"[73, 21, 34, 98, 56, 37, 77, 65, 82, 15, 36] 100 []\n",
"Partición OK\n"
]
}
],
"source": [
"verifica_particion(particionLomuto([73,21,34,98,56,37,77,65,82,15,36],100))"
]
},
{
"cell_type": "markdown",
"source": [
"## **P3. Bandera Holandesa**"
],
"metadata": {
"id": "-zHvs-rLw2E3"
}
},
{
"cell_type": "markdown",
"source": [
"###a) Analice los posibles invariantes del problema y dibújelos\n",
"\n",
"\n",
"En este caso es bastante más complejo poder intuír cuales serán los invariantes que nos permitan resolver el problema. La idea general para afrontar este problema es poder mantener una estructura que sea nuestro invariante.\n",
"
\n",
"\n",
"\n",
"Como pueden observar en la imagen de abajo, nuestra situación inicial es Q, donde tenemos un arreglo con los elementos desordenados y R es al arreglo al cual debemos llegar.\n",
"\n",
"Los arreglos con letras rojas representan 4 posibles invariantes que se pueden usar para resolver el problema.\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"Estas 4 estructuras funcionan como invariantes del problema, pues en todo momento podremos identificar un grupo que sea rojo, un grupo blanco, un grupo azul y un grupo indeterminado. La idea será partir con los grupos de colores vacíos y a medida que vamos recorriendo la lista podremos ir colocando valores en los grupos rojo, blanco y azul, según corresponda. Eventualmente lograremos clasificar todos los colores y el grupo indeterminado quedará vacío.\n",
"\n",
"Notemos que lo único que cambia en nuestros 4 modelos de invariantes son el orden en el que ponemos el grupo indeterminado, que para efectos de resolver el problema cualquiera de los 4 invariantes funcionarían.\n"
],
"metadata": {
"id": "vrwC0LErr0jz"
}
},
{
"cell_type": "markdown",
"source": [
"### b) Programe la solución al problema siguiendo alguno de los invariantes de la parte __a)__:"
],
"metadata": {
"id": "uLhub3lGr36i"
}
},
{
"cell_type": "markdown",
"source": [
"El invariante que usaremos será el de la esquina inferior izquierda. La idea del algoritmo es mantener 3 contadores, los cuales delimitan los trozos del arreglo en que estamos agrupando los colores.\n",
"\n",
"Usaremos algunos indices para representar el invariante del dibujo:\n",
"\n",
"* Desde el indice __0__ hasta el indice __i__ (sin incluirlo) estarán los elementos de color rojo\n",
"\n",
"* Desde el indice __i__ hasta el indice __j__ (sin incluirlo) estarán los elementos de color blanco\n",
"\n",
"* Desde el indice __j__ hasta el indice __k__ estarán los elementos que aun no sabemos de que color son y no hemos acomodado aún.\n",
"\n",
"* Desde el indice __k__ (sin incluirlo) hasta el indice __n-1__ (donde __n__ es el total de elementos) estarán los elementos de color azul\n",
"\n",
"Por lo tanto, la idea del algoritmo es ir avanzando el indice __j__ e ir acomodando los elementos que vayamos viendo. Para acomodarlos correctamente debemos manejar los indices __i__ y __k__ correctamente. Es importante notar que el elemento al que apunta __i__ no es rojo, ya que apunta al siguiente espacio donde puede ir un elemento rojo. Esto nos permite hacer un rápido intercambio de elementos. Lo mismo ocurre para los otros indices.\n",
"\n",
"En el momento que el indice __j__ supere al indice __k__ ya estaran vistos todos los elementos y por tanto ya se encuentran ordenados.\n",
"\n",
"Para simplificar el código usaremos el número 0 para representar el color rojo, el número 1 para respresentar el color blanco y el número 2 para el color azul"
],
"metadata": {
"id": "7A24nLXqr4bh"
}
},
{
"cell_type": "code",
"source": [
"def ordenarBandera(arr):\n",
" i = 0 #i,j,k serán los índices que nos permiten definir nuestro invariante\n",
" j = 0\n",
" k = len(arr)-1 #k parte siendo el último elemento de la lista porque su recorrido es de atrás hacía adelante\n",
" while(j <= k): #condición de término\n",
" if arr[j]==0: #caso en el que encontramos el color rojo\n",
" arr[i], arr[j] = arr[j], arr[i] #intercambiamos los valores del índice i y del índice j\n",
" i += 1 #como el color rojo aumento en 1 ahora debemos avanzar un valor el indice\n",
" j += 1 #aumentamos el valor de j para analizar el siguiente elemento de la lista\n",
" elif arr[j]==1: #caso en el que encontramos el color blanco\n",
" j += 1 #aumentamos el valor de j para analizar el siguiente elemento de la lista\n",
" else: #caso en el que encontramos el color azul\n",
" arr[j], arr[k] = arr[k], arr[j] #intercambiamos los valores del índice j y del índice k\n",
" k -= 1 #como el color azul aumento en 1 ahora debemos retroceder un valor el indice k\n",
" #OJO! no es necesario aumentar en 1 el valor de j, pues el índice k almacenaba un valor desconocido.\n",
" return arr #retornamos el mismo arreglo que recibimos, pero en este caso ya está modificado según lo pedido\n"
],
"metadata": {
"id": "2nCwrHDZr7_U"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"#Veamos un ejemplo:\n",
"import numpy as np\n",
"\n",
"arr = np.array([0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1])\n",
"ordenados = ordenarBandera(arr)\n",
"print(ordenados)"
],
"metadata": {
"id": "6KIBDxO1r9wB",
"outputId": "930af019-17b2-43e9-c94a-484db2a76439",
"colab": {
"base_uri": "https://localhost:8080/"
}
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"[0 0 0 0 0 1 1 1 1 1 2 2]\n"
]
}
]
}
]
}