Algoritmos voraces

Algoritmos voraces - TAD Conjuntos y dispersión Algorítmica III

2011 -0

GUIA 3

Algoritmos voraces, Conjuntos y dispersión

Valor.. a pesar de todas las debilidades del cuerpo, el espíritu debe triunfar Beethoven
Avram Noam Chomsky (nacido el 7 de diciembre de 1928 en Filadelfia, EEUU) es profesor emérito de Lingüística en el MIT y una de las figuras más destacadas de la lingüista delsiglo XX. Creó la gramática generativa, disciplina que situó la sintaxis en el centro de la investigación lingüística y con la que cambió por completo la perspectiva y los programas y métodos de investigación en el estudio del lenguaje, actividad que elevó definitivamente a la categoría de ciencia moderna. Desde el año 1959 en que Chomsky dio su clasificación de las gramáticas, se han publicadomuchos trabajos sobre lenguajes y gramáticas en el aspecto formal. La perspectiva lógico-matemática del distribucionalismo harrisiano, es reconocida y adoptada por Chomsky, como explícitamente se manifiesta en su libro The logical structure of linguistic theory, redactado entre 1951 y 1955, pero sin publicarse íntegramente. Chomsky es quien introduce estructuras sintácticas en el estudio de lalengua. Dada la enorme complejidad del sistema lingüístico, Chomsky considera adecuada la descripción estructural en términos de niveles de representación de las oraciones. Adicionalmente, lo novedoso de Chomsky frente a los estudiosos anteriores es la capacidad de conjugar orgánicamente un pensamiento tradicional con saberes de naturaleza lógico-matemática para tratar de manera clara, formal yexplicita los procesos recursivos del lenguaje humano. Como lingüista Chomsky ha sacudido de manera despiadada al estructuralismo lingüístico en sus manifestaciones estadounidenses y europeas, lo que suscito grandes discusiones y controversias en torno a su modelo generativo transformacional. Pero sus reflexiones no son solo de naturaleza lingüística, sino que tiene perfiles filosóficos, pues despiertacontroversias entre el empirismo y el racionalismo.

Objetivos de aprendizaje
1. 2. 3.

Conocer la técnica de algoritmos voraces Conocer el TAD conjuntos y sus principales algoritmos Conocer la técnica de dispersión

Introducción
Los algoritmos voraces suelen ser sencillos. Se emplean sobre todo para resolver problemas de optimización, como por ejemplo, encontrar la secuencia óptima paraprocesar un conjunto de tareas por un computador, hallar el camino mínimo de un grafo, etc. Habitualmente, los elementos que intervienen son: un conjunto o lista de candidatos (tareas a procesar, vértices del grafo, etc); un conjunto de decisiones ya tomadas (candidatos ya escogidos); una función que determina si un conjunto de candidatos es una solución al problema (aunque no tiene por qué ser laóptima); una función que determina si un conjunto es completable, es decir, si añadiendo a este conjunto nuevos candidatos es posible alcanzar una solución al problema, suponiendo que esta exista;

Augusto Cortez Vásquez

Pág. 1/26

Algoritmos voraces - TAD Conjuntos y dispersión Algorítmica III

2011 -0

una función de selección que escoge el candidato aún no seleccionado que es másprometedor; una función objetivo que da el valor/coste de una solución (tiempo total del proceso, la longitud del camino, etc) y que es la que se pretende maximizar o minimizar; Para resolver el problema de optimización hay que encontrar un conjunto de candidatos que optimiza la función objetivo. Los algoritmos voraces proceden por pasos. Inicialmente el conjunto de candidatos es vacío. Acontinuación, en cada paso, se intenta añadir al conjunto el mejor candidato de los aún no escogidos, utilizando la función de selección. Si el conjunto resultante no es completable, se rechaza el candidato y no se le vuelve a considerar en el futuro. En caso contrario, se incorpora al conjunto de candidatos escogidos y permanece siempre en él. Tras cada incorporación se comprueba si el conjunto resultante...