| Additional title: |
Techniques of Algorithm Design |
| Additional title: |
Técnicas de Diseño de Algoritmos |
| Date: |
2023-24 |
| Abstract: |
Partint de la base que els alumnes tenen uns coneixements bàsics sobre programació i estructures de dades, es pretén que l'alumne sigui capaç de analitza, dissenyar i implementar algoritmes basant-se en les tècniques de disseny d'algoritmes existents. Per complir amb aquest objectiu, l'alumne adquirirà els coneixements sobre: Especificació formal de problemes. Com passar d'una descripció d'un problema a una especificació vàlida per al desenvolupament d'un algoritme que el resolgui. Proves formals per validar programes. Disseny basat en contractes. Precondicions, postcondicions i invariants. Anàlisi de complexitat. Paradigmes per al disseny d'algorismes. Greedy. recursivitat, backtracking, branch & bound, programació dinàmica, algoritmes probabilístics, etc. El desenvolupament d'un algoritme comença per formalitzar l'enunciat d'un problema. A partir d'aquest enunciat es dissenya un algoritme que solucioni el problema, però això no és suficient, cal considerar quant trigarà l'algorisme a donar-nos la solució. Així que ens interessa crear algoritmes tan ràpids com sigui 1 trigarà l'algorisme a donar-nos la solució. Així que ens interessa crear algoritmes tan ràpids com sigui possible. D'aquesta manera podrem crear programes que solucionin problemes els més grans possibles en temps acceptables. Aquesta rapidesa s'aconsegueix dissenyant algoritmes que minimitzin el nombre d'operacions a realitzar per resoldre un problema i desenvolupant una implementació eficient de les operacions de l'algoritme. Això suposarà que en aquesta assignatura l'alumne adquirirà coneixements sobre algorísmica i implementació eficient d'algoritmes. |
| Abstract: |
Based on the basis that students have basic knowledge about programming and data structures, it is intended that the student is able to analyze, design and implement algorithms based on the design techniques of existing algorithms. To fulfill this objective, the student will acquire the knowledge about: Formal problem specification. How to move from a description of a problem to a valid specification for the development of an algorithm that solves it. Formal tests to validate programs. Design based on contracts. Preconditions, postconditions and invariant. Complexity analysis. Paradigms for the design of algorithms. Greedy. recursion, backtracking, branch & bound, dynamic programming, probabilistic algorithms, etc. The development of an algorithm begins by formalizing the statement of a problem. From this statement an algorithm is designed to solve the problem, but this is not enough, we must consider how long it will take the algorithm to give us the solution. So we are interested in creating algorithms as fast as possible. In this way we can create programs that solve problems as large as possible in acceptable times. This speed is achieved by designing algorithms that minimize the number of operations to be performed to solve a problem and developing an efficient implementation of the algorithm's operations. This will mean that in this subject the 1 developing an efficient implementation of the algorithm's operations. This will mean that in this subject the student will acquire algorithmic knowledge and efficient implementation of algorithms. |
| Abstract: |
Partiendo de la base de que los alumnos tienen unos conocimientos básicos sobre programación y estructuras de datos, se pretende que el alumno sea capaz de analiza, diseñar e implementar algoritmos basándose en las técnicas de diseño de algoritmos existentes. Para cumplir con este objetivo, el alumno adquirirá los conocimientos sobre: Especificación formal de problemas. Cómo pasar de una descripción de un problema a una especificación válida para el desarrollo de un algoritmo que lo resuelva. Pruebas formales para validar programas. Diseño basado en contratos. Precondiciones, postcondiciones e invariantes. Análisis de complejidad. Paradigmas para el diseño de algoritmos. Greedy. recursividad, backtracking, branch & bound, programación dinámica, algoritmos probabilísticos, etc. El desarrollo de un algoritmo empieza por formalizar el enunciado de un problema. A partir de este enunciado se diseña un algoritmo que solucione el problema, pero esto no es suficiente, hay que considerar cuánto tardará el algoritmo en darnos la solución. Así que nos interesa crear algoritmos lo más rápidos posibles. De esta forma podremos crear programas que solucionen problemas lo más grandes posibles en tiempos aceptables. Esta rapidez se consigue diseñando algoritmos que minimicen el número de operaciones a 1 aceptables. Esta rapidez se consigue diseñando algoritmos que minimicen el número de operaciones a realizar para resolver un problema y desarrollando una implementación eficiente de las operaciones del algoritmo. Esto supondrá que en esta asignatura el alumno adquirirá conocimientos sobre algorítmica e implementación eficiente de algoritmos. |
| Rights: |
Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial, la distribució, la comunicació pública de l'obra i la creació d'obres derivades, fins i tot amb finalitats comercials, sempre i quan es reconegui l'autoria de l'obra original.  |
| Language: |
Català, anglès, castellà |
| Studies: |
Matemàtica Computacional i Analítica de Dades [2503740] |
| Study plan: |
Grau en Matemàtica Computacional i Analítica de Dades [1403] |
| Document: |
Objecte d'aprenentatge |
guest ::
