Cours TC info polytechnique PC1

Sillion

Sujets

• informatique
• réseau
• réseaux

Informations

• Publié par: Sior
• Nombre de lectures: 79
• Langue: Français

Extrait

TC Informatique Le Tronc Commun d’informatique
PC N° 1 • Organisation
– 10 PC + 10 TD9 Novembre 2000
– Compositions HC (13/12) + CC (14/02/01)
– Projet info (~1000 lignes de code)
• François Sillion projet iMAGIS
• Supports
IMAG-INRIA Rhône-Alpes
– Polycopié Cori-Levy
• Patrick Gros projet VISTA
– Transparents PC
IRISA, Rennes
(http:w3.edu.polytechnique.fr/
profs/informatique/Francois.Sillion/TC)
– Bibliothèque
• Délégués
http://w3.edu.polytechnique.fr/informatique
PC 1 François Sillion 1 PC 1 François Sillion 2
1Algorithmique et Programmation Cursus d’informatique (1)
• Structures de données • Majeure Algèbre, Informatique et Applications
(automne 2001)– Listes, arbres, graphes, « tas »...
– 2 cours obligatoires :• Algorithmes fondamentaux
• Architecture du calcul– Tri, recherche
• Systèmes formels, calculabilité et complexité
– Parcours d’arbres, de graphes
• Imagerie tridimensionnelle
• Programmation
– 1 cours à choisir parmi :
– Langage Java • Bases de données
– Unix (ou machine personnelle) • Langages de programmation
– Bibliothèque graphique MacLib • Algèbre, arithmétique
(Philippe Chassignet) – 1 Enseignement d ’approfondissement parmi
• Modélisation des réseaux de communication• Utilisateur
• Composants programmables– Messagerie, WWW, etc.
• Géométrie et synthèse d ’images
• Automates finis
• Modularité, objets et types
PC 1 François Sillion 3 PC 1 François Sillion 4
2Cursus d’informatique (2) Moi-même
• Majeure d ’Informatique (printemps 2002)
– Initiation à C et ML • Directeur de recherche, INRIA
– 2 cours obligatoires :
• iMAGIS, Laboratoire GRAVIR/IMAG,
• Conception et analyse d ’algorithmes
http://www-imagis.imag.fr• Principes et programmation des systèmes
d ’exploitation • Thèmes de recherche (Image de Synthèse)
– 1 cours parmi : – Simulation de l ’éclairage
• Compilation – Visualisation interactive de grands volumes de
• Informatique distribuée données
– 1 cours parmi • Applications
• Informatique parallèle
– Simulation architecturale
• Composants programmables
– CAO, design
• Cryptologie
– Effets spéciaux cinéma, jeux vidéo• Images et vision
– Ondes radio• DEA
• Courriel: [e-mail]– Algorithmique
– Sémantique, Preuves et Programmation
– ...
PC 1 François Sillion 5 PC 1 François Sillion 6
3Algorithmique Programmation: Java
• Elements d’un problème informatique
– Structure de données ? • Langage récent (1994), Sun microsystems
– Algorithme ? • Principaux avantages
– Complexité ? – Typage fort
• Recherche d’un chemin dans le métro – Gestion automatique de la mémoire
www.sytadin.tm.fr • Mais aussi
– Orienté objet
– Multitâche (threads)
– Facilement distribué
– Gestion des erreurs (exceptions)
• Execution :
– Code intermédiaire : machine virtuelle
– Compilation (très récent)
– Sécurisation (Web)
PC 1 François Sillion 7 PC 1 François Sillion 8
4Le langage Java (1): variables Le Langage Java (2): instructions
• Types et déclarations • Simples
boolean b = true; // ou false expression;
char c = ‘ Z ’; declaration;
int n = 18; • Composées
double pi = 31.415e-1;
{ [ instr … ] }
int[] vecteur = {1,2,5,-4};
• Conditionnelle vecteur = new int[5];
if ( expr ) instr [else instr]String msg = "Bonjour";
• Boucles• Expressions
for ( expr1 ; expr2; expr3 ) instrc
while ( expr ) instrvecteur[0] = 2*pi - 0.1 // conversion
• Opérateursmsg + " !…" // surcharge
new type[tailleEntière] – Affectation: =
– Arithmétiques: + - * / %• Les types non scalaires sont manipulés par
– Comparaison: == (attention !!)référence
– Booléens: && || !
– Concaténation de chaînes: +
PC 1 François Sillion 9 PC 1 François Sillion 10
5Le Langage Java (4):
Le Langage Java (3): fonctions
Structure d'un programme
// Importation de modules externes• Fonctions
import java.io.*static typeRetour NomFonction( type1 var1,
type2 var2,
public class program… )
{{
// constantes et variables globalesdeclarations
static final int max = 100;instructions
return expression;
// fonctions}
static void FaitQuelqueChose( int p ... )
{ . . . }
• Procédures
= fonctions retournant void (rien) // point d'entrée
public static void main ( String[] arg )
{
…
}
}
PC 1 François Sillion 11 PC 1 François Sillion 12
6Le Langage Java (5): Un programme ultra simple :
Mise en œuvre Crible d'Eratosthène
public class crible
{
final int max = 100;
boolean EstPremier[] = new boolean [max];% javac program.java
% java program.class static void remplit ( int p )
{
int k = 2;
• Éxécute la fonction main() while ( k*p < max ) {
EstPremier[k*p] = false;• Autres classes nécéssaires sont recherchées dans le chemin
k++;défini par la variable CLASSPATH.
}
}
static void Initialise()• Quelques outils pratiques
{
for ( int i = 0 ; i < max ; ++i )
EstPremier[i] = true;
void system.out.print ( String ); }
public static void main ( String[] arg )void system.out.println ( String );
{
double Math.random (); int i;
Initialise();long Math.round ( double );
for ( i = 2 ; i < max ; ++i )
int Math.min ( int, int ); remplit(i);
for ( i = 1 ; i < max ; ++i )...
if ( EstPremier[i] )
writeln(i + "est premier");
}
}
PC 1 François Sillion 13 PC 1 François Sillion 14
7Enveloppe convexe Enveloppe convexe
PC 1 François Sillion 15 PC 1 François Sillion 16
8Algorithme du cordeau Algorithme du cordeau
PC 1 François Sillion 17 PC 1 François Sillion 18
9Enveloppe convexe : Enveloppe convexe :
Algorithme du cordeau Algorithme du cordeau
public class cordeau• Remarques
{
final static int max = 100;
static Point[] P = new Point[max+1];– La fonction Angle retourne une mesure de l'angle entre P[i]P[j] et l'horizontale.
Pas forcément l'angle lui-même…
static int wrap ( Point[] P, int max )– Échange de deux éléments du tableau :
{
int min = TrouveOrdonnéeMinimum();
static void Echange(int a, int b) // place une sentinelle
P[max] = P[min];{
double angle = 0;Point p = P[a];
for ( j=0 ; j < max ; ++j )
P[a] = P[b]; {
Echange(j,min);P[b] = p;
min = max; am = angle; angle = 360;}
for ( int k=j+1; k <= max; ++k )
– Nouvel objet if ( Angle( P[j], P[k] ) > am )
class Point if ( Angle ( P[j], P[k] ) < angle )
{{
min = k; angle = Angle(P[j],P[k]);
double x,y; }
} if ( min == max ) return j;
}
}
Point Pt = new Point(); }
Pt.x = 2.0; public static void main ( String[] arg )
{Point[] P = new Point[5]; Initialise();
int Nb = wrap ( P , max );
}
on verra qu'on peut définir des constructeurs…
}
PC 1 François Sillion 19 PC 1 François Sillion 20
10