1.1)

entier Min[1..k]
booléen Trouvé[1..n]
pour j de 1 à n
  Trouvé[j] <- faux
pour i de 1 à k
  min <- +oo // c'est-à-dire, le plus grand entier représentable
  argmin <- -1
  pour j de 1 a n
    si non Trouvé[j]
	  si T[j] <= min
	    min <- T[j]
		argmin <- j
  Min[i] <- min
  Trouvé[argmin] <- vrai

1.2)

Tri(T)
entier Min[1..k]
pour i de 1 à k
  Min[i] <- T[i]
  
1.3)
Le premier algorithme fait  n + kn  opérations ;
le deuxième en fait n log(n) + k.
Si k << n, le premier algorithme est plus performant, avec un nombre d'opérations O(n), contre O(n log(n)) du deuxième.
Par contre, si k ~ n, le deuxième est plus performant, O(n log(n)), vis-à-vis de O(n^2) du premier.

2) Logarithmes

2.1) log_2(n)
2.2) i, log_2(n) et 32 respectivement
2.3) 

3) Le juste prix

Stratégie: on commence avec un interval de nombres possibles [bottom, top], où bottom = 1 et top = 1000 ;
à chaque essai, on propose le nombre middle = (bottom + top)/2 ; si le voisin dit que le nombre qu'il a
choisi est supérieur, bottom <- middle ; s'il dit que le nombre est inférieur, top <- middle.
De cette façon, il faudra log(1000) essais dans le pire cas pour deviner. Comme 1024 = 2^10, on peut affirmer
que 10 essais devraient suffir. Par contre, en choisissant n nombres au hazard, la probabilité de deviner
sera de p(n) = 1 - 0.999^n (c'est-à-dire, 1 - la probabilité qu'aucun des nombres choisis soit le juste) ;
pour n << 1000, p(n) ~ n/1000 : p(10) = 0.01, p(20) = 0.02, p(50) = 0.0488.
Si, par contre, on suppose que les n nombres choisis soient tous distincts, p(n) est exactement n/1000.
Donc, dans le pire cas, il faut choisir tous les 1000 nombres, c'est-à-dire, faire 1000 essais, 100 fois
le nombre d'essais de la stratégie optimale.

4) Dynamic Array

- version mémoire

t <- ALLOUER(n)
i <- 0
répéter
	nb <- GÉNÉRATEUR()
	si nb != -1
		si i >= n
			s <- ALLOUER(2 * n)
			pour j de 0 à i - 1
				Mem[s + j] <- Mem[t + j] // recopie des i éléments
			n <- 2 * n
			t <- s
		Mem[t + i] <- nb
		i <- i + 1
tant que nb != -1
// n cases allouées, i éléments pertinents

- version à la C

      T <- ALLOUER(n)
      i <- 1
      nb <- GÉNÉRATEUR()
      tantque nb != -1 {
	si i = n+1 {
	  Tbis <- ALLOUER(2 * n)
	  recopie(Tbis, T, n) // recopie des n éléments
	  n <- n * 2
	  T <- Tbis
	}
	T[i] <- nb
	i <- i + 1
	nb <- GÉNÉRATEUR()
      }
      // n cases allouées, i-1 éléments pertinents