Introducció

Aquesta assignatura és la continuació de Fonaments de Programació, i per tant, es parteix d'uns coneixements inicials de programació. Aquests coneixements seran la base tant dels exercicis com dels nous conceptes que s'introduiran, i és important que els tingueu clars. En aquest mòdul es resumeixen els conceptes que s'han donat a Fonaments de Programació, i teniu enllaços a aquests materials per si necessiteu revisar-los. També podeu accedir en qualsevol moment als materials complerts amb el següent enllaç:

Fonaments de Programació

També disposeu de les Transparències de Síntesis, un conjunt de petits documents que us permeten fer un repàs ràpid a tots els conceptes.

Transparències de síntesis

A continuació teniu un conjunt de petites presentacions que resumeixen certs aspectes de l'assignatura. Estan pensades per servir de repàs ràpid, tot i que pot aparèixer-hi alguna informació addicional. Al costat de cada enllaç de descàrrega hi ha una breu definició del contingut:

Resum de conceptes

Durant l'assignatura de Fonaments de Programació hem vist els conceptes bàsics de programació que permeten definir formalment un algorisme per resoldre un problema donat i implementar-l'ho en llenguatge C. 

Algorismes i programes

Generalment tot problema que cal solucionar per mitjà d'un programa informàtic s'exposa en llenguatge no formal, és a dir, el llenguatge que utilitzem les persones per comunicar-nos. Per exemple, un enunciat d'un problema podria ser:

"M'agradaria tenir organitzats els meus contactes per poder buscar el telèfon a partir del seu nom."

Qualsevol persona és capaç d'entendre aquest problema, però malauradament, els ordinadors només entenen instruccions precises i sense ambigüitats. Per aquest motiu, el primer pas que caldria fer és definir formalment aquest problema.

La descripció formal la fem mitjançant el llenguatge algorísmic (conegut com a pseudocodi), un llenguatge que tot i ser molt flexible, permet definir de forma precisa i sense ambigüitats el problema. En aquest cas, caldria identificar que necessitarem un tipus de dades que en permeti representar objectes compostes de nom i telèfon, que un nom és una cadena de caràcters i un número de telèfon una seqüència de números amb un format determinat.

Segurament també identificarem que caldrà poder guardar múltiples objectes d'aquest tipus i per tant que necessitarem utilitzar una taula. Que caldrà com a mínim poder afegir i cercar elements dins d'aquesta taula (possiblement també modificar i eliminar), i per tant, caldrà definir els algorismes que ens permetin dur a terme aquestes accions.

En aquest punt, cal recordar que un algorisme no és res més que una seqüència d'instruccions que s'executen l'una després de l'altre per tal de resoldre un problema.

Un cop tenim el pseudocodi definit amb els tipus de dades i els algorismes, el problema ha quedat totalment formalitzat, però un ordinador encara no és capaç d'entendre'l. Un ordinador només entén seqüències de 0's i 1's (valors binaris), però per a una persona és molt difícil treballar a aquest nivell. La solució és utilitzar un llenguatge de programació, que tot i esser molt més rígid que el pseudocodi, encara és comprensible per a una persona.

Existeixen molts llenguatges de programació, alguns més propers al pseudocodi (alt nivell) i altres més propers al llenguatge de la màquina (baix nivell). En el nostre cas hem utilitzat el llenguatge C, que es considera un llenguatge de nivell mitjà.

Un cop descrit el problema amb el llenguatge de programació, utilitzem el compilador per a traduir de forma automàtica aquest codi a codi màquina que l'ordinador pot entendre, i per tant, executar.

Tipus de dades

El nom d'Informàtica prové de la fusió entre Informació i Automàtica, i bàsicament és la ciència o tècnica de processar informació automàticament. En l'assignatura hem vist que els algorismes acostumen a partir d'una informació inicial, ja sigui llegida per teclat, d'un fitxer o passada com a paràmetre. Els nostres algorismes agafen aquesta informació i la organitzen, manipulen o fan càlculs per obtenir nova informació, que acostuma a ser el resultat de l'algorisme, el qual pot mostrar-la per pantalla, guardar-la en un fitxer o retornar-la per a que un altre algorisme la pugui utilitzar. Per tant, la peça clau en tot el procés és la informació.

En aquest sentit, hem vist 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ó, ...). També hem vist que es poden fer canvis d'un tipus de dades a un altre (casts).

Els tipus bàsics 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.

A més a més, podem guardar conjunts d'objectes. 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. També tenim els tipus abstractes de dades, molt similars a les taules, però que tenen un conjunt d'operacions que els atorguen propietats especials, com són cues, piles i llistes.

Finalment hem 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.

Estructures de control

Hem vist que 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

El concepte de modularitat fa referència a la divisió del codi en fragments més petits i reutilitzables. Hem vist que hi ha 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ó. Els paràmetres de les accions poden ser d'entrada, de sortida o d'entrada/sortida, mentre que els paràmetres de les funcions només poden ser d'entrada.
• 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. Tot i que no hem fet les nostres pròpies llibreries, si que hem utilitzat múltiples llibreries de C, com la stdio que ens proporciona la acció scanf i printf, o la stdlib que ens proporciona les funcions malloc i free.

Memòria estàtica i memòria dinàmica

Amb els tipus de dades hem vist que 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 TADs, 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, se'ns 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

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. Hem 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.

CodeLite

Per facilitar la realització de les activitats de programació, utilitzarem igual que a Fonaments de Programació l'entorn CodeLite. S'aconsella que s'instal·li el CodeLite en l'ordinador, tot i que en cas de problemes, també es pot utilitzar una màquina virtual per utilitzar-lo. En els enllaços relacionats trobareu tota la informació.