Curs 2015-16

Anàlisi i Disseny d'Algorismes

Titulació:	Codi:	Tipus:
Grau en Enginyeria Informàtica	21438	Optativa
Grau en Enginyeria Telemàtica	22613	Optativa
Grau en Enginyeria en Sistemes Audiovisuals	22680	Optativa

 

Crèdits ECTS:

4

Dedicació:

100 hores

Trimestre:

1r

 

Departament:	Dept. de Tecnologies de la Informació i les Comunicacions
Coordinador:	Víctor Dalmau
Professorat:	Victor Dalmau
Idioma:	Català
Horari:
Campus:	Campus de la Comunicació - Poblenou

 

Presentació de l'assignatura

L'assignatura Disseny i Anàlisis d’algorismes és una assignatura optativa, de 4 crèdits, que s'ofereix el segon trimestre del Grau en Enginyeria en Informàtica encara que pot ser cursada també per estudiants dels altres graus.

En aquest curs, s'estudien tècniques per al disseny i anàlisis d'algorismes. Hi ha moltes aplicacions practiques que requereixen solucionar tasques complexes. Per exemple, biòlegs necessiten emmagatzemar informació sobre centenars de milers de gens i sobre milers de milions de parells de bases en bases de dates i necessiten eines per analitzar la similitud entre gens i altres tasques. Totes aquestes tasques requereixen sofisticats algorismes. En l'àmbit d'internet també es necessiten algorismes sofisticats per trobar rutes eficients per on enviar informació o en el disseny de buscadors, per citar nomes un parell d'exemples. El disseny d'algorismes eficients també juga un paper molt important en l’àmbit de les finances, el comerç electrònic, intel·ligència artificial, visió per ordinador, mineria de dades, investigació operativa i molts altres. Molt sovint una petita millora en un algorisme te un impacte molt major en la nostra capacitat per resoldre un problema que 10 anys de millores en la velocitat de CPU.

Molts cops, però, els problemes algorítmics no ens arriben clarament plantejats. Els trobem barrejats amb detalls tècnics que depenen de l’aplicació, alguns essencials i d'altres no. En aquest curs aprendrem a identificar el nucli algorísmic d'un problema (eliminant detalls que son superflus) i veurem tot un conjunt de tècniques que podem utilitzar per a disseny i anàlisis d'algorismes per a tasques complexes. El material vist durant el curs cobreix els següent temes: anàlisis asimptòtic (incloent acotació i recurrències), la tècnica de dividir i vèncer, algorismes voraços, programació dinàmica, algorismes randomitzats, tornada enrere (backtracking), ramificació i poda (branch- and-bound), aproximació, cerca local i programació lineal. S’emfatitzarà el rigor en l'anàlisi dels algorismes.

En el present Pla Docent es detallaran les competències i capacitats a que condueix l'aprenentatge de l'assignatura, on paral·lelament al desenvolupament i estudi dels blocs de continguts teòrics en que està organitzada l'assignatura, juguen un paper fonament al els mòduls pràctics i activitats associades, que estan basats en exercicis i problemes, on es pretén consolidar la comprensió dels conceptes i tècniques adquirides.

En aquesta assignatura es pretén aportar formació algorítmica i una major maduresa en la capacitat de raonament de l'estudiant, potenciant la seva capacitat d'abstracció.

 

Prerequisits

Els requisits previs fonamentals per al seguiment de l’assignatura són els següents:

Coneixements i habilitats bàsics de programació que l’estudiant hauria d’haver adquirit al cursar l’assignatura “Fonaments de la Programació”. En particular, es necessària certa familiaritat amb la notació asimptòtica.

Coneixements bàsics sobre grafs que l’estudiant hauria d’haver adquirit al cursar el segon bloc de l’assignatura “Àlgebra lineal i Matemàtica discreta” del primer curs dels estudis.

Una base matemàtica mínima que l'estudiant hauria d 'haver adquirit durant l'Ensenyament Secundari Obligatori o al cursar l’assignatura “Càlcul i Mètodes Numèrics”. De les habilitats i continguts tractats a l’assignatura “Càlcul i Mètodes Numèrics” només ens cal una destresa mínima a l’hora de manipular expressions algebraiques i familiaritat amb les funcions més importants, com ara l’exponencial o el logaritme, que l’estudiant hauria d’haver vist a les primeres sessions del curs. No es necessari en absolut nocions sobre continuïtat, derivació de funcions, desenvolupaments de Taylor, anàlisi en varies variables ni mètodes numèrics.

Algunes nocions sobre estructures de dades que l’estudiant hauria d’haver adquirit al cursar l’assignatura “Estructures de Dades i Algorismes”.

També s’utilitza, encara que en menor mesura, alguns conceptes que son tractats a les assignatura “Probabilitat i Processos Estocàstics” del segon curs. Amb tot i això, els estudiants que, al no haver superat amb èxit aquesta assignatura, no estiguin familiaritzat s amb aquests conceptes, també podran superar sense problemes l'assignatura, dedicant-hi més d'esforç.

 

Competències

Competències transversals

Competències específiques

Instrumentals G1. Capacidad de análisis y síntesis G2. Capacidad de organización y planificación G3. Capacidad para aplicar los conocimientos al análisis de situaciones y la resolución de problemas G4. Habilidad en la búsqueda y la gestión de la información G5. Habilidad en la toma de decisiones G6. Capacidad de comunicarse con propiedad de forma oral y escrita en catalán y en castellano, tanto ante audiencias expertas como inexpertas   Interpersonals G8. Capacidad de trabajo en equipo   Sistèmiques G11. Capacidad de aplicar con flexibilidad y creatividad los conocimientos adquiridos y de adaptarlos a contextos y situaciones nuevas G12. Capacidad para progresar en los procesos de formación y aprendizaje de manera autónoma y continua G14. Capacidad de motivación por la calidad y por el logro G15. Capacidad de generación de nuevas ideas

H1. Capacidad de concebir y llevar a cabo proyectos informáticos utilizando los principios y metodologías propios de la ingeniería. H3. Capacidad para la redacción y desarrollo de proyectos en el ámbito de su especialidad. H4. Aprender de manera autónoma nuevos conocimientos y técnicas adecuados para la concepción, el desarrollo o la explotación de sistemas informáticos. E1. Poseer familiaridad con las técnicas principales de diseño y analisis de algoritmos eficientes: divide-y-vencerás, algoritmos voraces, algoritmos randomizados, programación dinámica y lineal. E2. Poseer familiaridad con las técnicas principales de diseño de algoritmos para problemas NP- dificiles: la tècnica de vuelta atrás (backtracking), ramificación y poda (branch and bound), aproximación y busqueda local.

 

Avaluació

Els mecanismes d'avaluació són els següents:

1.- Avaluació continua. Aquí s'inclou tant la participació a classe com el resultat dels lliuraments o altres activitats avaluades. El resultat serà una nota, C, entre 0 i 10.

 2.- Examen parcial. Consistirà en un examen obligatori amb preguntes de teoria i problemes sobre les unitats 1 i 2 de l'assignatura que es farà al mig del trimestre. El resultat serà una nota, B1 entre 0 i 10.

3.- Examen final (Desembre). Consistirà en un examen obligatori amb preguntes de teoria i problemes sobre les unitats 3 i 4 de l'assignatura (encara que també hi pot sortir, encara que en menor quantitat, preguntes sobre altres unitats) que es realitzarà durant el període d'exàmens del primer trimestre. El resultat de l'examen final de desembre serà una nota, B2 entre 0 i 10. També es realitzarà un examen opcional que permet avaluar novament les unitats 1 i 2 del parcial. S'actualitzarà la nota B1 si la nota obtinguda és millor.

4.- Examen final (Juliol). Consistirà en dos examens independents i opcionals (un per a les unitats 1 i 2 i l'altre per les unitats 3 i 4). Les notes B1 i B2 s'actualitzaran si la nota obtinguda es millor.

 

Els estudiants poden escollir el tipus d'avaluació.

A) Avaluació contínua.

Per a aprovar una convocatòria cal que les notes B1 i B2 siguin, com a mínim 4. En aquest cas la nota serà 0.30*C+0.30*B1+0.4*B2

B) Avaluació no contínua.

Per a aprovar una convocatòria cal que les notes B1 i B2 siguin, com a mínim 4. En aquest cas la nota serà (0.30*B1+0.4*B2)/0.70

 

 

 

Concreció de l'avaluació per competències.

Totes les competències (tant generals com específiques) s'avaluen mitjançant els mecanismes 1,2,3 i 4 de la secció anterior. L'indicador d'assoliment consisteix en respondre co rrectament a les qüestions plantejades.

 

Continguts

L'assignatura es divideix en dos blocs.

 

BLOC 1

1.- Algorismes dividir-i-vèncer.

Algorisme Mergesort. Algorismes recursius per multiplicació. Com calcular la mitjana amb temps lineal.

 

2.- Algorismes voraços

El problema de la planificació d’intervals. Algorisme de Dijkstra. Implementació mitjançant heaps. Algorisme de Kruskal. Implementació mitjançant l’estructura union-find

 

3.- Programació dinàmica

El problema de la planificació d’intervals amb pesos. Com solucionar el problema de la motxilla i el problema de l’alineació de seqüències utilitzant programació dinàmica.

 

BLOC 2

 

4.- Algorismes randomitzats

Algoritmes randomitzats per als problemes del tall mínim d’un graf i del càlcul de la mitjana.

 

5.- Que fer davant un problema NP-difícil.

Subcasos tractables. Técnica de tornar enrere (back tracking). Ramificació i poda (backtracking). Algorismes d’aproximació. Cerca local. Programació lineal.

 

Metodologia

L'aprenentatge d'una unitat didàctica conté les següents activitats.

-Sessió de teoria. Es realitza amb un grup gran d'estudiants. El professor introdueix els conceptes teòrics de la unitat didàctica. Es realitzaran 11 sessions de teoria. El contingut tra ctat a cada sessió de teoria serà, aproximadament,  el següent:

T1.Presentació de l'assignatura. Introducció del problema de l’alineació de seqüències. Introducció a la tècnica dividir-i-vèncer. Algorisme Mergesort.

T2. Teorema mestre per recurrències. Algorismes recursius per multiplicació. Com calcular la mitjana amb temps lineal.

T3. Introducció als algorismes voraços. El problema de la planificació d’intervals.

T4. Algorisme de Dijkstra. Implementació mitjançant heaps. Algorisme de Kruskal. Implementació mitjançant union-find.

T5. Introducció a la programació dinàmica. El problema de la planificació d’intervals amb pesos.

T6. Com solucionar el problema de la motxilla i el problema de l’alineació de seqüències utilitzant programació dinàmica.

T7. Introducció als algorismes randomitzats. Algorismes randomitzats per als problemes del tall mínim i del càlcul de la mitjana.

T8. Com afrontar problemes NP-complets. Subcasos tractables. Algorismes d’aproximació.

T9. Técnica de tornar enrere (backtracking). Técnica de ramificació i poda (backtracking).

T10. Introducció a la cerca local i exemples.

T11. Introducció a la programació lineal i exemples . Ús de la programació lineal en algorismes d’aproximació i en algorismes de ramificació i poda.

-Treball personal de l'estudiant desprès de la sessió de teoria. L'estudiant revisa els apunts de classe de teoria, tot resolvent dubtes i entenent els conceptes més importants.

-Treball personal de l'estudiant abans de cada sessió de seminari. Abans de cada sessió de seminari el professor farà públic un llistat d'exercicis que posen en pràctica els conceptes vistos a la classe de teoria. Abans de la sessió de seminari, l'estudiant ha de resoldre els exercicis de la llista (o al menys intentar-ho) individualment o amb un altre company.

-Sessió de seminari. Aquesta activitat es durà a terme en grups petits (d'uns 15) d'estudiants. El professor en col·laboració amb els estudiants resoldrà exercicis de la llista. Es realitzaran 6 sessions de seminari.

S1. Es resoldran exercicis sobre algorismes dividir-i-vèncer.

S2. Es resoldran exercicis sobre algorismes voraços.

S3. Es resoldran exercicis sobre programació dinàmica.

S4. Es resoldran exercicis sobre algorismes randomitzats. També es treballaran exercicis sobre l’exploració de subcasos tractables d’un problema difícil.

S5. Es resoldran exercicis sobre algorismes d’aproximació, la tècnica de la tornada enrere, ramificació i poda.

S6. Es resoldran exercicis sobre cerca local i programació lineal

 

Unitat didàctica	Activitat	Hores a l'aula	Hores fora de l’aula
1.-Algorismes dividir-i-vèncer	T1	2	2
	T2	2	2
	S1	2	5
2.- Algorismes voraços	T3	2	2
	T4	2	2
	S2	2	5
3.-Programació dinàmica	T5	2	2
	T6	2	2
	S3	2	5
4.- Algorismes randomitzats	T7	2	2
	S4	2	5
5.-Afrontament de problemes NP-difícils	T8	2	2
	T9	2	2
	T10	2	2
	T11	2	2
	S5	2	5
	S6	2	5
Examen parcial		2	5
Examen final		2	5
Total:		36	64	Total: 100

 

Recursos

Recursos didàctics. Material docent de l'assignatura

- Problemes de Disseny i Anàlisis d’Algorismes. Suport electrònic. Accessible a l'espai Moddle dedicat a l'assignatura abans de cada sessió de seminari.

 

Bibliografia bàsica

-J. Kleinberg, E. Tardos. Algorithm Design. Addison -Wesley 2006.

-S. Dagupta, C.H. Papadimitriou, U.V. Vazirani. Algorithms. Accessible a la url http://www.cs.berkeley.edu/~vazirani/algorithms.html

 

Bibliografia complementària

T.H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein . Introduction to Algorithms. MIT Press i McGraw-Hill 2001.

C. More, E. Mertens. The Nature of Computation. Oxford University Press, 2011.