Aquest projecte es basa en la pràctica d'ampliació del mòdul 6. Es tracta de fer un programa que permeti construir sopes de lletres i buscar paraules en una sopa de lletres definida prèviament.

El programa tindrà dues parts:

1. Construcció de sopes de lletres.

Aquesta opció demanarà a l'usuari la dimensió de la taula (que pot no ser quadrada) i el nombre de paraules a amagar. El nombre de files i de columnes de la taula, i el nombre de paraules a amagar, no serà en cap cas superior a 50. 

L'usuari haurà de decidir on vol amagar la paraula. Una vegada introduïda la paraula, haurà d'indicar la fila i columna de la primera lletra de la paraula i la direcció de lectura amb el següent conveni:

• hd   horitzontal d'esquerra a dreta.
• he   horitzontal de dreta a esquerra.
• vb   vertical de dalt a baix.
• vd   vertical de baix a dalt.
• db   diagonal d'esquerra a dreta i de dalt a baix.
• dd   diagonal d'esquerra a dreta i de baix a dalt.
• eb   diagonal de dreta a esquerra i de dalt a baix.
• ed   diagonal de dreta a esquerra i de baix a dalt.

Per exemple:

programa 0 0 db
projecte 2 0 hd
 
 

P
	R
P	R	O	J	E	C	T	E
			G
				R
					A
						M
							A

• Una vegada introduïda la paraula, la posició de la primera lletra i la direcció, el programa haurà de comprovar si és possible, és a dir, si la paraula cap en el tauler i si és compatible amb les paraules introduïdes amb anterioritat.

 
• Una vegada introduïdes totes les paraules, el programa omplirà les posicions buides amb lletres a l'atzar.

 
• S'ha de permetre guardar una sopa així construïda en disc. L'arxiu ha de contenir la dimensió, la llista de paraules que estan amagades i tota la taula. L'arxiu no guadarà la posició ni la direcció on s'amaguen les paraules.

2. Cerca de paraules

• Aquesta serà la part similar a la pràctica d'ampliació del mòdul 6. El programa haurà de llegir un arxiu en el mateix format comentat abans. 

• Una vegada que es trobi la sopa de lletres en memòria haurà de cercar les paraules en les 8 direccions possibles i mostrar en pantalla la llista de paraules amagades i la sopa de lletres amb les paraules amagades en majúscules.

Aquest projecte està basat en un dels exercicis de la 1a Pre-Olimpíada Informàtica Catalana que es va celebrar a Barcelona el 21 d'abril de 2001.

Considerem un taulell quadriculat com el de la figura en el qual cada casella està representada per les seves coordenades (fila, columna). En aquest taulell hi podem trobar algunes caselles negres com les caselles (0,0) i (1,2). 

De les caselles que no són negres, n'hi ha dues que s'han representat d'un color diferent i s'han marcat amb les lletres A i B. A representarà la casella inicial i B la casella final.

Es tracta de cercar un camí, sense passar per caselles negres, que ens porti de la casella A a la casella B. Els camins poden unir dues caselles no negres que tinguin un costat o un vèrtex comú, és a dir, podem considerar camins horitzontals, verticals o en diagonal. El programa podria millorar-se si pogués trobar el camí que satisfaci alguna d'aquestes dues condicions:

1. Que passi per un nombre mínim de caselles.

 
2. Que contingui un nombre mínim de traços rectes. A l'exemple del dibuix, el camí trobat conté 4 traços: horitzontal, diagonal, vertical i, de nou, horitzontal. 

En aquesta figura pot semblar que el programa no serà molt interessant, però proveu amb un tauler de 50 x 50 caselles i veureu com a mà (sense ajuda del programa) no serà fàcil trobar el camí més curt entre dues caselles.

La forma d'introduir les dades pot triar-se lliurement d'entre diverses possibilitats. Una d'aquestes possibilitats és fer servir un arxiu d'entrada i un arxiu de sortida. L'arxiu d'entrada tindrà la següent informació:

1. Nombre total de files.

 
2. Nombre total de columnes.

 
3. Nombre total de caselles negres.

 
4. Coordenades de les caselles negres.

 
5. Coordenades de les caselles inicial i final (A i B).

 
6. Si s'escau, algun paràmetre que indiqui quin camí ha de buscar: un camí qualsevol, un camí amb un mínim de caselles o un camí amb un mínim de traços.

L'arxiu de sortida contindrà la llista de totes les caselles del camí trobat començant per la casella A i acabant per la casella B. En el cas que el camí no sigui possible, també l'haurà d'indicar.
 
 

Quan ens trobem amb el problema del càlcul d'àrees limitats per funcions contínues ens veiem obligats a calcular integrals d'aquestes funcions. Molts altres problemes que aparentment no tenen res a veure amb el càlcul d'àrees també es poden resoldre amb el càlcul d'integrals definides. En molts casos no és possible un càlcul analític exacte d'aquestes integrals i ens veiem en l'obligació de recórrer a un mètode numèric. En aquest projecte es proposa implementar els algorismes més coneguts de càlcul numèric d'integrals i fer una comparació d'aquests en quant a temps de càlcul i precisió.

Mètode dels rectangles

El primer i més intuïtiu dels mètodes numèrics d'integració és el mètode dels rectangles, que consisteix en aproximar l'àrea tancada per la funció que volem integrar i l'eix d'abscisses per una suma d'àrees de rectangles.

Per això es divideix l'interval d'integració [a,b] en n parts iguals de longitud (b-a)/n i s'agafen els rectangles que tenen com a base cadascú d'aquests subintervals i d'alçada la imatge de la funció en l'extrem esquerre (o dret). Les fórmules són:

Mètode dels trapezis

Aquest mètode consisteix en aproximar l'àrea no per rectangles sinó per trapezis, tal i com es pot observar a la figura:

L'àrea d'un trapezi de bases f(x_k) i f(x_k+1) i distància entre bases (b-a)/2 és igual a:

La suma de totes aquestes àrees és:

Es pot comprovar molt fàcilment que el mètode dels trapezis dóna la mitjana aritmètica dels valors (I) i (II) del mètode anterior.

Mètode de Simpson

El mètode de Simpson consisteix en aproximar la funció per arcs de paràbola determinats per tres punts consecutius. 

Després d'un desenvolupament una mica més llarg que en els mètodes anteriors es pot trobar que:

on 

Per tal de fer servir el mètode de Simpson és necessari que n sigui parell.

Es pot fer que la introducció de la funció es pugui fer de dues formes: 

• Un arxiu amb els valors tabulats de la funció. És necessari, en aquest cas, aquestes dades:

• extrem esquerre (a)

 
• longitud del subinterval ((b-a)/n)

 
• llista dels n+1 valors f(x_k)

• Una funció externa que es pugui modificar i tornar a compilar cada vegada. Aquesta funció començaria:

double f(double x){

     return (...);

} 

En aquest últim cas és necessari la introducció del valor n.

 

Com a ampliació de la pràctica d'ampliació 2 del mòdul 3, es proposa en aquest projecte cercar més informació sobre els diferents mètodes d'ordenació i fer una aplicació C/C++ que mostri de forma comparada els dos mètodes ja explicats més un o dos mètodes més. 

Es recorda que els mètodes que es van tractar en la pràctica d'ampliació 2 del mòdul 3 són els mètodes de la bombolla i el de selecció. A més, es podria estudiar i implementar un mètode d'ordenació per inserció. Aquest últim consisteix en ordenar les dades inserint els elements en una estructura ja ordenada de dades. 

A més d'aquests tres mètodes simples, es podria considerar també els següents mètodes més sofisticats: Ordenació Shell i Ordenació ràpida (QSORT).

El projecte no consistiria només en la implementació dels tres o quatre algorismes d'integració sinó que ha de permetre fer un estudi comparatiu de tots tres o tots quatre. Aquest estudi ha de consistir en:

• Velocitat de l'ordenació en un cas promig. ¿Com augmenta aquesta velocitat a l'augmentar el nombre de dades? (Només un estudi experimental)

 
• Velocitat en el pitjor i el millor dels casos.

 
• ¿Té l'algorisme un comportament natural o antinatural? Es diu que un algorisme té un comportament natural si treballa poc, si la llista està gairebé ordenada.

 

 

Una pila és un tipus d'estructura de dades que fa servir el mètode d'accés LIFO (Last in, first out), és a dir, l'última dada en entrar és també la primera en sortir. Podem imaginar una pila de plats que es posen un a sobre d'un altre. El primer plat, el que es troba a sota de tot, és l'últim en fer-lo servir, i el de sobre, l'últim que es va posar, és el primer en fer-lo servir.

Les piles es fan servir molt en programari de sistemes. El mateix compilador de C fa servir una pila per passar arguments a funcions.

Les úniques accions que es poden fer amb una pila és afegir una dada, que es posarà a sobre de tot, i treure una dada, que s'agafarà de sobre de tot.

Una aplicació útil i alhora senzilla de les piles són els analitzadors d'expressions en notació polonesa. Aquesta és la lògica operacional típica de les calculadores de la marca HP. 

L'avantatge principal d'aquest mètode és que no es necessita parèntesis ni la necessitat de suposar cap prioritat entre les operacions. Aquest sistema fa que es minimitzi tant el nombre de tecles presses com el nombre real d'operacions.

Per tal d'explicar aquest mètode operacional imaginem que hem de fer aquesta operació:

3+4*5

Aquesta expressió s'introduiria com:

3, 4,  5, *, +

o bé:

4, 5, *, 3, +

Aquestes dues expressions només contenen números, els símbols d'operació :+ *, i el símbol , (coma) que separa els diferents tokens.

El programa analitzador d'aquesta expressió comença llegint l'expressió pel caràcter de l'esquerra i fa el següent:

• Si és un número l'escriu a la pila.
• El caràcter ',' serveix per separar dos tokens diferents. (s'anomena token a un número o un operador)
• Si és un símbol: +, -, *, / fa l'operació binària corresponent, esborra els dos operadors i posa el resultat corresponent a la pila.

Per tal de distingir entre l'operador binari '-' que representa la resta i l'operador unari '-' que representa canviar el signe, aquest últim operador sempre anirà a l'esquerra del número sense separar per comes. També pot ser útil reservar un símbol diferent per aquest operador, com pot ser 'n'.  Exemple: 

-3+(2*(-5)) 

seria:

 -3,2,-5,*,+

o:

3,n,2,5,n,*,+

Per tal de veure el funcionament de l'analitzador veurem el contingut de la pila amb la següent expressió:

3, 4,5, *,+

 
 

		3
	3	4	3
3	4	5	20	23
3	4	5	*	+
dada	dada	dada	operador	operador

Veiem un exemple una mica més sofisticat:

3,3,2,4,+,*,-,3,5,-,/,1,2,/,+,2,1,3,1,-,/,+,/

																		8
			3														8	2	8
		3	3	3				-15				7.5				8	2	1	2	8
	3	3	2	3	3		-15	3	-15		7.5	1	7.5		8	2	1	3	1	2	8
3	3	2	4	6	18	-15	3	5	-2	7.5	1	2	0.5	8	2	1	3	1	2	0.5	2.5	3.2
3	3	2	4	+	*	-	3	5	-	/	1	2	/	+	2	1	3	1	-	/	+	/

 

Es pot veure que és molt fàcil avaluar expressions d'aquests tipus, només fa falta que el programa pugui extraure els tokens de l'expressió que estan separats per comes. Si el token és un número ha de cridar a una funció que afegeixi aquest número a la pila. Si el token és un operador (per simplificar només considerarem +,-,*,/) fa l'operació binària amb els dos últims números emmagatzemats en la pila i els substitueix pel resultat, per tant, en cada operació, el nivell de la pila baixa en una posició.
 
 

Feu que el programa pugui llegir del teclat o d'un arxiu una expressió aritmètica i doni el resultat. 
 
 

Podeu perfeccionar aquest senzill analitzador d'expressions afegint altres operadors binaris com l'exponenciació i unaris com funcions trigonomètriques, logarítmiques i exponencials. Podeu permetre també l'ús de variables (de moment una o dues variables serà suficient). Si l'analitzador troba el nom d'una variable afegeix a la pila el contingut d'aquesta variable. 
 
 

L'objectiu final d'aquest projecte podria ser construir un programa que, donada una funció que es pugui introduir per teclat o mitjançant un arxiu, tabuli la funció entre dos valors determinats i amb un increment determinat. Per exemple:
 
 

Si volem tabular la funció:

entre els valors 0 i 1 amb un increment 0.1:

Les dades serien:

Funció:             x,x,*,n,exp,x,x*,exp,+,2,/
• dada inicial:       0
• dada final:         1
• increment:         0.1

L'avantatge dels analitzadors d'expressions és que no és necessari haver de compilar el programa de nou per tabular una altra funció.

6. Anàlisi criptogràfic d'un missatge. Substitució monoalfabètica
 

Els mètodes elementals de criptografia consisteixen en substituir unes lletres per unes altres. Si la substitució es fa lletra a lletra i el missatge és suficientment llarg com per tenir unes freqüències de símbols significatius, la comparació d'aquestes freqüències amb les freqüències de les lletres en l'idioma en què està escrit el missatge ens permetrà desxifrar-lo.

 
 

Un conjunt de programes per tal d'obtenir missatges xifrats i desxifrar-los seria un senzill projecte que podria desenvolupar-se de la següent forma:
 
 

Un programa que permeti xifrar missatges. El programa podrà optar per diferents opcions:

Xifrat Juli Cèsar (fa falta introduir un número).
• Xifrat monoalfabètic determinat (fa falta introduir la correspondència de cada lletra. Aquesta serà la clau i es pot introduir mitjançant un arxiu que contingui una permutació qualsevol de les 27 lletres)
• Xifrat monoalfabètic aleatori (la clau la decideix aleatòriament el programa i no la mostra, per tant, serà una bona forma de provar els programes per desxifrar.

En qualsevol cas, la llargada del missatge ha de ser suficient per tal que les freqüències de les seves lletres siguin significatives (mínim 1000 lletres).

Un programa que permeti obtenir les freqüències de les diferents lletres de qualsevol text en format ASCII. Aquest programa ens servirà per determinar la freqüència de les lletres en l'idioma dels textos. Amb aquest programa es pot estudiar si aquestes freqüències depenen no només de l'idioma sinó també del tipus de text, de l'autor, de l'època, del tema, etc.

 

Amb aquest programa determinarem tant les freqüències de les lletres en el idioma determinat sinó també les freqüències de les lletres en el missatge xifrat. Aquestes freqüències sortiran en un arxiu que servirà d'entrada per al tercer programa.

 

El tercer programa agafarà com a dades el text xifrat i les freqüències trobades de les lletres en l'idioma i en el missatge. S'ha de cercar alguns criteris automàtics de substituir lletres amb freqüència similar i intercalar-los amb criteris manuals. 
 

 

Una variant d'aquest mètode de substitució consisteix en agrupar les lletres de dues en dues i substituir cada grup de dues lletres per un símbol que habitualment és un altre conjunt de dues lletres.
 
 

El primer que s'ha de fer per desxifrar un missatge xifrat amb aquest mètode és disposar d'una taula de freqüències de tots els parells de lletres. La primera part d'aquest projecte serà, per tant, construir un programa que permeti comptabilitzar aquestes freqüències pels 27x27=729 parelles possibles de dues lletres. S'ha de disposar abans d'un conjunt de textos suficients per tal d'obtenir unes dades significatives. Aquests textos estaran en format ASCII. Això es pot fer amb qualsevol processador de textos com Word o AmiPro.
 
 

Una vegada es disposi d'aquesta taula de freqüències, s'ha d'establir també una taula de freqüències dels parells de lletres del missatge xifrat. Això es farà amb el mateix programa anterior.
 
 

Després s'ha de fer un programa que permeti substituir unes seqüències de lletres per unes altres. Podeu establir, com en la proposta anterior, alguns criteris automàtics i  alternar-los amb criteris manuals. 
 
 

Evidentment falta un tercer programa que pugui xifrar un text amb aquest mètode. Aquest programa és necessari per tal d'obtenir un missatge a desxifrar. 
 
 

Busqueu formes d'indicar com fer aquesta substitució (fórmules de qualsevol forma), també és possible una correspondència a l'atzar.