Entusiasme per la programació i per la resolució de problemes vistos com a reptes intel.lecutals. Tenir gana. No conformar-se amb un aprovat. Voler un excel.lent i treballar CADA DIA per aconseguir-lo (n'hi ha per a tots). Afrontar els problemes i les pràctiques des del primer moment en què es publiquin. No esperar al darrer dia.
Revisar els apunts de Programació de primer curs.
Assignatura/matèria en el conjunt del pla d'estudis (màx. 4000 caràcters)
L'assignatura d'Estructures de dades s'ubica al tercer quadrimestre del grau en E. Informàtica.
És la continuació natural de Programació 2, perquè aprofundeix en la disciplina de la programació i, especialment, en el paradigma de la Programació Orientada a Objectes (POO).
*Complementa Matemàtica discreta (també del tercer semestre) perquè un dels seus objectius és arribar a implementar un dels objectes que es descriuen teòricament a aquesta assignatura: els grafs
*Complementa també Algoritmes i complexitat perquè descriu algoritmes associats a estructures de dades i discuteix la seva eficiència.
*Dóna eines que seran usades a les assignatures de Bases de dades i Enginyeria de software (en quadrimestres posteriors). En particular, Estructures de dades descriu algunes implementacions d'índexos i de fitxers directes que s'usaran a Bases de dades i també presenta el paradigma de la POO i algun patró de disseny, aspectes en els quals s'aprofundirà a Enginyeria de software.
Requisits per cursar-la
Prerequisits
Corequisits
Professorat
Nom
Correu
Horari de consulta
Crèdits teòrics
Crèdits pràctics
Josep M. Ribo
josepma@diei.udl.cat
Dilluns a les 15:30 o amb Cita prèvia
10.8
Competències
Competències estratègiques de la Universitat de Lleida
Competències específiques de la titulació
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.
Objectius
Dissenya jerarquies de classes polimòrfiques i usant tipus genèrics com a paràmetres.
Segueix i comprén codi desenvolupat per altri (no principal)
Coneix el sentit del software lliure i, particularment, els projectes OpenStreetMap i OpenJDK
Dissenya classes amb excepcions. Captura i tracta excepcions.
Capacitat per comprendre i dominar els conceptes bàsics de matemàtica discreta, lògica, algorísmica i complexitat computacional, i la seva aplicació per a la resolució de problemes propis de l'enginyeria.
Objectius
Aplica algoritmes de teoria de grafs a una situació concreta (secundari)
Dissenya una classe graf
Aplica la notació "O" per tal de discutir el cost d'un algoritme.
Coneix el cost dels algoritmes principals que s'apliquen a grafs (secundari).
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.
Objectius
Coneix el cost dels algoritmes principals que s'apliquen a llistes, taules i arbres.
Coneix el cost dels algoritmes principals que s'apliquen a grafs (secundari).
Dissenya algorismes recursius per a arbres
Aplica algorismes de teoria de grafs a una situació concreta (secundari)
Transforma algorismes recursius amb una i vàries crides en iteratius equivalents (secundari)
Coneixement, disseny i utilització de forma eficient dels tipus i estructures de dades més adequats a la resolució d'un problema.
Objectius
Decideix quina implementació de llistes és més adient per a una situació concreta
Implementa una classe llista amb encadenaments
Decideix quina implementació de taula és més convenient en una situació concreta
Implementa una taula de hash obert
Implementa una taula de hash tancat (secundari)
Dissenya classes que combinen vàries estructures de dades
Dissenya algoritmes recursius per a arbres
Transforma algoritmes recursius amb una i vàries crides en iteratius equivalents (secundari)
Dissenya una classe graf
Aplica algoritmes de teoria de grafs a una situació concreta (secundari)
Programa recorreguts en arbres amb diferents estratègies.
Competències transversals de la titulació
Continguts
Continguts de la matèria
1. Preliminars: El paradigma de la Programació Orientada a Objectes (POO)
1.1 Excepcions
1.2 Generalitzacions, herència i polimorfisme
1.3 Tipus genèrics
2. Estructures de dades d'accés seqüèncial: les llistes
2.1 Què són els contenidors de dades?
2.2 Els contenidors de la Java Collection Framework
2.3 Iterables i iteradors. Especificació i ús
2.4 Col.leccions. Especificació i ús
2.5 Llistes. Especificació.
2.6 Llistes. Implementacions.
2.7 Llistes implementades amb enllaços: LinkedList<T>
3. Estructures de dades arborescents
3.1 Els arbres a vista d'ocell. Definicions, notació, propietats i recorreguts.
3.2 Arbres binaris. Especificació.
3.3 Arbres binaris. Implementació.
4. Estructures de dades d'accés directe: les taules
4.1 Què són les taules?
4.2 Especificació de les taules
4.3 Estratègies d'implementació de les taules
4.4 Taules implementades amb funcions de dispersió (les taules de hash)
->El hash a vista d'ocell
->Hash obert. Implementació de HashMap<K,V>
->El hash en fitxers
4.5 Taules implementades amb arbres binaris de cerca
4.6 Taules implementades amb arbres B.
Bibliografia
Bibliografia recomanada
Bibliografia bàsica:
William Collins: Data Structures and the Java Collections Framework
ISBN: 978-0-470-48267-4
Adam Drozdek: Data Structures and Algorithms in Java [Paperback]
ISBN: 981-4239-23-2
Mark Guzdial, Barbara Ericson: Problem Solving with Data Structures Using Java: A Multimedia Approach
Prentice Hall
Mark A. Weiss: Data Structures and Problem Solving Using Java (3a o 4a edició. Preferiblement, 4a).
Addison Wesley
ISBN: 9780321541406
Bibliografia complementària:
Roberts, Eric S.: The Art & science of Java : an introduction to computer science / Eric S. Roberts
Pearson/Addison Wesley, cop. 2008
ISBN: 0321486129
(Per repassar els aspectes fonamentals de Java)
Kurt Mehlhorn, Peter Sanders: Algorithms and data structures the basic toolbox
Springer
ISBN: 9783540779780
(Llibre amb aspectes més teòrics)
Joan Gimbert i altres: Apropament a la teoria de grafs i els seus algorismes