Initiation à la programmation
La programmation est un outils informatique permettant l'écriture et la réalisation
de logiciels informatiques. Je pense qu'aujourd'hui cet outil devient très important voir indispensable pour nos quotidiens. Donc si vous voulez être à la mode mettez vous à la programmation!
Plan du cours
- 1 Introduction
- 2 Algorithmique et exemples
- 2.1 Qu'est ce qu'un algrorithme?
- 2.2 Compléxité d'un algorithme
- 2.3 Premiers exemples
- 3 Langages C
- 3.1 Connaissances de base et contenu d'un programme en C
- 3.2 Les différents type de données en C
- 3.3 Les déclarations (locales et globales)
- 3.4 Premiers Exemples
- 3.5 Boucles (while, for)
- 3.6 Conditionnement (if, else, switch, break, continue, retirn, exit)
- 3.7 La Récursivité
- 3.8 Les Tableaux et les Pointeurs
- 3.9 Les structures et les Unions
- 3.10 La bibliothèque GMP et les grands nombres
- 3.11 Le compilateur GCC
- 3.8.5 Exemples complets et detaillés
- 4 Langage C++
Initiation a la programmation
1 Introduction
La programmation se fait en trois étapes:
- L'algorithmique:
Définir le but du programme et la procédure à suivre.
Préciser les entrées fournis à l'algorithme et les sorties fournis par ce dernier.Exemple: Nous allons écrire l'algorithme RechercheMax qui permet de trouver le maximum de n entiers. / Procédure: Recherche du maximum d'une liste de n entiers. / Entrées : n entiers dans un tableau. / Sorties : un entier Max. procédure RechercheMax(Entrées t : Tableau[1..n] d'entiers, Sorties: Max) Déclaration i Max : Entier naturels début pour i allant de 0 à n-1 faire si t[i]>t[i+1] alors echanger(t[i+1],t[i]) fin si fin pour Max=t[n] retourner(Max) fin
Explication: C'est une simple comparaison; si le premier entier est plus grand que le second nous échangeons leur valeurs, puis nous comparons le dexième entier (qui est maintenant le max du premier et du deuxieme) avec le troisième et ainsi de suite nous parcourrons toute la liste. Le dernier élément du tableau est l'élément maximale! - Le codage:
Maintenant que notre algorithme est écrit nous pouvons le coder, pour cela nous avons une large gamme de langages de programmation. Dans mes cours nous allons voir le C, le C++ et le Java.
En C, l'algorithme ci-dessus se traduit comme suit:void RechercheMax(t[n]) { int i, Max; for(i=0;i< n;i++) { if(t[i]>t[i+1]){ echanger(t[i],t[i+1]);} } Max=t[n-1]; return(Max); }J'ai, bien évidemment utilisé une fonction que je n'ai pas éxplicité, c'est la fonction "echanger". Dans mes cours je reviendrais à tout les détails mais pour le moment je ne fais qu'introduire des notions de base! - La compilation: Dans la majorité des situations, un programme ne peut être utilisé dans son état brut. Il faudra le compiler pour qu'il soit utilisable! Vous pourrez utiliser le compilateur de votre choix, en ce qui concerne mes cours j'utiliserais le gcc.
2 Algorithmique et exemples
2.1 Qu'est ce qu'un algrorithme?
Un Algorithme est un ensemble d'intructions determinant une méthode qui, en utilisant des données, fournit un résultat voulu. On peut imaginer un mixeur par exemple;Entrées: Persil, tomates, oignons, blés concassés. Sortie : Taboulé Libanais!!
Un ordinateur ne pourrait pas fonctionner sans les algorithmes, ce sont eux qui lui disent quoi faire. Quand vous tapez sur votre clavier, un algorithme implementé dans votre machine donne l'ordre à l'ordinateur d'afficher ce que vous aviez demandé. Aujourd'hui tout fonctionne grace aux algorithmes: Calcul des salaires, notes des élèves, ...
2.2 Compléxité d'un algorithme
Un algorithme interréssant doit rapide et pas cher. A quoi servirait un algorithme qui met 30 minutes pour s'éxecuter? Personne n'utiliserais Google ou une quelconque autre fonction de recherche s'il faut attendre des minutes!! Un programmeur doit penser à optimiser son programme de sorte qu'il ait le minimum possible d'operations et d'utilisation mémoire.
La complexité algorithmique est la mesure de l'efficacité d'un algorithme. Elle dépend, principalement de deux quantités: le nombre d'instruction ou opérations (+, -, x, /, comparaison, affectation, ..) et la mémoire utilisée ( pour la taille d'un tableau par exemple). Prenons à titre d'exemple un algorithme de base:Affiche(Entrée: tableau de n entiers) debut Pour i allant de 1 à n afficher(tableau[i]) fin pour fin
La complexité de cet algorithme est f(n)=n c'est le nombre des opérations effectué par cet algorithme!
Il faut noter que la compléxité devient interraissant pour des algorithme ayant un grand nombre d'opération, et c'est là où la différence se joue. Nous verrons l'exemple de l'exponentiation rapide, et la difference en cout de temps avec l'exponentiation basique.
En Mathématique la compléxité se note par Ο(g(n)), je vous donne une petite explication pour bien assimiler cette notation:
Soit f(n) le nombre d'operation qu'utilise un algorithme. On dit que le temps mis par un programme pour s'executer est Ο(g(n)) si ∃ M et a tels que pour n>a on ait f(n)≤ Mg(n) Par exemple si f(n)=(1/3)n+1, prenons a=3/2 et M=1. En dessinant les graphe de la droite y=(1/3)x+1 et celle de y=x, a est l'abscisse de l'intersection, et nous obtenons, pour g(n)=n et a=3/2, f(n)≤ Mg(n)
