INFO719 : rappels d'algorithmique et programmation C

Ce wiki est un complément de cours pour le cours "info-719 : rappels d'algorithmique et programmation C". La participation au wiki n'est pas obligatoire mais fortement encouragée. Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Vous pouvez aller voir ce guide pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

Détails techniques

Nouvelles

Les nouvelles récentes sont en haut de la liste...

• Hyvernat 12 septembre 2008 à 15:43 (CEST) : création du wiki

Organisation des séances

Comme vous n'êtes pas nombreux, le cours sera entièrement en mode cours / TD.

• première séance (12/09/2008) : introduction, calcul du maximum,
• deuxième séance (16/09/2008) : introduction au C (partie I), début du TD1,
• troisième séance (23/09/2008) : TP0 (reprise du TD1 en salle machines),

Les support de TD et TP

• TD1

• TP0

• Compléments pour le TP 0 :
  • Pour compiler un programme, allez voir la page Comment compiler le C ?
  • Pour faire du C chez vous, vous pouvez :
    • soit installer linux (je vous conseille Ubuntu)
    • soit installer une "émulation Unix" pour Windows (Cygwin, en précisant à l'installation que vous voulez installer au moins gcc, gdb et make dans la partie Devel)
    • soit installer un environnement de programmation C pour Windows (par exemple, Dev-C++)

Correction TDP0

• Question 3 : Ecrire une fonction sui renverse l'ordre des elements d'un tableau sans le recopier

/* Fonction renverse */
int renverse (int T[10]) {
	int tmp;
	int i;

	for (i=0;i<10/2;i=i+1){
		tmp=T[i];
		T[i]=T[10-i-1];
		T[10-i-1]=tmp;
	}
	return 1;
}


/* permet d'afficher les valeurs du tableau dans le terminal */
int affiche_tableau(int T[10]) {
	int i;

	for (i = 0; i < 10; i=i+1) {
		printf("T[%d]=%d\n",i,T[i]);
	}
	return 1 ;
} 


/* Programme principal */
int main () {
	int T[10]={20,15,78,56,69,24,18,14,47,11};
	
	affiche_tableau(T);
	printf("Son tableau renversé est: \n");
	
	renverse(T);
	affiche_tableau(T);

	return 1;
} 

• Question 4 : Ecrire un test pour verifier si u tableau est un palindrome. Si c'est le cas, il devra renvoyer la valeur 0; sinon, il devra renvoyer la plus grande valeur longueur du prefixe qu'on retrouve inversé en suffixe du tableau.

/* Fonction palindrome*/
int palindrome (int T[10]){ 
	int i;

	for (i=0;i<10/2;i=i+1){
		if (T[i] != T[10-i-1])
		{return i+1;}
	}
    return 0;
}

/* permet de taper les 10 valeurs dans le terminal et de les afficher */
int lire_tableau(int T[10]) { 
	int i;

	for (i = 0; i < 10; i=i+1) {
		printf("T[%d]= ",i);
		scanf("%d",&(T[i]));
	}
	return 1;
} 

/* Programme principal*/
int main () {
	int T[10];
	int x;
	
       lire_tableau(T);
	x=palindrome(T);	
	
       if (x==0)
		{printf("Le tableau est un palindrome. \n");}
	else
		{printf("La plus grande valeur longueur du prefixe est %i. \n",x-1);}
	return 1;
}

---

---

Introduction

Objectifs

• mettre tout le monde à niveau sur les compétences de base en algorithmique
• donner des notions de base sur l'informatique concrète
• Étudier quelques techniques importantes d'algorithmique
• apprendre les bases du langage C

Plan

• intro, étude d'un exemple
• rappel d'algorithmique (probablement faits en TD)
• rappel mathématiques, complexité
• quelques techniques d'algorithmique
• notions de complexité

• le langage C

Rappels historiques

Vous pouvez partir de cette page pour avoir un peu plus de détails...

La préhistoire : le calcul

• le boulier chinois
• la pascaline de Pascal, inventée en 1641/42 : elle ne permet de faire que des additions (et des soustractions
• Leibniz rajoute la multiplication à la pascaline (1673)
• les "moulins à chiffres" de Charles Babbage (1834-36), malheureusement jamais construits...
• la "tabulating business machine" de Hollerith permet d'automatiser les calculs pour le recensement de la population américaine. Ceci donnera ensuite la société "international business machine" (IBM).
• l'apparition du relais électromécanique (1900) d'une fréquence de 100 Hz, permet la construction du Harvard Mark I en 1944

Les programmes et instructions

• les orgues de Barbarie
• les métiers à tisser de Vaucanson et Jacquard (1801)

Les ordinateurs "modernes"

• l'invention du tube à vide permet le développements d'ordinateurs entièrement électroniques : l'ENIAC en est le premier exemplaire (1946) ; il pèse environ 30 tonnes...
• la machine de Turing (ordinateur théorique)
• le Manchester Mark I (1948) et l'EDVAC (1951) améliorent l'ENIAC et commencent à ressembler à des ordinateurs modernes
• l'UNIVAC I est le premier ordinateur commercialisé, en 1951.

Rappels d'algorithmique

Un exemple

Exercice : écrivez un programme qui fait la chose suivante : on dispose d'un tableau d'entier T de taille n. L'élément i du tableau est noté T[i]. On veut modifier T en interchangeant le plus petit et le plus grand élément.

Solution possible

int i=0
int max=0   /* indice du maximum */
int min=0   /* indice du minimum */

if (n==0) then  exit  /* est-ce que le tableau est vide ? */

for i:=0 to n-1                /* j'ai pris la convention du C : les tableaux commencent à l'indice 0 */
  if T[i] < T[min] then min:=i
  if T[i] > T[max] then max:=i
end

i:=T[min]
T[min] := T[max]
T[max] := i

exit

Exercice : écrivez un algorithme pour chercher les deux éléments maximaux d'un tableau

Solution possible

à faire

Exercice : écrivez un algorithme pour chercher l'élément maximal, ainsi que celui qui est juste en dessous (strictement). Par rapport à la question précédente, la différence ne se voit que si l'élément maximal apparaît plusieurs fois dans le tableau.

Solution possible

à faire

Le langage C, partie 1

Un exemple caractéristique :

/* « ouverture » des bibliothèques utilisées */
#include <stdio.h>

/* première fonction : elle prend deux entiers en argument et renvoie un entier */
int minimum (int n, int m) {
  if (n<m) { return(n); }
  else  { return(m); }
}

/* la fonction principale */
int main () {
  int i=42,x;  /* i et x sont deux variables entières */
  int j;
  j=24;
  x=minimum(i,j*2);
  printf("Le minimum de %i et %i est %i.\n", i, j*2, x);
  return(1);
}

Quelques points importants :

• il faut explicitement déclarer les bibliothèques utilisées,
• on n'est pas obligé d'avoir des fonctions autre que la fonction main, mais les fonctions doivent être déclarées dans l'ordre
• la fonction main est obligatoire, et il est conseillé de lui donné le type de retour int.

• une variable ne « vit » qu'à l'intérieur du bloc { ... } dans lequel elle est déclarée
• les variables ne sont pas initialisées automatiquement à 0

Pour la syntaxe de base et des exemples concernant les conditions et les boucles, reportez-vous au chapitre « les bases » et « les tableaux » du polycopié de Bernard Cassagne.

Références

• "The C programming language", de Kernighan et Ritchie,
• « Le langage C », version française du précédent,
• le polycopié de Bernard Cassagne, disponible ici, au format html (en ligne) ou pdf,
• « Programmation C », un livre collaboratif sur le mode Wikipedia, disponible ici.