UABC Unidad 2 - Técnicas avanzadas de Diseño de Algoritmos.ipynb

uabc-unidad-2-t-cnicas-avanzadas-de-dise-o-de-algoritmos.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "UABC  Unidad 2 - Técnicas avanzadas de Diseño de Algoritmos.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyN7u5JqnOJZvWjERlE/mUvn",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/sanchezcarlosjr/74770aa9a9a08eb3e31b62a344378e24/uabc-unidad-2-t-cnicas-avanzadas-de-dise-o-de-algoritmos.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 2 Técnicas avanzadas de Diseño de Algoritmos\n",
        "## UABC\n",
        "\n",
        "### Ilustración\n",
        "By [Carlos Eduardo Sanchez Torres](https://twitter.com/CharllierJr)\n",
        "\n",
        "[Análisis de algoritmos](https://sanchezcarlosjr.notion.site/An-lisis-de-Algoritmos-38fac5ca34e740719b43673db9f8b9188)"
      ],
      "metadata": {
        "id": "yhWhr7QDDMGp"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Eha7gz3_Csp8",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "187bcdb6-1a64-40fc-d2d5-4e9c8ae58131"
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[0., 0., 0., 1., 1., 1., 0.],\n",
              "       [1., 1., 1., 1., 2., 2., 0.],\n",
              "       [1., 1., 2., 2., 2., 2., 0.],\n",
              "       [1., 1., 2., 2., 3., 3., 0.],\n",
              "       [1., 2., 2., 2., 3., 3., 0.],\n",
              "       [1., 2., 2., 3., 3., 4., 0.],\n",
              "       [1., 2., 2., 3., 4., 4., 0.],\n",
              "       [0., 0., 0., 0., 0., 0., 0.]])"
            ]
          },
          "metadata": {},
          "execution_count": 3
        }
      ],
      "source": [
        "import numpy as np\n",
        "\n",
        "def LCSL(X, Y):\n",
        "  m = len(X)\n",
        "  n = len(Y)\n",
        "  c = np.zeros((m+1,n+1))\n",
        "  for i in range(c.shape[0]-1):\n",
        "     for j in range(c.shape[1]-1):\n",
        "        if X[i] == Y[j]:\n",
        "          c[i,j] = c[i-1, j-1] + 1\n",
        "        elif c[i-1, j] >= c[i,j-1]:\n",
        "           c[i,j] = c[i-1,j]\n",
        "        else:\n",
        "          c[i,j] = c[i,j-1]\n",
        "  return c\n",
        "\n",
        "X=\"ABCBDAB\"\n",
        "Y=\"BDCABA\"\n",
        "c = LCSL(X,Y)\n",
        "\n",
        "c"
      ]
    }
  ]
}