|
Semaine du |
(très) bref résumé du cours |
algo |
|
2 oct. |
Evaluation d’algorithmes |
|
|
9 oct. |
Optimalité |
|
|
22 oct. |
Tri simple en O(n²)- En pire cas, tris en au
moins O(n log n) |
|
|
29 oct. |
Tri rapide (Quicksort). Evaluation pire cas et
meilleur cas |
|
|
5 nov.(2 cours) |
Evaluation en moyenne du tri rapide. Tri par
tas et son évaluation, tri fusion et son évaluation |
|
|
12 nov. |
Diviser pour régner |
Produit de matrice |
|
19 nov. |
Table de hachages |
- |
|
26 nov. |
Structures arborescentes : arbre k-aires,
arbre planaire généraux |
- |
|
3 dec. |
Implémentation et parcours |
|
|
10 dec. |
Arbre binaire de recherche, AVL |
|
|
17 dec. |
Algorithmes gloutons |
- |
|
7 jan. |
Recherche de motif |
- |
|
|
|
|
public class RecSeq {
private int t[];
public RecSeq (int T[])
{
this.t=T;
}
public int Recherche(int
w){
int j=0;
while (j<t.length && t[j]
!= w) j++;
if (j>=t.length) j=0;
return j;
}
public int Maximum(){
int m=t[0];
for(int j=1;j<t.length;j++)
if (t[j]>m)m=t[j];
return m;
}
}
et programme de test
import java.util.*;
public class progtest {
public static void main(String[]
args)
{
int [] T= new int [20];
// Generation par tirage aleatoire
d'un tableau T
//de 20 valeurscompris entre -999 et
999
Random rand = new Random ();
for(int i=0;i<T.length;i++)
{
T[i]=rand.nextInt()%1000;
System.out.print(T[i]);
System.out.print("
");
}
RecSeq tmp= new RecSeq(T);
// T[3] appartient il?
System.out.println(tmp.Recherche(T[3]));
// 2 appartient il?
System.out.println(tmp.Recherche(2));
// le maximum
System.out.print("le maximun
est:");
System.out.println(tmp.Maximum());
}
public class TriInsertion {
TriInsertion(int a[])
{
tri(a,0,a.length-1);
}
void tri(int a[], int deb, int fin)
{
for(int i=1;i<a.length;i++) {
int j=i;
int tmp=a[i];
while(j>0 && a[j-1] >tmp){
a[j]=a[j-1];
j--;
}
a[j]=tmp;
}
}
}
b.
Tri rapide(pour le tester class
ProgTest). Le pivot est le dernier élément du tableau
public class TriRapide {
TriRapide(int a[])
{
tri(a,0,a.length-1);
}
void tri(int a[], int deb, int fin)
{
if (deb >= fin) return;
else if (deb == fin -1){
if (a[deb]>a[fin]){
int aux=a[deb];
a[deb]=a[fin];
a[fin]=aux;
}
return;
}
int pivot
=a[fin];
int FIN=fin;
int DEB=deb;
while ( deb < fin) {
while (a[deb] <= pivot && deb< fin){ deb++;}
while (pivot <= a[fin] && deb <fin){ fin--;}
if (deb <fin ){
int aux=a[deb];
a[deb]=a[fin];
a[fin]=aux;
}
}
a[FIN]=a[fin];
a[fin]=pivot;
tri(a,DEB,deb-1);
tri(a,fin+1,FIN);
}
}
c.
Tri par tas (pour le tester class ProgTest)
public class TriTas {
TriTas(int a[])
{
tri(a,0,a.length-1);
}
void tri(int a[], int deb, int fin)
{
int n = a.length;
for(int k=n/2;k>0;k--){
FormeTas(a,k,n);
}
do {
int tmp = a[0];
a[0]=a[n-1];
a[n-1]=tmp;
n=n-1;
FormeTas(a,1,n);
} while(n>1);
}
void FormeTas(int a[],int k,int n){
int tmp=a[k-1];
while (k<=n/2)
{ int j = 2*k;
if(j<n && a[j-1]<a[j])j++;
if (tmp >= a[j-1]){
break;
}
else {
a[k-1]=a[j-1];
k=j;}
};
a [k-1]=tmp;
}
}
d.Tri fusion (pour
le tester class ProgTest). Implémentation utilisant un
tableau auxilliaire
public class TriFusion {
TriFusion(int a[])
{
tri(a,0,a.length-1);
}
void tri(int a[], int deb, int fin)
{
if (deb >= fin) {
return;
}
int mi = (deb + fin) / 2;
// Partition des listes et tri
recursif
tri(a,deb,mi);
tri(a, mi + 1, fin);
// Fusion de 2 listes tries
int [] aux= new int[a.length];
int i1 = deb;
int i2 = mi + 1;
int ind = deb;
while ((i1 <= mi) && (i2
<= fin)) {
if (a[i1]< a[i2]) {
aux[ind++]=a[i1++];
}
else
{ aux[ind++]=a[i2++];
}
}
while (i1 <= mi)
aux[ind++]=a[i1++];
while (i2 <= fin)
aux[ind++]=a[i2++];
for(ind=deb;ind <=fin;ind++)
a[ind]=aux[ind];
}
}
e. Pour tester ces
tris.
import java.util.*;
public class ProgTest {
public static void main(String[]
args)
{
int [] T= new int [20];
// Generation par tirage aleatoire
d'un tableau T
//de 20 valeurscompris entre -999 et
999
Random rand = new Random ();
for(int i=0;i<T.length;i++)
{
T[i]=rand.nextInt()%1000;
System.out.print(T[i]);
System.out.print("
");
}
System.out.println();
// decommenter le tri choisi
// TriFusion x= new TriFusion(T);
// TriRapide x= new TriRapide(T);
// TriInsertion x= new TriInsertion(T);
// TriTas x= new TriTas(T);
for(int i=0;i<T.length;i++)
{
System.out.print(T[i]);
System.out.print("
");
}
System.out.println();
}
}
3. Recherche dichotomique (le tableau est trié)
public class
RecDic {
private int t[];
public RecDic (int T[])
{
this.t=T;
}
public int Recherche(int w){
int deb = 0;
int fin= t.length - 1;
int mi;
while (deb <= fin){
mi=(deb + fin)/2;
if(t[mi] == w)return mi;
else
if (t[mi]<w) deb=mi+1;
else fin=mi-1;
}
return -1;
}
}
et le programme de test (utilise la classe TriRapide)
import java.util.*;
public class ProgTest2 {
public static void main(String[]
args)
{
int [] T= new int [20];
// Generation par tirage aleatoire
d'un tableau T
//de 20 valeurscompris entre -999 et
999
Random rand = new Random ();
for(int i=0;i<T.length;i++)
{
T[i]=rand.nextInt()%1000;
System.out.print(T[i]);
System.out.print("
");
}
System.out.println();
new TriRapide(T);
RecDic tmp= new RecDic(T);
// T[3] appartient il?
System.out.println(tmp.Recherche(T[3]));
// 2 appartient il?
System.out.println(tmp.Recherche(2));
}
}
//ARBRE GENERAL
import java.util.*;
class Noeud
{
private int valeur;
private Vector children = new Vector();
public Noeud () {}
public Noeud (int v) {
this.valeur=v;
}
public void setVal(int val) {
this.valeur = val;
}
public int getVal (){ return valeur;}
public Noeud getChild(int index) {
if (index >=degree() || index <0)
return null;
return (Noeud) children.elementAt(index);
}
public Noeud addChild(int val){
Noeud tmpNoeud = new Noeud(val);
children.addElement(tmpNoeud);return
tmpNoeud;
}
public Noeud addChild(int val, int index){
Noeud tmpNoeud = new Noeud(val);
children.insertElementAt(tmpNoeud,index);
return tmpNoeud;
}
public Noeud removeChild(int index) {
Noeud tmpNoeud = (Noeud)
children.elementAt(index);
children.removeElementAt(index);
return tmpNoeud;
}
public int degree(){
return children.size();
}
}
public
class ArbreGen {
public Noeud racine;
public ArbreGen () {
}
public ArbreGen (int v) {
this.racine = new Noeud(v);
}
public static void main (String[] args) {
//
Generation par tirage aleatoire de
//de 10
valeurs comprise entre -99 et 99
Random rand
= new Random ();
ArbreGen a=new
ArbreGen(rand.nextInt()%10); //la racine
System.out.println(a.racine.getVal());
a.racine.addChild(rand.nextInt()%10);//la
racine a 3 fils
System.out.print(a.racine.getChild(0).getVal()+
" " );
a.racine.addChild(rand.nextInt()%10);
System.out.print(a.racine.getChild(1).getVal()+
" " );
a.racine.addChild(rand.nextInt()%10);
System.out.println(a.racine.getChild(2).getVal()+
" " );
Noeud
tmp= a.racine.getChild(0);//le premier fils de la racine a 3 fils
tmp.addChild(rand.nextInt()%10);System.out.print(tmp.getChild(0).getVal()+
" " );
tmp.addChild(rand.nextInt()%10);System.out.print(tmp.getChild(1).getVal()+
" " );
tmp.addChild(rand.nextInt()%10);System.out.println(tmp.getChild(2).getVal());
tmp=
a.racine.getChild(1);//le second fils de la racine a 2 fils
tmp.addChild(rand.nextInt()%10);System.out.print(tmp.getChild(0).getVal()+
" ");
tmp.addChild(rand.nextInt()%10);System.out.println(tmp.getChild(1).getVal());
tmp=
a.racine.getChild(2);//le 3eme fils de l aracine a 3 fils
tmp.addChild(rand.nextInt()%10);System.out.print(tmp.getChild(0).getVal()+
" " );
tmp.addChild(rand.nextInt()%10);System.out.print(tmp.getChild(1).getVal()+
" " );
tmp.addChild(rand.nextInt()%10);System.out.println(tmp.getChild(2).getVal());
//parcours
en largeur
Enumeration
noeuds= a.largeur();
while
(noeuds.hasMoreElements()){
System.out.println(((Noeud) noeuds.nextElement()).getVal());
}
}
public Enumeration largeur() {
return(this.new Traversee());
}
class Traversee implements Enumeration {
private Vector noeuds;
public Traversee(){
noeuds= new Vector();
if (racine!= null)
noeuds.addElement(racine);
}
public boolean hasMoreElements(){
if (noeuds.size() ==0) return false;
return true;
}
public Object nextElement() {
Noeud tmp = (Noeud) noeuds.elementAt(0);
noeuds.removeElementAt(0);
for (int i=0;i <tmp.degree();i++)
noeuds.addElement(tmp.getChild(i));
return tmp;
}
}
}
import java.util.*;
class Noeud {
private int valeur;
private Noeud
fg,fd;
public Noeud () {}
public Noeud (int
v) {
this.valeur=v;
}
public void
setVal(int val) {
this.valeur = val;
}
public int getVal
(){ return valeur;}
public boolean afg(){
return(fg !=
null);
}
public
boolean afd(){
return(fd !=
null);
}
public Noeud
getfg(){
return fg;
}
public Noeud
getfd(){
return fd;
}
public Noeud addfg(int val){
Noeud tmp = new
Noeud(val);
fg=tmp;
return tmp;
}
public Noeud
addfd(int val){
Noeud tmp= new
Noeud(val);
fd= tmp;
return tmp;
}
public Noeud
removefg() {
Noeud tmpNoeud =
fg;
fg = null;;
return tmpNoeud;
}
public Noeud
removefd() {
Noeud tmpNoeud =
fd;
fd = null;
return tmpNoeud;
}
public int
Degree()
{int i=0;
if( fg!= null)
i++;
if (fd != null)
i++;
return i;
}
}
public class ArbreBin {
public Noeud
racine;
public ArbreBin ()
{
}
public ArbreBin (int
v) {
this.racine = new
Noeud(v);
}
public static void
main (String[] args) {
// Generation par tirage aleatoire de
//de
7 valeurs comprise entre -99 et 99
//
creation d'un arbre parfait
Random rand
= new Random ();
ArbreBin a=new ArbreBin(rand.nextInt()%10);
//la racine
System.out.println(a.racine.getVal());
a.racine.addfg(rand.nextInt()%10);//la
racine a 2 fils
System.out.print(a.racine.getfg().getVal()+
" " );
a.racine.addfd(rand.nextInt()%10);
System.out.println(a.racine.getfd().getVal());
Noeud tmp= a.racine.getfg();//le premier fils de la
racine a 2 fils
tmp.addfg(rand.nextInt()%10);System.out.print(tmp.getfg().getVal()+
" " );
tmp.addfd(rand.nextInt()%10);System.out.println(tmp.getfd().getVal());
tmp= a.racine.getfd();//le second fils de la racine a 2
fils
tmp.addfg(rand.nextInt()%10);System.out.print(tmp.getfg().getVal()+
" ");
tmp.addfd(rand.nextInt()%10);System.out.println(tmp.getfd().getVal());
//parcours en largeur
Enumeration
noeuds= a.largeur();
while
(noeuds.hasMoreElements()){
System.out.print(((Noeud)
noeuds.nextElement()).getVal()+ " ");
};
System.out.println();
//parcours prefixe
noeuds= a.prefixe();
while
(noeuds.hasMoreElements()){
System.out.print(((Noeud)
noeuds.nextElement()).getVal()+ " ");
}
System.out.println();
a.parcourspref(a.racine);
System.out.println();
System.out.println();
noeuds=
a.interne();
while
(noeuds.hasMoreElements()){
System.out.print(((Noeud) noeuds.nextElement()).getVal()+
" ");
}
System.out.println();
a.parcoursint(a.racine);
System.out.println();
System.out.println();
a.parcourspost(a.racine);
System.out.println();
}
public void parcourspref(Noeud rac){
if (rac != null) {
System.out.print(rac.getVal()+ " ");
parcourspref(rac.getfg());
parcourspref(rac.getfd());
}
}
public void parcoursint(Noeud rac){
if (rac != null) {
parcoursint(rac.getfg());
System.out.print(rac.getVal()+ " ");
parcoursint(rac.getfd());
}
}
public void parcourspost(Noeud rac){
if (rac != null) {
parcourspost(rac.getfg());
parcourspost(rac.getfd());
System.out.print(rac.getVal()+ " ");
}
}
public Enumeration largeur() {
return(this.new Traversee());
}
class Traversee implements Enumeration {
private Vector noeuds;
public Traversee(){
noeuds= new Vector();
if (racine!= null)
noeuds.addElement(racine);
}
public boolean hasMoreElements(){
if (noeuds.size() ==0) return false;
return true;
}
public Object nextElement() {
Noeud tmp = (Noeud) noeuds.elementAt(0);
noeuds.removeElementAt(0);
if (tmp.afg()) noeuds.addElement(tmp.getfg());
if (tmp.afd()) noeuds.addElement(tmp.getfd());
return tmp;
}
}
public Enumeration prefixe() {
return(this.new PreTraversee());
}
class PreTraversee implements Enumeration
{
private Vector noeuds;
public PreTraversee(){
noeuds= new Vector();
if (racine!= null)
noeuds.addElement(racine);
}
public boolean hasMoreElements(){
if (noeuds.size() ==0) return false;
return true;
}
public Object nextElement() {
Noeud tmp = (Noeud) noeuds.elementAt(0);
noeuds.removeElementAt(0);
if (tmp.afd()) noeuds.insertElementAt(tmp.getfd(),0 );
if (tmp.afg()) noeuds.insertElementAt(tmp.getfg(),0);
return tmp;
}
}
public Enumeration interne() {
return(this.new InTraversee());
}
class InTraversee implements Enumeration
{
private Vector noeuds;
public InTraversee(){
noeuds= new Vector();
if (racine!= null){
Noeud tmp = racine;
do {
noeuds.insertElementAt(tmp,0 );
tmp= tmp.getfg();
}
while(tmp !=null);
}
}
public boolean hasMoreElements(){
if (noeuds.size() ==0) return false;
return true;
}
public Object nextElement() {
Noeud courant = (Noeud)
noeuds.elementAt(0);
noeuds.removeElementAt(0);
if (courant.afd()) {
Noeud tmp= courant.getfd();
do {
noeuds.insertElementAt(tmp,0);
tmp=tmp.getfg();
} while(tmp != null);
}
return courant;
}
}
}
// Arbre binaire de recherche d'entiers
class Noeud
{
....
}
public
class Arbre {
....
// Insertion recursive
public Noeud insere(int v, Noeud a){
if (a == null){
a = new Noeud(v);
return(a);
}
else {if (v <= a.valeur)
a.fg=insere(v, a.fg);
else
a.fd=insere(v, a.fd);
return(a);
}
}
// Recherche
minimum d'un arbre
public
Noeud minimum(Noeud a){
if (a == null)
return(null);
else
if (a.fg == null)
return (a);
else
return(minimum(a.fg));
}
// Suppression
recursive d'un noeud
Noeud
supprimer(int v, Noeud r)
{
if (r==null)
return (null);
else
{if (r.valeur==v)
{r=supprimer_tete(r);
return (r);
}
else
{if (r.valeur>v)
r.fg=supprimer(v, r.fg);
else
r.fd=supprimer(v,
r.fd);
return(r);
}
}
}
// suppression
de la racine de l'arbre
Noeud
supprimer_tete(Noeud a)
{
if (a==null)
return(null);
else
{if ((a.fg==null) &&
(a.fd==null))
{a=null;
return (a);
}
else
{if (a.fg==null)
{a=a.fd;
return(a);
}
else
{if (a.fd==null)
{return(a);
}
else
//
remplacer par le minimum du sous arbre droit
{if
((a.fd.fg==null) && (a.fd.fd==null))
{a.valeur=a.fd.valeur;
a.fd=null;
return (a);
}
else
// trouver le minimum du sous-arbre droit
{Noeud m =
new Noeud();
m=minimum(a.fd);
a.valeur=m.valeur;
a.fd=supprimer(m.valeur,a.fd);
return(a);
}
}
}
}
}
}
....
}