Seminari 2
Introducció als algorismes (I)

Bioinformàtica - 1er trimestre curs 2012/2013 - UPF

En el següent enllaç trobareu els apunts en format PDF corresponents a la part d'introducció als algorismes.

Aquest seminari introdueix el tema de la programació i el desenvolupament d'algorismes mitjançant el llenguatge de programació Perl. Els conceptes més importants que heu d'entendre són:

Exemple introductori

Un exemple recent de desenvolupament d'un programari (software) altament complexe ha estat el que ha fet possible l'aterratge autònom del vehicle de la NASA Curiosity al planeta Mart (intenteu entendre quantes línies de codi informàtic han arribat a programar per fer això possible):

Trobareu mes informació a la plana de la missió científica a Mart de la NASA.

Malgrat aquest es un exemple d'una tasca de programació informàtica altament complexa, els conceptes fonamentals sobre els que estan desenvolupats tots els programes que han fet possible aquesta l'aterratege autònom del Curiosity són els mateixos que veurem avui a classe.

Noció d'Algorisme

acció: és un aconteixement que té lloc en un periode de temps finit i produeix un resultat ben definit i previst.


el fet de que una acció duri un temps finit vol dir que es pot trobar l'instant del temps en què comença i l'instant del temps en què acaba.


informació: per tal de poder entendre el resultat de l'algorisme, és necessari que durant el temps entre l'instant en què comença l'algorisme i l'instant en què acaba, poguéssim observar o obtenir informació sobre el que està passant.


estat: el conjunt d'informació observat en un instant de temps donat (entre el principi i el final) s'anomena ''estat''.


algorisme: un algorisme és una seqüència d'accions que ens porta d'un estat inicial a un estat final en el qual obtenim el resultat.


la construcció d'un algorisme consisteix en descobrir quines accions elementals cal organitzar en el temps i, també, consisteix en escollir la forma d'organitzar-les per tal d'obtenir el resultat.


això requereix:


un programa és la implementació d'un algorisme en un llenguatge de programació determinat (per exemple el Perl).

Estructures algorísmiques bàsiques

constants: són valors explícits que no varien en el curs d'execució de l'algorisme. També es coneixen com a literals. Per exemple: 

1, 2, 10, 3.1416, ''hola''


variables: una variable és un nom associat a un espai a la memòria de l'ordinador on s'emmagatzema una constant o be una estructura de dades.


considerarem dues classes de variables: les variables singulars i les variables plurals.


les variables que anomenarem singulars seran aquelles que estan associades a un únic valor, mentre que les variables que anomenarem plurals seran aquelles que estan associades a dos o mes valors.


ens podem referir a una variable escrivint simplement el seu nom, com ara x, v o i. No obstant, sovint utilitzarem la notació del llenguatge Perl que distingeix explícitament el caràcter singular o plural d'una variable, de la següent forma:


direm que a una variable li assignem un valor quan especifiquem quin valor volem que prengui la variable. Exemples d'assignacions són: 

$a = 2
$a = 2 + 1
$a = $a + 1


expressions: anomenarem expressió a l'especificació sintàcticament correcta d'una o més operacions sobre un conjunt de variables, constants i funcions. Exemples d'expressions són: 

1 + 1
$a + 2
3 * log($a)
($a + $b) * 2

el conjunt d'operadors aritmètics en el llenguatge Perl és el següent:


Operador Exemple Resultat
Suma $a + $b suma de a i b
Resta $a - $b resta de a menys b
Multiplicació $a * $b producte de a i b
Divisió (quocient) $a / $b divisió de a per b
Divisió (residu, mòdul) $a % $b residu de dividir a per b

les expressions regulars són un tipus (no aritmètic) d'expressió.


la composició seqüencial: 

$a = 2;
$b = $a;
$b = $b + $a * 4;
print $b;

quin valor imprimirà l'algorisme anterior ?


operadors de comparació:


Comparació Numèrica Alfabètica
Igual == eq
No igual != ne
Més petit que < lt
Més gran que > gt
Més petit o igual que <= le
Més gran o igual que >= ge


la composició alternativa (o condicional): 

$a = 4;
$b = 7;
$c = ($a * $b) + 1;

if ($a % 2 == 0) {
  print "parell\n";
}
else {
  print "senar\n";
}

què imprimirà l'algorisme anterior, ''parell'' o ''senar'' ?


la composició iterativa: 

$i = 0;
$s = 0;
while ($i < 10) {
  $i = $i + 1;
  $s = $s + $i;
}
print $s;
què fa l'algorisme anterior ?

Tota composició iterativa compleix:

  1. una o més condicions inicials que corresponen a tot allò que és cert abans de començar a iterar.
  2. una o més condicions finals que corresponen a tot allò que és cert quan s'ha acabat d'iterar.
  3. una o més condicions invariants que corresponen a tot allò que no canvia durant l'execució de la composició iterativa.

L'especificació d'aquestes condicions és útil a l'hora d'entendre una composició iterativa o de dissenyar-ne una desde zero donat que,

Com ara, aquestes podrien ser les condicions inicials, finals i invariants de l'exemple anterior:

  1. condicions inicials: 1. abans de començar a comptar, no hem comptat res ($i=0;); 2. abans de començar a sumar no hem sumat res ($s=0;).
  2. condicions finals: 1. el darrer número que hem sumat és el 10 (per tant anirem iterant mentre $i < 10).
  3. condicions invariants: 1. el següent número a sumar és el número actual més 1 ($i = $i + 1;); 2. la suma següent és la suma actual més el número que toca sumar ($s = $s + 1;).

Disseny d'algorismes iteratius

vector: és un tipus de variable que pot emmagatzemar més d'un valor i que permet l'accés indexat dels seus valors. També es coneix sovint com a taula o array. Per exemple: 

@v = (1,2,3,4,5);

print $v[0];

emmagatzema a un vector que es diu ''v'' els valors de l'u al cinc, i la darrera instrucció imprimeix el primer valor del vector, es a dir un 1. Teniu en compte que els valors d'un vector van indexats des de la posició 0 fins a la n-1, per un vector amb n valors.


els algorismes iteratius consisteixen principalment d'un esquema algorísmic en el que una o més accions poden executar-se repetidament sense have d'especificar-les mes d'un cop. Per exemple, utilitzarem un algorisme iteratiu per sumar els valors d'un vector: 

@v = (1,2,3,4,5);
$i = 0;
$s = 0;

while ($i < 5) {
  $s = $s + $v[$i];
  $i = $i + 1;
}
print $s;


suposem que al vector ''v'' tenim una seqüència d'ADN i volem contar quants nucleòtids T hi ha en aquesta seqüència. Això es pot resoldre de la següent forma: 

  @v=('A','T','T','G','C','C','T','A');
  $i=0;
  $n=0;
  while ($i < 8) {
                                                                                
    if ($v[$i] eq 'T') {
      $n = $n + 1;
    }
                                                                                
    $i = $i + 1;
  }
  print "hi han ",$n," nucleotids T\n";

al programa anterior fem anar una composició alternativa amb una condició formada per una sola comparació alfanumèrica ($v[$i] eq 'T'). Si volguéssim contar el nombre de dinucleòtids TT necessitariem construir una expressió lògica formada per dues comparacions i un operador lògic de conjunció. Els operadors lògics en Perl són:

Operador Significat
cond1 && cond2 conjunció cond1 i cond2
cond1 || cond2 disjunció cond1 o cond2
!cond negació no cond

on cond, cond1 i cond2 fan referencia a condicions com ara: 

$a == 2

$v[$i] eq 'b'

$x != 3.5

$j >= 10

$v[0] ne ' '

etc..

el programa que ens contaria els dinucleòtids TT podria ser aquest: 

  @v=('A','T','T','G','C','C','T','A');
  $i=1;
  $n=0;
  while ($i < 8) {
                                                                                
    if ($v[$i] eq 'T' && $v[$i-1] eq 'T') {
      $n = $n + 1;
    }
                                                                                
    $i = $i + 1;
  }
  print "hi han ",$n," dinucleotids TT\n";

Exercicis

Intenteu fer per a la primera sessió de problemes (Seminari 5) els següents 4 exercicis que trobareu a les pàgines 9 i 10 dels apunts: 1.2, 1.3, 1.4, 1.6 i 1.7.