Anar al contingut (clic a Intro)
UdG Home UdG Home
Tancar
Menú

Estudia

Dades generals

Curs acadèmic:
2023
Descripció:
Estructures de dades: punters, estructures lineals, arbres, diccionaris de dades, grafs. Esquemes algorítmics: divideix i venç, mètode voraç, backtracking.
Crèdits ECTS:
9

Grups

Grup A

Durada:
Semestral, 1r semestre
Professorat:
David Figuls Massot  / Jerónimo Hernández González  / Joan Surrell Saurí  / Pau Xiberta i Armengol
Idioma de les classes:
Català (100%)

Grup N

Durada:
Semestral, 1r semestre
Professorat:
David Figuls Massot  / Jerónimo Hernández González  / Joan Surrell Saurí  / Pau Xiberta i Armengol
Idioma de les classes:

Competències

  • CT01 Analitzar situacions complexes i dissenyar estratègies per a resoldre-les
  • CB01 - Analitzar situacions complexes i dissenyar estratègies per resoldre-les
  • CB03 - Aplicar criteris de qualitat a les propostes i / o projectes
  • CB05 - Prendre decisions per a la resolució de situacions diverses
  • CCI6 Coneixement i aplicació dels procediments algorísmics bàsics de les tecnologies informàtiques per a dissenyar solucions a problemes, analitzar la idoneïtat i complexitat dels algorísmics proposats
  • CCI7 Coneixement, disseny i utilització de forma eficient els tipus i estructures de dades més adequades a la resolució d'un problema.
  • CCI8 Capacitat per analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, elegint el paradigma i els llenguatges de programació més adequats
  • CE17 - Coneixement i aplicació dels procediments algorísmics bàsics de les tecnologies informàtiques per dissenyar solucions a problemes , analitzant la idoneïtat i complexitat dels algorismes proposats
  • CE18 - Coneixement, disseny i utilització de forma eficient els tipus i estructures de dades més adequades a la resolució d'un problema
  • CE19 - Capacitat per analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, triant el paradigma i els llenguatges de programació més adequats

Continguts

1. Introducció

          1.1. Classes i abstracció de dades

          1.2. Programació utilitzant classes

          1.3. Memòria dinàmica i estructures enllaçades

          1.4. Genèrics

          1.5. Esquemes algorítmics

2. Estructures de dades lineals

          2.1. Introducció

          2.2. Piles

          2.3. Cues

          2.4. Llistes amb punt d'interès

          2.5. Iteradors

3. Arbres

          3.1. Introducció. Recursivitat.

          3.2. Arbres binaris

          3.3. Algoritmes sobre arbres

          3.4. Arbres n-aris

          3.5. Monticles i cues de prioritat

          3.6. Particions

4. Diccionaris de dades

          4.1. Introducció

          4.2. Conjunts, EDFs, fitxers directes

          4.3. Representacions lineals

          4.4. Representacions ordenades

          4.5. Arbres de cerca

          4.6. Tècniques de dispersió

          4.7. Fitxers relatius i directes

5. Grafs i estructures compostes

          5.1. Concepte

          5.2. Representació de grafs

          5.3. Algoritmes bàsics sobre grafs

          5.4. Relacions

          5.5. Estructures compostes

6. Algoritmes voraços

          6.1. Introducció

          6.2. L'esquema voraç

          6.3. Exemples de l'esquema voraç

          6.4. Algoritmes quasi-òptims

          6.5. Algoritmes voraços sobre grafs

7. Algoritmes de divideix i venç

          7.1. Introducció

          7.2. L'esquema de divideix i venç

          7.3. Eficiència i llindar d'un algoritme

          7.4. Exemples d'algoritmes de divideix i venç

8. Backtracking

          8.1. Introducció

          8.2. Concepte de backtracking

          8.3. Variants de l'esquema

          8.4. Exemples de backtracking

Activitats

Tipus d’activitat Hores amb professor Hores sense professor Hores virtuals amb professor Total
Elaboració individual de treballs 14,00 34,00 0 48,00
Prova d'avaluació 4,00 10,00 0 14,00
Resolució d'exercicis 42,00 56,00 0 98,00
Sessió participativa 30,00 35,00 0 65,00
Total 90,00 135,00 0 225

Bibliografia

  • Franch Gutiérrez, Xavier (1999 ). Estructures de dades : especificació, disseny i implementació (4ª ed.). Barcelona: Edicions UPC. Catàleg
  • Brassard, Gilles (cop. 1996 ). Fundamentals of algorithmics . Englewood Clifs, N.J.: Prentice-Hall International. Catàleg
  • Horowitz, Ellis (cop. 2007 ). Fundamentals of data structures in C++ (2nd ed.). Summit: Silicon Press. Catàleg
  • Horowitz, Ellis (cop. 2008 ). Computer algorithms (2nd ed.). Summit: Silicon Press. Catàleg
  • Preiss, Bruno R (cop. 1999 ). Data structures and algorithms : with object-oriented design patterns in C++ . New York [etc.]: John Wiley and Sons. Catàleg
  • Gonzalo Arroyo, Julio (1997 ). Esquemas algorítmicos : enfoque metodológico y problemas resueltos . Madrid: Universidad Nacional de Educación a Distancia. Catàleg
  • Wirth, Niklaus (cop. 1987 ). Algoritmos y estructuras de datos . México, D.F. [etc.]: Prentice-Hall Hispanoamericana. Catàleg
  • Stroustrup, Bjarne (cop. 2013 ). The C++ programming language (4th ed.). Upper Saddle River, NJ: Addison-Wesley. Catàleg
  • Stroustroup, Bjarne (2014). Programming: Principles and Practice Using C++ (2a edició). Addison Wesley. Catàleg

Avaluació i qualificació

Activitats d'avaluació:

Descripció de l'activitat Avaluació de l'activitat % Recuperable
Avaluació continuada Problemes de teoria i exercicis de laboratori.

• S'avaluaran un conjunt de problemes proposats, resolts a classe i a casa.

• També s'avaluaran alguns exercicis proposats a les sessions de laboratori.
25 No
Pràctiques S'avaluarà la implementació d'una pràctica d'estructures de dades i una segona d'algorítmica).

Aquesta activitat es desenvoluparà principalment fora de classe.
25 No
Examen Examen amb dues parts, una d'Estructures de dades i una d'Algorítmica, amb qüestions curtes i un problema a cada part.
Aquesta activitat és obligatòria i es podrà recuperar.
50

Qualificació


  • En l'avaluació es tindran en compte les activitats segons els pesos indicats (avaluació continuada, pràctiques de laboratori i les dues parts de l'examen).
  • La nota d'avaluació continuada només es tindrà en compte en els alumnes que demostrin treure profit de les sessions de problemes i de laboratori (≥5), mentre que la resta d'alumnes s'avaluaran amb el sistema d'avaluació únic.
  • Les pràctiques no tenen recuperació. Les persones que no presentin les pràctiques o les presentin i no funcionin, s'avaluaran amb un sistema equivalent a l'avaluació única, sigui quina sigui la seva nota d'avaluació continuada.
  • L'examen constarà de dues parts (Est.de Dades i Algorítmica) i caldrà treure una nota mínima en cadascuna d'elles.
  • Hi haurà recuperació de l'examen.
  • A la Guia Docent que es presenta el primer dia de classe hi ha una explicació més detallada de l'avaluació.
  • Els professors de l'assignatura decidiran sobre qualsevol aspecte no contemplat.

Criteris específics de la nota «No Presentat»:
Tindran la qualificació de NP els alumnes que no es presentin a l'examen de segona volta (i no hagin superat l'assignatura a primera volta).

Avaluació única:
En l'avaluació única només es tindrà en compte:

  • Les pràctiques de laboratori, 30% de la nota (no recuperable).
  • L'examen de final, 70% de la nota (consta de dues parts i és recuperable).

Les pràctiques de laboratori s'hauran de lliurar dins els mateixos terminis de la resta d'alumnes.

Requisits mínims per aprovar:
Per considerar superada l’assignatura, caldrà obtenir una qualificació mínima de 5.0 i superar el mínim de cada part de l'examen.

Tutoria

Les tutories seran presencials, però es podran fer usant Google Meet.

Comunicacio i interacció amb l'estudiantat

A més de les classes, la comunicació amb els alumnes es farà usant els fòrums de l'assignatura.

També es pot fer per correu electrònic, però es reserva per qüestions personals.

Observacions

A l'inici de l'assignatura no hi haurà classes de laboratori i es faran classes addicionals de teoria.

Segons el pla d'estudis oficial, cal tenir aprovada Metodologia i Tecnologia de la Programació II per matricular-se d'aquesta assignatura.

Assignatures recomanades

  • Lògica i matemàtica discreta
  • Metodologia i tecnologia de la programació II

Escull quins tipus de galetes acceptes que el web de la Universitat de Girona pugui guardar en el teu navegador.

Les imprescindibles per facilitar la vostra connexió. No hi ha opció d'inhabilitar-les, atès que són les necessàries pel funcionament del lloc web.

Permeten recordar les vostres opcions (per exemple llengua o regió des de la qual accediu), per tal de proporcionar-vos serveis avançats.

Proporcionen informació estadística i permeten millorar els serveis. Utilitzem cookies de Google Analytics que podeu desactivar instal·lant-vos aquest plugin.

Per a oferir continguts publicitaris relacionats amb els interessos de l'usuari, bé directament, bé per mitjà de tercers (“adservers”). Cal activar-les si vols veure els vídeos de Youtube incrustats en el web de la Universitat de Girona.