{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Informatika - Programación \n",
    "# Examen ordinario - Fecha 11-01-2020\n",
    "\n",
    "## Nombre y apellidos: \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Se denominan \"matrices dispersas\" a aquellas matrices en las que la mayoría de sus elementos son cero. Cuando estas matrices tienen una dimensión muy elevada, la cantidad de ceros es tan alta que, en aras de la eficiencia, se suelen utilizar representaciones alternativas a la habitual (lista de listas con todos los elementos de la matriz). Una de las más sencillas se denomina COO y consiste en almacenar, por cada elemento de la matriz no nulo (distinto de cero), la fila y la columna en la que se sitúa. Toda esta información se guardaría en una matriz de 3 filas, en la que:\n",
    "- en la primera fila se almacenan los elementos no nulos\n",
    "- en la segunda fila se almacenan la fila en la que se sitúan los elementos no nulos\n",
    "- en la tercera fila se almacenan las columnas en las que se sitúan los elementos no nuls \n",
    "\n",
    "\n",
    "Así, por ejemplo, la siguiente matriz de dimensión 5x5 tiene 4 elementos no nulos\n",
    "    \n",
    "    m = [[0, 0, 1, 0, 0], \n",
    "         [0, 0, 0, 0, 0], \n",
    "         [-1, 0, 0, 0, 0], \n",
    "         [1, 2, 0, 0, 0],\n",
    "         [0, 0, 0, 0, 0]]\n",
    "\n",
    "- el elemento 1, que está situado en la fila 0, columna 2\n",
    "- el elemento -1, que está situado en la fila 2, columna 0\n",
    "- el elemento 1, que está situado en la fila 3, columna 0\n",
    "- el elemento 2, que está situado en la fila 3, columna 1\n",
    "\n",
    "Por tanto, la representación COO de la matriz $m$ sería:\n",
    "\n",
    "        d = [[1, -1, 1, 2],\n",
    "             [0, 2, 3, 3],\n",
    "             [2, 0, 0, 1]]\n",
    "\n",
    "Escribe las funciones que se describen a continuación para poder diseñar el programa principal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Función `genera_coo` (0.25 puntos)\n",
    "\n",
    "Esta función no tiene parámetros de entrada y devolverá una matriz en representación COO vacía. Básicamente, devolverá una lista formada por tres listas vacías."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Función `normal_a_dispersa` (1.75 puntos)\n",
    "\n",
    "Crea una función `normal_a_dispersa` que reciba una matriz en su formato habitual ($NxM$ elementos) y devuelva la matriz en formato COO (elemento/fila/columna), que será una matriz de $3\\times q$, donde $q$ es el número de elementos no nulos de la matriz de entrada. Recuerda que en la primera fila se almacenará el valor del elemento, en la segunda el valor de la fila y en la tercera el valor de la columna que ocupe el elemento en la matriz original."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = [[0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [-1, 0, 0, 0, 0], [1, 2, 0, 0, 0],[0, 0, 0, 0, 0]]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ejemplo**\n",
    "\n",
    "    Entrada: \n",
    "        m = [[0, 0, 1, 0, 0], \n",
    "             [0, 0, 0, 0, 0], \n",
    "             [-1, 0, 0, 0, 0], \n",
    "             [1, 2, 0, 0, 0],\n",
    "             [0, 0, 0, 0, 0]]\n",
    "    Salida:\n",
    "        d = [[1, -1, 1, 2],\n",
    "             [0, 2, 3, 3],\n",
    "             [2, 0, 0, 1]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Función `dispersa_a_normal` (1.75 puntos)\n",
    "\n",
    "Crea una función `dispersa_a_normal` que haga justo lo contrario que la función anterior. Esta vez la función debe recibir, además de la matriz $d$, el número de filas $N$ y de columnas $M$ de la matriz original."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = [[1, -1, 1, 2], [0, 2, 3, 3], [2, 0, 0, 1]]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ejemplo**\n",
    "\n",
    "    Entrada: \n",
    "        d = [[1, -1, 1, 2],\n",
    "             [0, 2, 3, 3],\n",
    "             [2, 0, 0, 1]]\n",
    "    Salida:\n",
    "        m = [[0, 0, 1, 0, 0], \n",
    "             [0, 0, 0, 0, 0], \n",
    "             [-1, 0, 0, 0, 0], \n",
    "             [1, 2, 0, 0, 0],\n",
    "             [0, 0, 0, 0, 0]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Función `esta` (1.75 puntos)\n",
    "\n",
    "Implementa la función `esta`, que recibe como parámetro de entrada una matriz $d$ en formato COO, un número de fila $i$ y un número de columna $j$. En el caso en el que la matriz $d$ contenga un elemento no nulo en la fila $i$ y columna $j$, la función devolverá el índice de la columna de $d$ en la que se sitúa dicho elemento. Si, por el contrario, la matriz $d$ no contiene un elemento no nulo en dichas posiciones, devolverá -1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = [[1, -1, 1, 2], [0, 2, 3, 3], [2, 0, 0, 1]]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ejemplo**\n",
    "\n",
    "    Entrada: \n",
    "        d = [[1, -1, 1, 2],\n",
    "             [0, 2, 3, 3],\n",
    "             [2, 0, 0, 1]]\n",
    "        i = 2\n",
    "        j = 0\n",
    "    Salida:\n",
    "        1\n",
    "        \n",
    "        \n",
    "    Entrada: \n",
    "        d = [[1, -1, 1, 2],\n",
    "             [0, 2, 3, 3],\n",
    "             [2, 0, 0, 1]]\n",
    "        i = 3\n",
    "        j = 4\n",
    "    Salida:\n",
    "        -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Función `inserta_o_incrementa` (1.75 puntos)\n",
    "\n",
    "Implementa una función `inserta_o_incrementa`, que recibe como parámetro de entrada una matriz $d$ en formato COO, un número de fila $i$, un número de columna $j$ y un número $x$:\n",
    "- si en $d$ ya existe un elemento situado en la fila $i$ y columna $j$, entonces al elemento correspondiente debemos sumarle la cantidad $x$\n",
    "- si en $d$ no existe un elemento situado en la fila $i$ y columna $j$, entonces debemos añadir (por el final) el elemento $x$ situado en la fila $i$ y columna $j$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = [[1, -1, 1, 2], [0, 2, 3, 3], [2, 0, 0, 1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = [[1, -1, 1, 2], [0, 2, 3, 3], [2, 0, 0, 1]]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ejemplo**\n",
    "\n",
    "    Entrada: \n",
    "        d = [[1, -1, 1, 2],\n",
    "             [0, 2, 3, 3],\n",
    "             [2, 0, 0, 1]]\n",
    "        i = 2\n",
    "        j = 0\n",
    "        x = 5\n",
    "    Salida:\n",
    "        d = [[1, 4, 1, 2],\n",
    "             [0, 2, 3, 3],\n",
    "             [2, 0, 0, 1]]\n",
    "        \n",
    "        \n",
    "    Entrada: \n",
    "        d = [[1, -1, 1, 2],\n",
    "             [0, 2, 3, 3],\n",
    "             [2, 0, 0, 1]]\n",
    "        i = 3\n",
    "        j = 3\n",
    "        x = -5\n",
    "    Salida:\n",
    "        d = [[1, -1, 1, 2, -5],\n",
    "             [0, 2, 3, 3, 3],\n",
    "             [2, 0, 0, 1, 3]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Función suma_disperas (1.75 puntos)\n",
    "\n",
    "Crea una función `suma_dispersas` que recibe como parámetro de entrada dos matrices $d1$ y $d2$ en formato COO. La función deberá calcular una nueva matriz $d3$, también en formato COO, que corresponda a la suma de $d1$ y $d2$. Para ello,  se recorrerán, en primer lugar, todos los elementos de $d1$ y se insertarán en $d3$. A continuación se hará lo mismo con los elementos de $d2$.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d1 = [[1, -1, 1, 2], [0, 2, 3, 3], [2, 0, 0, 1]]\n",
    "d2 = [[1, 1, 2], [0, 1, 3], [2, 1, 1]]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ejemplo**\n",
    "\n",
    "    Entrada: \n",
    "        d1 = [[1, -1, 1, 2],\n",
    "              [0, 2, 3, 3],\n",
    "              [2, 0, 0, 1]]\n",
    "        d2 = [[1, 1, 2],\n",
    "              [0, 1, 3],\n",
    "              [2, 1, 1]]\n",
    "    Salida:\n",
    "        d3 = [[2, -1, 1, 4, 1],\n",
    "              [0, 2, 3, 3, 1],\n",
    "              [2, 0, 0, 1, 1]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Función `imprime_matriz` (0.5 puntos)\n",
    "\n",
    "Escribe una función `imprime_matriz` que reciba una matriz en su representación habitual (matriz de $M\\times N$ elementos) y la muestre por pantalla"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Programa principal (0.5 puntos)\n",
    "\n",
    "Dadas las siguientes matrices $m1$ y $m2$, transformarlas a su representación COO ($d1$ y $d2$) y constuir una nueva matriz $d3$ como la suma de las dos matrices anteriores. Mostrar la matriz suma en su representación habitual."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m1 = [[0,1,0,0], [0,0,0,0], [0,0,2,0], [0,0,0,0]]\n",
    "m2 = [[0,0,0,0], [0,5,0,0], [0,0,0,0], [0,0,0,0]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ejemplo**\n",
    "\n",
    "    Entrada: \n",
    "        m1 = [[0,1,0,0], \n",
    "              [0,0,0,0], \n",
    "              [0,0,2,0], \n",
    "              [0,0,0,0]]\n",
    "        m2 = [[0,0,0,0], \n",
    "              [0,5,0,0], \n",
    "              [0,0,0,0], \n",
    "              [0,0,0,0]]\n",
    "\n",
    "    Salida:\n",
    "        La suma de m1 y m2 es:\n",
    "        0 1 0 0\n",
    "        0 5 0 0\n",
    "        0 0 2 0\n",
    "        0 0 0 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}