Un ordinateur est bête !
Le noyeau de l'ordinateur ne peux pas faire de tâche complexe.
- un bug = un problème lié à l'incompréhension d'un humain face à la machine
- un ordibnateur ne calcule que la memoire alloué.
- Nous sommes capable de reconnaître nos amis, notre famille de dos, car nous exécution pas comme un ordinateur, mais plus complexe. Un ordinateur est incapable de reconnaître un visage (l'inteligence artificiel n'utilise pas l'algorithmie pour la reconnaissance).
Exemple :
- Il ne peux pas faire de multiplication
- si 5*3 l'ordinateur ferra 5+5+5
Pour comprendre un ordinateur il faut être bête !
⚠ Un algorithme n'est pas une équation, mais une suite d'intruction
Algorithmie très vieux datant du 8e siècle qui se nomme AL KARWAZI qui donne Algorithmie.
Turing a imaginé la machine de Turing qui permet de résoudre pleins de problème mathématique.
Les ordinateur ce sont basé sur les machines de Turing avec des case d'instruction, de case et d’exécution.
Pour intervertir des valeurs je suis obligé d'utiliser une 3e variable.
Un trie en quick sort, est un trie rapide qui se base sur plusieurs fonction, de processus ce basant sur une médiane distribué à chaque fonction jusqua avoir une valeur par fonction.
Cas pratique
Pouvoir créer des sortes de recettes pour executer une tâche. Turing a Imaginer une machine :
- Des cases
Trier un jeu de carte :
3 méthodes proposé :
Proposition quick sort :
effectué plusieurs tâche en parallèle
Valeur médianne entre 1-5
et 5-10
le procésseur va donner la carte a que
Démontrer en Code
Méthode de Aimé :
pseudo code :
carte_trier[10] ={0,0,0,0,0,0,0,0,0,0}
carte_non_trier[10] = {7,6,10,9,3,4,2,1,5,8}
for i = 0 to i = 9
i++
carte_a_placer = carte_non_trier[i]
carte_a_trier[carte_a_placer - 1] = carte_a_la_place
# output
# 1ère iteration
# {0,0,0,0,0,0,7,0,0,0}
Pratique :
Méthode a bulle
Le tri à bulles ou tri par propagation1 est un algorithme de tri. Il consiste à comparer répétitivement les éléments consécutifs d'un tableau, et à les permuter lorsqu'ils sont mal triés. Il doit son nom au fait qu'il déplace rapidement les plus grands éléments en fin de tableau, comme des bulles d'air qui remonteraient rapidement à la surface d'un liquide.
def venant de wikipedia
python :
carte = [4,9,2,10,3,7,6,1,5,8]
def algo(i):
first_local = carte[i]
second_local = carte[i+1]
if first_local > second_local :
carte[i] = second_local
carte[i+1] = first_local
else:
carte[i] = first_local
i = i + 1
if __name__ == '__main__':
while carte != [1,2,3,4,5,6,7,8,9,10]:
for i in range(0,9):
algo(i)
print(carte)
Corection du professeur
Tableau_trier(taille_tableau)
je commence avec i = 0 et tant que i < taille_tableau alors incremente i de 1
case = tableau[i]
case_au _dessus = tabelau[i+1]
si case > case_au_dessus
alors retourne pas_trier
retourne tableau_trier
tant que Tableau_trier est faux
case_a_analyser = 0
je commence avec case_a_analyser = 0 et tant que i < taille_tableau alors incrémente i de 1
premiere_case = tableau[case_a_analyser]
deuxieme_case = tableau[case_a_analyser + 1]
si premiere_case > deuxieme_case
intervertir(premiere_case avec deuxieme_case) # on sais pas encore le faire
Méthode shaker
La différence entre cet algorithme et le tri à bulles est qu'il exécute un tri dans chaque direction à chaque passe le long de la liste à trier2. Cet algorithme de tri n'est que légèrement plus difficile à comprendre et à mettre en œuvre que le tri à bulles, et il résout en partie le problème des tortues du tri à bulles (les tortues sont les petits éléments situés près de la fin de la liste d'origine, qui ne remontent que très lentement, un emplacement par itération, vers leur emplacement définitif).
def venant de wikipedia
python :
carte = [4,9,2,10,3,7,6,1,5,8]
def up(i, y):
if carte[i] > carte[i+y] :
first_local = carte[i]
second_local = carte[i+y]
carte[i] = second_local
carte[i+y] = first_local
i = i + y
def down(i, y):
if carte[i] < carte[i+y] :
first_local = carte[i]
second_local = carte[i+y]
carte[i] = second_local
carte[i+y] = first_local
i = i + y
if __name__ == '__main__':
i = 0
while carte != [1,2,3,4,5,6,7,8,9,10]:
while i < 9:
up(i, 1)
i = i + 1
while i > 0:
down(i, -1)
i = i - 1
print(carte)
Correction professeur
pseudo code
caseEnCours = 0
caseSuivante = 0
caseAuBout = Faux
//je veux intervir deux case array[indice1] et array[indice2]
Fonction intervertir(array[],indice1,indice2)
temp = array[indice1]
array[indice1] = array[indice2]
array[indice2] = temp
//je parcours le tableau mais je ne peux pas sortir du tableau
Fonction parcoursTableau(array[] , step) //
caseAuBout = Faux
caseEnCours = caseEnCours + step //caseEnCours = caseEnCours + 1 = 1
si caseEnCours > taille(array[]) -1
caseEnCours = taille(array[]) -1
caseAuBout = Vrai
si caseEnCours < 0
caseEnCours = 0
caseAuBout = Vrai
//je remonte la carte la plus haute
Fonction remonteCartePlusHaute(array[]) {1,5,7,2}
X Tant que caseAuBout = Faux //tant que je n'ai pas parcouru tout mon tableau
X indice1 = caseEnCours
parcoursTableau(array, 1) //caseEnCours = 1
indice2 = caseEnCours
V si array[indice1] > array[indice2] alors
intervertir(array,indice1 , indice2 )
//je redescend la carte la plus base
Fonction redescendCartePlusBasse(array[])
Tant que caseAuBout = Faux //tant que je n'ai pas parcouru tout mon tableau
X indice1 = caseEnCours
parcoursTableau(array, -1) //caseEnCours = 1
indice2 = caseEnCours
V si array[indice1] < array[indice2] alors
intervertir(array,indice1 , indice2 )
//Est-ce que mon tableau est trier?
Fonction isArraySorted(array[])
tableauTrier = Vrai
Tant que caseAuBout = Faux
indice1 = caseEnCours
parcoursTableau(array, 1) //caseEnCours = 1
indice2 = caseEnCours
si array[indice1] > array[indice2] alors
tableauTrier = Faux
exit
//Je veux trier un jeu de carte
Fonction sort(array[])
//Est-ce que mon tableau est trier?
sorted = isArraySorted(array)
//tant que mon tableau est pas trier alors
tant que pas sorted
remonteCartePlusHaute(array)
redescendCartePlusBasse(array)
//j'affiche mon tableau
Méthode quick sort
Pour trier chaque carte nous créeon un arbre binaire. Le principe est de séparer chaque partie en la médiane (la moitier de chaque nombre). Puis nous repartissons chaque partie encore en la médianne.
-> jeux de couloir
Voir un autre post