EDA1

Estructures de
Dades i Algorismes
Prof. Ricardo Baeza Yates
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 

Introducció
Estructures Lineals 1: Aproximació Estructural
Estructures Lineals 1: Aproximació Estructural (cont)
Especificació Formal
Estructures Lineals 2: Implementació 1
Estructures Lineals 3: Implementació 2
Estructures Lineals 4: Comparativa i Resum
Exercici exemple
Estructures en Arbre 1Estructures en Arbre 2
Estructures Associatives: Taules 1
Estructures Associatives: Taules 2
Cues amb Prioritat

Estructures de Dades i Algorismes – Enginyeria Informàtica – DTIC

Introducció
•  Presentació assignatura, definició grups
laboratori i seminaris, descripció de
feina i programació temporal
•  Introducció Global
•  Introducció Estructures de Dades i
Algorismes
•  Introducció als TADs
• Definició formal de TADs
Estructures de Dades i Algorismes – Enginyeria Informàtica – DTIC

1

Presentació
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 

Moodle de l’assignatura a l’Aula Global
Informació Actualitzada
Grups i horaris
Aquestes transparències
Llista de problemes
Enunciats pràctiques
Enllaços i material extra
Bibliografia
Avaluació
Notícies
Estructures de Dades i Algorismes – Enginyeria Informàtica –DTIC

Introducció Global
•  Per què estudiar Informàtica?
•  Què és Informàtica:
Informàtica ≠ programació
•  Informàtica existeix des de 1930
 abans dels ordinadors!
•  Informàtica resol problemes
 diverses tècniques i metodologies
•  Estudiar Informàtica per ser Analista més que no
Programador
•  Assignatura EDI-1  anàlisi i resolució de
problemes amb Estructures de Dades i TADs
•  EDI-1 primerlloc on caldrà fer d’analista a la
carrera
Estructures de Dades i Algorismes – Enginyeria Informàtica – DTIC

2

Introducció Estructures de Dades
i Algorismes
[1]
•  Heu vist tipus simples de dades a Programació: enters,
caracter, reals, booleans.
•  Tipus de dades sense estructura ni funcionalitat
específica.
•  Cal definir formes de funcionar i/o agrupar la informació
•  Sovint és anàleg a quanles persones funcionem i/o ens
organitzem (pq la info. és sovint reflex d’un segment de
nostra societat):
–  Deixem processos pendents  a mig fer una recepta.
–  Invertim una seqüència de passos  desmuntem i tornem a
muntar una moto.
–  Hem d’esperar fer una activitat si hi ha altra gent que ha
arribat primer.
–  Apuntem coses que hem de fer, comprar, recordar,...
Estructures de Dades iAlgorismes – Enginyeria Informàtica – DTIC

Introducció Estructures de Dades
i Algorismes
[2]
•  Cal pensar com:
–  guardar la informació
–  organitzar-la
–  accedir-hi
–  manipular-la (afegir, esborrar, canviar,...)

•  Tota això caldrà fer-ho de manera formal:
–  Per verificar que tot és correcte
–  Per a tenir clar que fa allò que volem
–  Per si algú altre ho ha de fer/programar
–  Per si algú altreho ha de mantenir, ampliar, ...
Estructures de Dades i Algorismes – Enginyeria Informàtica – DTIC

3

Introducció Estructures de Dades
i Algorismes
[3]
•  Exemple: Efecte 2000
–  Molts sistemes codificaven els anys amb dues xifres
decimals
–  Pitjor: usaven directament aquesta implementació
–  Per tant, canviar la implementació va significar retocar tot
el codi existent. Cost i risc!
–  Solució:l‘encapsulació, “no deixar manipular les dades
de qualsevol manera”
•  Separar la interfície de la implementació de les dades
•  Permetre accés a les dades només a través de la interfície
•  D'aquesta manera un canvi d'implementació d'una dada, no
afecta el codi que la utilitza
Estructures de Dades i Algorismes – Enginyeria Informàtica – DTIC

Introducció als Tipus Abstractes
de Dades (TADs)
[1]Context històric dels TADs
Codi

Dades

Llenguatges de baix nivell

bits, bytes
accés a l'espai físic de les dades

Llenguatges d'alt nivell

tipus de dades (punt flotant, caràcters,
estructures...)
no es té accés a l'espai físic de les dades.
Aquestes són variables amb tipus.

Programació estructurada tipus abstractes de dades (llistes, arbres...)
la representació del tipus s'amaga darrera una...