Introducció

En aquest mòdul es presenta un resum dels conceptes que s'han treballat en l'assignatura, juntament amb la descripció de la prova de síntesi i materials que us poden servir de cara a estudiar per a la prova.

Resum de conceptes

Durant l'assignatura de Pràctiques de Programació hem reforçat els conceptes apresos a l'assignatura de Fonaments de Programació, aprofundint en alguns dels conceptes, estenent-ne d'altres i sobretot avançant en el formalisme.

Conceptes bàsics

A l'inici de l'assignatura es varen repassar els conceptes bàsics que s'havien vist a Fonaments de Programació, i que són la base d'aquesta assignatura. Els principals conceptes que cal tenir clar són:

• Diferència entre algorisme i programa: un algorisme és la descripció formal i precisa de la solució a un problema. Els algorismes s'escriuen en pseudocodi, un llenguatge que es troba entre el llenguatge natural amb que es comuniquen les persones i el llenguatge màquina que entenen els ordinadors. Aquest algorisme es tradueix mitjançant un llenguatge de programació a un programa, que posteriorment pot ser compilat per a convertir-lo en llenguatge màquina i executat per un ordinador.

• Tipus de dades: un programa informàtic no és res més que una transformació d'una informació inicial en una informació final. Per tant, un dels punts més importants és poder definir de forma precisa aquesta informació i poder-la manipular. S'ha recordat el concepte de variable i tipus de dades. Les variables són objectes que contenen informació i ens permeten manipular-la. La informació que pot contenir una variable ve determinada pel seu tipus de dades. Cada tipus de dades permet guardar un determinat tipus d'informació, i tenim diferents nivells de complexitat. A més a més, cada tipus de dades té un conjunt d'operacions associades (aritmètiques, lògiques, d'assignació, ...). Es poden fer canvis d'un tipus de dades a un altre (casts). Dins d'aquests tipus de dades tenim els tipus bàsics, que permeten guardar informació molt bàsica, com un caràcter, un nombre enter o un real. Aquests tipus bàsics es poden combinar mitjançant tuples per formar tipus de dades més complexes, que poden guardar la informació d'una persona o un moviment bancari. Finalment havíem vist els punters, que són un tipus de dades que poden emmagatzemar una adreça de memòria. Aquest tipus de dades ens permeten definir paràmetres d'entrada i sortida en accions i funcions, i tenen un paper molt important en l'ús de la memòria dinàmica.

• Seqüències: també havíem vist que independentment de quin sigui el tipus de dades, sovint no només tenim una dada aïllada, sinó conjunts de dades. Quan tenim un conjunt amb un nombre fixat d'elements, utilitzem els vectors o les matrius. Quan tenim un nombre variable d'elements, utilitzem les taules. Depenent de quines operacions definim sobre les taules, a més a més podem definir alguns tipus abstractes de dades, com ara piles, cues i llistes.

• Estructures de control: els algorismes i programes són un conjunt d'instruccions que s'executen de forma seqüencial. Les estructures de control ens permeten modificar aquesta execució. Tenim dos tipus d'estructures de control, les alternatives, que ens permeten decidir si executar un codi o no depenent d'una condició lògica i les repetitives, que ens permeten executar un codi vàries vegades. Dins el primer conjunt tenim les estructures if, if-else, i switch. En el segon conjunt hem vist les estructures for i while. També hem vist que per a les estructures repetitives, existeixen dos casos típics que si els identifiquem ens poden ajudar a definir la estructura (cerca i recorregut).

• Modularitat: havíem vist que és convenient dividir els problemes en problemes més petits i reutilitzables. Teníem diferents nivells de modularitat:
  • Podem agrupar fragments de codi en una acció o funció. La diferència és que les funcions retornen un valor i per tant es poden utilitzar com a part d'una expressió, mentre que les accions no retornen valor i per tant no poden estar en una expressió. Tant les funcions com les accions poden tenir paràmetres d'entrada, de sortida i d'entrada/sortida.
  • Les funcions i accions es poden agrupar en fitxers. Tenim dos tipus de fitxers, els de capçalera (*.h) i els de codi (*.c).
  • Múltiples fitxers es poden agrupar en format de llibreria, podent-se utilitzar en múltiples aplicacions. 

• Memòria estàtica i memòria dinàmica: cada variable ocupa un cert espai de memòria. La forma com aquesta memòria es reserva diferencia entre memòria estàtica o memòria dinàmica. La memòria estàtica queda definida en el nostre programa, i no pot canviar durant la execució d'aquest. Per exemple, quan definim una variable entera, real o booleana, l'espai que ocupa està fixat, i es reserva automàticament al executar el programa. El mateix passa quan definim un vector o una matriu. El gran avantatge de la memòria estàtica és que es gestiona automàticament, no cal reservar-la ni alliberar-la, ja que el compilador s'encarrega de tot. El gran inconvenient el trobem quan tenim conjunts de dades, com ara taules o TAD, que tenen un nombre d'elements que pot anar variant. Si utilitzem memòria estàtica, hem de reservar un espai de memòria prou gran per a que pugui guardar-se tots els elements que necessitem, i això obliga a posar una mida màxima d'elements, i fa que estiguem utilitzant més memòria de la necessària. La memòria dinàmica és aquella memòria que demanem explícitament durant la execució del programa, mitjançant les crides a les funcions malloc o realloc. Al demanar memòria dinàmica, s'ens retorna l'adreça inicial de l'espai que hem demanat, i cal guardar-la en un punter per poder accedir-hi. Cal tenir en compte que quan utilitzem aquest tipus de memòria, nosaltres (els programadors) tenim la responsabilitat d'alliberar aquesta memòria quan ja no la necessitem, mitjançant la comanda free.

• Recursivitat: A Fonaments de Programació havíem vist que la recursivitat és una estratègia de programació que bàsicament implica que un mètode es cridi a si mateix per tal de resoldre un problema. També havíem vist que alguns problemes son recursius per definició, i que altres problemes es poden convertir en recursius. El gran avantatge de la recursivitat és que quan és aplicable, simplifica molt els algorismes.

Especificació formal d'algorismes

A fonaments de programació havíem vist com escriure algorismes per resoldre problemes. Aquest algorismes descrivien una seqüència de passos per resoldre el problema. A Pràctiques de Programació hem vist que podem especificar formalment aquelles assumpcions inicials en les dades a partir de les precondicions. D'aquesta manera queda detallat formalment quin és l'estat inicial de l'algorisme. També podíem escriure formalment l'estat final de l'algorisme un com a acabat a través de les postcondicions.

A part de la especificació formal, hem vist que aquestes condicions formals es poden traslladar al codi en llenguatge C, utilitzant les assercions.

Disseny descendent

A Fonaments de Programació havíem vist el tema de modularitat. El disseny descendent ens proporciona una metodologia per aplicar aquesta modularitat, dividint un problema en problemes més petits i simples. En l'anàlisi d'un problema cal tenir en compte tant les dades que s'hi manipulen, com el tractament que es fa d'aquestes dades. 

Recursivitat

A partir de la definició bàsica vista a Fonaments de Programació, a Pràctiques de Programació hem vist exemples de mètodes recursius més complexes. També hem vist que tenim diferents tipus de recursivitat, podent parlar de recursivitat simple o múltiple, directa o indirecte, i final o no final. Finalment també hem vist que tot algorisme recursiu es pot convertir en un algorisme iteratiu.

Tipus abstractes de dades (TAD)

A Fonaments de Programació ja havíem vist els tipus abstractes de dades, en concret les piles, cues i llistes. Totes aquestes estructures les havíem definit bàsicament sobre taules. Hem vist com podem definir aquests tipus de dades basats en memòria dinàmica, a través de l'ús dels punters. També hem vist que un TAD pot contenir qualsevol tipus d'element, inclús un altre TAD.

Anàlisi de la complexitat

Hem vist que no només cal fer algorismes que resolguin problemes, sinó que també cal fer algorismes que siguin òptims. Hem vist com calcular la complexitat d'un algorisme respecte al nombre de dades. És molt important tenir consciència de la complexitat d'un algorisme a l'hora d'utilitzar-lo en una aplicació, ja que pot ser la diferència entre que aquesta aplicació sigui d'utilitat o no.

Mètodes de cerca i ordenació

Finalment, hem vist que existeixen algorismes per cercar elements en una seqüència ordenada i com ordenar una seqüència. Aquestes dues operacions són molt comunes en totes les aplicacions, i per tant cal conèixer els mètodes que existeixen i la seva complexitat.

Prova de Síntesi

La Prova de Síntesi pot contenir preguntes teòriques, exercicis a realitzar en llenguatge algorísmic i exercicis a realitzar en llenguatge C. Les preguntes barrejaran els diferents continguts vistos a l'assignatura. A mode d'exemple, a continuació teniu un enunciat de mostra de la Prova de Síntesi. Es recomana intentar solucionar la PS primer i després comprovar la solució. Si teniu dubtes, ho podeu comentar en el fòrum de teoria de l'assignatura.

Recomanacions a l'hora de fer la Prova de Síntesi

Abans de començar la prova de síntesi (o qualsevol prova/examen de la UOC) és important comprovar la informació de la portada. En concret, cal comparar el codi de l'assignatura amb els codis que trobareu al vostre full personal d'examen. En la següent figura es mostra on trobareu els codis dins de l'enunciat:

També és important verificar el pes de cada pregunta i quins materials es poden utilitzar. En aquesta assignatura es permet utilitzar materials. Ho trobareu a les següents apartats: