Quicksort

Quicksort es un algoritmo de divide y vencerás . primero divide una gran lista en dos pequeñas sub-listas: los elementos de baja y los elementos de alta. puede recursivamente ordenar las listas sub-.

Los pasos son los siguientes:

1. Elija un elemento, llamado pivote , de la lista.

2.Reordenar la lista para que todos los elementos con valores menores que el pivote venir antes de que el pivote, mientras que todos los elementos con valores mayores que el pivote de venir después de él (los mismos valores pueden ir en cualquier dirección).Después de esta división, el pivote está en su posición final. Esto se llama la operación de partición.

3.Recursiva ordenar la lista de sub-elementos de menor y de la sub-lista de mayores elementos.

Pseudocodigo:

function quicksort(array)
     var list less, greater
     if length(array) ≤ 1
         return array  // an array of zero or one elements is already sorted
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

Referencia:
medusa.unimet.edu.ve/programacion/bppr12/Clases/.../QuickSort.ppt

Algoritmos de Busqueda

<iframe src="https://docs.google.com/present/embed?id=dd595rdw_72fxbvzswz" frameborder="0" width="410" height="342"></iframe>

Lenguajes de Programacion

¿Que es Lenguaje de Programacion?

Los lenguajes de programación son herramientas que nos permiten crear programas y software. Entre ellos tenemos Delphi, Visual Basic, Pascal, Java, etc..

Una computadora funciona bajo control de un programa el cual debe estar almacenado en la unidad de memoria; tales como el disco duro.

Los lenguajes de programación de una computadora en particular se conoce como código de máquinas o lenguaje de máquinas.

Estos lenguajes codificados en una computadora específica no podrán ser ejecutados en otra computadora diferente.

Para que estos programas funcionen para diferentes computadoras hay que realizar una versión para cada una de ellas, lo que implica el aumento del costo de desarrollo.

Por otra parte, los lenguajes de programación en código de máquina son verdaderamente difíciles de entender para una persona, ya que están compuestos de códigos numéricos sin sentido nemotécnico.

Los lenguajes de programación facilitan la tarea de programación, ya que disponen de formas adecuadas que permiten ser leidas y escritas por personas, a su vez resultan independientes del modelo de computador a utilizar.

Los lenguajes de programación representan en forma simbólica y en manera de un texto los códigos que podrán ser leidos por una persona.

Los lenguajes de programación son independientes de las computadoras a utilizar.

Existen estrategias que permiten ejecutar en una computadora un programa realizado en un lenguaje de programación simbólico. Los procesadores del lenguaje son los programas que permiten el tratamiento de la información en forma de texto, representada en los lenguajes de programación simbólicos.

Hay lenguajes de programación que utilizan compilador.


La ejecución de un programa con compilador requiere de dos etapas:

1) Traducir el programa simbólico a código máquina
2) Ejecución y procesamiento de los datos.

Otros lenguajes de programación utilizan un programa intérprete o traductor, el cual analiza directamente la descripción simbólica del programa fuente y realiza las instrucciones dadas.

El intérprete en los lenguajes de programación simula una máquina virtual, donde el lenguaje de máquina es similar al lenguaje fuente.

La ventaja del proceso interprete es que no necesita de dos fases para ejecutar el programa, sin embargo su inconveniente es que la velocidad de ejecución es más lenta ya que debe analizar e interpretar las instrucciones contenidas en el programa fuente.

Referencia:

www.lenguajes-de-programacion.com/lenguajes-de-progra...

Algoritmo Recursivo

Teoria de Grafos

la teoría de grafos estudia las propiedades de los grafos, que son colecciones de objetos llamados nodos (o vértices) conectados por líneas llamadas aristas (o arcos) que pueden tener orientación (dirección asignada).

Aristas: Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.

Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.

Referencia:
enciclopedia.us.es/index.php/Teoría_de_grafos

Arbol Binario

Lista de Problemas NP-Completos

SAT (Problema de satisfacibilidad booleana, para fórmulas en forma normal conjuntiva)

• 0-1 INTEGER PROGRAMMING (Problema de la Programación lineal entera)
• CLIQUE (Problema del clique, véase también Problema del conjunto independiente)
  • SET PACKING (Problema del empaquetamiento de conjuntos)
  • VERTEX COVER (Problema de la cobertura de vértices)
    • SET COVERING (Problema del conjunto de cobertura)
    • FEEDBACK NODE SET
    • FEEDBACK ARC SET
    • DIRECTED HAMILTONIAN CIRCUIT (Problema del circuito hamiltoniano dirigido)
      • UNDIRECTED HAMILTONIAN CIRCUIT (Problema del circuito hamiltoniano no dirigido)
• 3-SAT (Problema de satisfacibilidad booleana de 3 variables por cláusula)
  • CHROMATIC NUMBER (Problema de la coloración de grafos)
    • CLIQUE COVER (Problema de la cobertura de cliques)
    • EXACT COVER (Problema de la cobertura exacta)
      • HITTING SET
      • STEINER TREE
      • 3-DIMENSIONAL MATCHING (Problema del matching tridimensional)
      • KNAPSACK (Problema de la mochila)
        • JOB SEQUENCING (Problema de las secuencias de trabajo)
        • PARTITION (Problema de la partición)
          • MAX-CUT (Problema del corte máximo)