12 files changed, 322 insertions, 0 deletions
diff --git a/sem_3/algo/tp1-done/PROG_TP1/mainTP1.cpp b/sem_3/algo/tp1-done/PROG_TP1/mainTP1.cpp
new file mode 100644
index 0000000..18d30ab
--- /dev/null
+++ b/sem_3/algo/tp1-done/PROG_TP1/mainTP1.cpp
@@ -0,0 +1,65 @@
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include "outilsTab.h"
+
+using namespace std;
+
+
+int main(int argc, char ** argv)
+{
+    int* Tab;
+    struct triplet res;
+    int sm, taille, q;
+    clock_t t1, t2;
+
+    srand(time(NULL));
+    printf("Numero de la question traitee (1/2/3/4) ? ");
+    scanf("%d",&q);
+    switch (q){
+        case 1 :
+            taille=1000;
+            Tab=genTab(taille);
+            t1=clock(); sm=ssTabSomMax1(Tab,taille); t2=clock();
+            cout << "\n Somme Max1 : " << sm << " tps : " <<  (double) (t2-t1)/  (double) CLOCKS_PER_SEC << endl;
+            t1=clock(); sm=ssTabSomMax2(Tab,taille); t2=clock();
+            cout << "\n Somme Max2 : " << sm << " tps : " <<  (double) (t2-t1)/  (double) CLOCKS_PER_SEC << endl;
+            t1=clock(); sm=ssTabSomMax3(Tab,taille); t2=clock();
+            cout << "\n Somme Max3 : " << sm << " tps : " <<  (double) (t2-t1)/  (double) CLOCKS_PER_SEC << endl;
+            t1=clock(); sm=ssTabSomMax4(Tab,taille); t2=clock();
+            cout << "\n Somme Max4 : " << sm << " tps : " <<  (double) (t2-t1)/  (double) CLOCKS_PER_SEC << endl;
+
+        break;
+        case 2 :
+            fichierTemps("sm1.dat", 1000, 100, ssTabSomMax1);
+            fichierTemps("sm2.dat", 1000, 100, ssTabSomMax2);
+            fichierTemps("sm3.dat", 1000, 100, ssTabSomMax3);
+            fichierTemps("sm4.dat", 1000, 100, ssTabSomMax4);
+            system("gnuplot trace1.gnu");
+            fichierTemps("sm2.dat", 20000, 1000, ssTabSomMax2);
+            fichierTemps("sm3.dat", 20000, 1000, ssTabSomMax3);
+            fichierTemps("sm4.dat", 20000, 1000, ssTabSomMax4);
+            system("gnuplot trace2.gnu");
+            fichierTemps("sm3.dat", 1000000, 100000, ssTabSomMax3);
+            fichierTemps("sm4.dat", 10000000, 1000000, ssTabSomMax4);
+            system("gnuplot trace3.gnu");
+       break;
+        case 3 :
+            Tab=genTab(20);
+            afficheTab(Tab,20);
+            res=indSsTabSomMax(Tab,20);
+            cout << "\n somme Max : " << res.somMax << "\n debut souTab : " << res.deb << "\n fin SouTab : " << res.fin << endl;
+        break;
+        case 4 :
+            Tab=genTab(20);
+            afficheTab(Tab,20);
+            rangerElemNeg(Tab,20);
+            afficheTab(Tab,20);
+        break;
+    }
+   return 0;
+}
+
diff --git a/sem_3/algo/tp1-done/PROG_TP1/outilsTab.cpp b/sem_3/algo/tp1-done/PROG_TP1/outilsTab.cpp
new file mode 100644
index 0000000..6643b13
--- /dev/null
+++ b/sem_3/algo/tp1-done/PROG_TP1/outilsTab.cpp
@@ -0,0 +1,131 @@
+#include <iostream>
+#include <fstream>
+
+#include <stdlib.h>  // pour rand
+#include <assert.h>
+#include "outilsTab.h"
+using namespace std;
+
+int* genTab(int n){
+    int* t; int i;
+    t=new int[n];
+    for (i=0;i<n;i++) t[i]=-100+rand()%200;
+    return t;
+}
+
+void afficheTab(int* T, int taille){
+    int i;
+    cout << "\n[ ";
+    for (i=0;i<taille;i++) cout << T[i] << " ";
+    cout << "]\n";
+    }
+
+void fichierTemps(const char* nomFic, int tMaxTab, int pas, int (*f)(int*, int)){
+    int taille;
+    int* Tab;
+    clock_t t1, t2;
+    ofstream fichier(nomFic,ios::out);
+
+    if (fichier)
+    {
+        for (taille=pas; taille<=tMaxTab; taille=taille+pas){
+            Tab=genTab(taille);
+            t1=clock();
+            (*f)(Tab,taille);
+            t2=clock();
+            fichier << taille <<" "<< (double)(t2-t1)/ CLOCKS_PER_SEC << endl;
+        }
+        fichier.close();
+    }
+    else cerr << " Problème ouverture fichier"<< endl;
+
+    return ;
+}
+
+int ssTabSomMax1(int* T, int taille){
+    int somMax, som, i, j, k;
+    somMax=0;
+    for (i=0;i<taille;i++){
+        for (j=i; j<taille; j++){
+            som=0;
+            for (k=i; k<=j; k++) {
+                som = som + T[k];
+            }
+            if (som > somMax) somMax = som;
+        }
+    }
+    return somMax;
+}
+
+int ssTabSomMax2(int* T, int taille){
+    int somMax, som, i, j;
+    somMax=0;
+    for (i=0;i<taille;i++){
+        som=0;
+        for (j=i; j<taille; j++){
+            som = som + T[j];
+            if (som > somMax) somMax = som;
+        }
+    }
+    return somMax;
+}
+
+int sTSM3(int* T,int g,int d){
+    int m, som, i, smgd, smdg, smm, smg, smd;
+    assert(g<=d);
+    if (g==d){
+        if (T[g]>0) return T[g]; else return 0;
+    }
+    else {
+        m = (d+g)/2;
+        smg=sTSM3(T,g,m);
+        smd=sTSM3(T,m+1,d);
+        smgd=0; som=0;
+        for (i=m;i>=g;i--){
+            som=som+T[i];
+            if (som > smgd) smgd=som;
+        }
+        smdg=0; som=0;
+        for(i=m+1;i<=d;i++){
+            som=som+T[i];
+            if (som>smdg) smdg=som;
+        }
+        smm=smgd+smdg;
+        if ((smg>=smd) && (smg>=smm)) return smg;
+        else {
+            if (smd>=smm) return smd;
+            else return smm;
+        }
+    }
+}
+
+int ssTabSomMax3(int* T, int taille){
+    return sTSM3(T,0,taille-1);
+}
+
+int ssTabSomMax4(int* T, int taille){
+    int ancienplusgrand = 0;
+    int somme =0;
+    for (int i =0; i < taille; i ++) {
+      somme+=T[i];
+      if (somme < 0 ){
+        somme= 0;
+    }
+    ancienplusgrand= ancienplusgrand> somme ? ancienplusgrand : somme;
+    }
+    return ancienplusgrand;
+}
+
+struct triplet indSsTabSomMax(int* T, int taille){
+/* A COMPLETER */
+    struct triplet  res;
+    res.somMax=0; res.deb=0; res.fin=0;
+    return res;
+}
+
+
+void rangerElemNeg(int* T,int taille){
+/* A COMPLETER */
+   return;
+
+}
diff --git a/sem_3/algo/tp1-done/PROG_TP1/outilsTab.h b/sem_3/algo/tp1-done/PROG_TP1/outilsTab.h
new file mode 100644
index 0000000..9576c28
--- /dev/null
+++ b/sem_3/algo/tp1-done/PROG_TP1/outilsTab.h
@@ -0,0 +1,74 @@
+#ifndef OUTILSTAB_H_INCLUDED
+#define OUTILSTAB_H_INCLUDED
+
+struct triplet {
+    int deb, fin, somMax;} ;
+
+int* genTab(int t);
+//    Renvoie un tableau de taille t, dont les éléments sont des entiers aléatoires compris entre -100 et 100
+
+
+void afficheTab(int* T, int t);
+//    Affiche les éléments de T, tableau d'entiers de taille t
+
+
+void fichierTemps(const char* nomFic, int tMaxTab, int pasTaille, int (*fssTabSomMax)(int*, int));
+//    Données nomFic une chaîne de caractères, tMaxTab et pasTaille 2 entiers positifs pasTaille < tMaxTab
+//            fssTabSomMax nom d'une fonction dont les données sont 1 tableau d'entiers et la taille de ce tableau et renvoyant 1 entier
+//    Resultat : crée un fichier de nom nomfic et pour chaque taille comprise entre pasTaille et tMaxTab (avec un pas de pasTaille),
+//               génère un tableau de cette taille
+//               execute la fonction ssTabSomMax sur ce tableau
+//               ajoute au fichier de nom nomfic la taille du tableau et le temps d'execution de ssTabSomMax
+
+
+int ssTabSomMax1(int* Tab, int n);
+/*
+    Données : Tab un tableau d'entiers de taille n
+    Resultat : renvoie la somme max des sous-tableaux de tab, algo de complexite O(n^3)
+*/
+
+int ssTabSomMax2(int*, int);
+
+/*
+    Données : Tab un tableau d'entiers de taille n
+    Resultat : renvoie la somme max des sous-tableaux de tab, algo de complexite O(n^2)
+*/
+
+int ssTabSomMax3(int* Tab, int n);
+/*
+    Données : Tab un tableau d'entiers de taille n
+    Resultat : renvoie la somme max des sous-tableaux de tab, algo de complexite O(n log n)
+*/
+
+int ssTabSomMax4(int* Tab, int n);
+/*
+    Données : Tab un tableau d'entiers de taille n
+    Resultat : renvoie la somme max des sous-tableaux de tab, algo de complexite O(n)
+    FONCTION A COMPLETER
+*/
+
+struct triplet indSsTabSomMax(int* Tab,int n);
+/*
+    Données : Tab un tableau d'entiers de taille n
+    Resultat : renvoie une structure contenant
+                    la somme max des sous-tableaux de tab,
+                    l'indice de début d'un sous-tableau de somme max
+                    l'indice de fin d'un sous-tableau de somme max
+                algo de complexite O(n)
+    FONCTION A COMPLETER
+
+*/
+
+
+void rangerElemNeg(int* Tab,int n);
+/*
+    Données : Tab un tableau d'entiers de taille n
+    Resultat : modifie le tableau Tab de sorte que tous les éléments négatifs soient placés avant tous les éléments positifs
+                algo de complexite O(n)
+    FONCTION A COMPLETER
+
+*/
+
+
+
+#endif /* OUTILSTAB_H_INCLUDED */
diff --git a/sem_3/algo/tp1-done/PROG_TP1/sm1.dat b/sem_3/algo/tp1-done/PROG_TP1/sm1.dat
new file mode 100644
index 0000000..6fe54af
--- /dev/null
+++ b/sem_3/algo/tp1-done/PROG_TP1/sm1.dat
@@ -0,0 +1,10 @@
+100 0
+200 0
+300 0.03125
+400 0.03125
+500 0.046875
+600 0.09375
+700 0.15625
+800 0.21875
+900 0.3125
+1000 0.4375
diff --git a/sem_3/algo/tp1-done/PROG_TP1/sm2.dat b/sem_3/algo/tp1-done/PROG_TP1/sm2.dat
new file mode 100644
index 0000000..79cda5f
--- /dev/null
+++ b/sem_3/algo/tp1-done/PROG_TP1/sm2.dat
@@ -0,0 +1,7 @@
+1000 0
+2000 0
+3000 0.015625
+4000 0.015625
+5000 0.03125
+6000 0.046875
+7000 0.0625
diff --git a/sem_3/algo/tp1-done/PROG_TP1/sm3.dat b/sem_3/algo/tp1-done/PROG_TP1/sm3.dat
new file mode 100644
index 0000000..811f1f9
--- /dev/null
+++ b/sem_3/algo/tp1-done/PROG_TP1/sm3.dat
@@ -0,0 +1,10 @@
+100 0
+200 0
+300 0
+400 0
+500 0
+600 0
+700 0
+800 0
+900 0
+1000 0
diff --git a/sem_3/algo/tp1-done/PROG_TP1/sm4.dat b/sem_3/algo/tp1-done/PROG_TP1/sm4.dat
new file mode 100644
index 0000000..811f1f9
--- /dev/null
+++ b/sem_3/algo/tp1-done/PROG_TP1/sm4.dat
@@ -0,0 +1,10 @@
+100 0
+200 0
+300 0
+400 0
+500 0
+600 0
+700 0
+800 0
+900 0
+1000 0
diff --git a/sem_3/algo/tp1-done/PROG_TP1/tp1 b/sem_3/algo/tp1-done/PROG_TP1/tp1
new file mode 100644
index 0000000..8cce618
--- /dev/null
+++ b/sem_3/algo/tp1-done/PROG_TP1/tp1
diff --git a/sem_3/algo/tp1-done/PROG_TP1/trace1.gnu b/sem_3/algo/tp1-done/PROG_TP1/trace1.gnu
new file mode 100644
index 0000000..a7f446a
--- /dev/null
+++ b/sem_3/algo/tp1-done/PROG_TP1/trace1.gnu
@@ -0,0 +1,5 @@
+set ylabel "secondes"
+plot "sm4.dat" with lines, "sm3.dat" with lines, "sm2.dat" with lines, "sm1.dat" with lines
+pause -1 "Appuyez sur RETURN pour continuer"
+exit
+
diff --git a/sem_3/algo/tp1-done/PROG_TP1/trace2.gnu b/sem_3/algo/tp1-done/PROG_TP1/trace2.gnu
new file mode 100644
index 0000000..ba4de89
--- /dev/null
+++ b/sem_3/algo/tp1-done/PROG_TP1/trace2.gnu
@@ -0,0 +1,5 @@
+set ylabel "secondes"
+plot "sm4.dat" with lines, "sm3.dat" with lines, "sm2.dat" with lines
+pause -1 "Appuyez sur RETURN pour continuer"
+exit
+
diff --git a/sem_3/algo/tp1-done/PROG_TP1/trace3.gnu b/sem_3/algo/tp1-done/PROG_TP1/trace3.gnu
new file mode 100644
index 0000000..1907656
--- /dev/null
+++ b/sem_3/algo/tp1-done/PROG_TP1/trace3.gnu
@@ -0,0 +1,5 @@
+set ylabel "secondes"
+plot "sm4.dat" with lines, "sm3.dat" with lines
+pause -1 "Appuyez sur RETURN pour continuer"
+exit
+
diff --git a/sem_3/algo/tp1-done/énoncéTP1.pdf b/sem_3/algo/tp1-done/énoncéTP1.pdf
new file mode 100644
index 0000000..bdd788a
--- /dev/null
+++ b/sem_3/algo/tp1-done/énoncéTP1.pdf