Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

UNIVERSITE ADVENTISTE ZURCHER Département de l’Informatique DESCRIPTIF & SYLLAB

UNIVERSITE ADVENTISTE ZURCHER Département de l’Informatique DESCRIPTIF & SYLLABUS Pour le cours de Logique Et Algorithme INAL 211 2021 Enseignant : Dr Rindra RAKOTOMAHEFA Dr Rindra Rakotomahefa Logique et Algorithme | 2021 - 2 UNIVERSITE ADVENTISTE ZURCHER Département de l’Informatique Descriptif du cours INAL 211 – Logique et Algorithme Premier semestre, Année académique 2021 Information concernant le cours Heures créditées : Trois Prérequis : - UE : Algorithmes ECUE : INAL 211 – Logique et Algorithme Enseignant : Dr Rindra Rakotomahefa Mail : rindrarakotomahefa@zurcher.edu.mg Contact : 034 07 056 20 – 033 08 641 91 Facebook : Thylacine Doux Langue : Français Heures de classe : Mardi de 08h10 à 10h Description du cours et Objectifs visés Ce cours initie les étudiants à la méthodologie de la programmation. Ils apprennent à analyser les problèmes et à les résoudre en utilisant la démarche prescrite. À la fin du semestre, l'étudiant pourrait : • Avoir les connaissances en matière de logique pour traiter un problème informatique • Connaître tous les symboles utilisés pour la construction d’un diagramme de succession des tâches et actions • Ecrire un algorithme pour résoudre un problème informatique • Ecrire les pseudocodes correspondant à un algorithme • Construire le diagramme correspondant aux pseudocodes • Maitriser la méthode de base pour résoudre un problème informatique Contenu du cours Partie 1 : Notion de logique Chapitre 1 : Vocabulaire usuel a. Axiome b. Proposition c. Théorème d. Corollaire e. Lemme f. Conjecture g. Définition Chapitre 2 : Calculs propositionnels a. Négation d’une proposition b. Les connecteurs logiques c. L’implication logique d. L’équivalence logique e. Les quantificateurs Dr Rindra Rakotomahefa Logique et Algorithme | 2021 - 3 Partie 2 : Méthodologie de la programmation Chapitre 1 : Introduction a. Terminologies b. Symboles utilisés c. Principe de construction d’un diagramme Chapitre 2 : Résolution d’un problème a. Principe de résolution d’un problème b. Algorithmes c. Pseudocodes Chapitre 3 : Types de processus a. Processus séquentiel b. Processus conditionnel c. Processus à tâches répétitives Chapitre 4 : Modules prédéfinies Exigence du cours Durant le semestre, l’étudiant doit faire/rendre/passer : - Quatre (04) tests - Quatre (04) projets/recherches - Un examen (01) mi-semestriel - Un examen (01) final Système de notation L’évaluation des performances des étudiants prend en compte les notes des tests, des projets et des examens et dont la répartition et la suivante : Tests ................................................. 10% Projets............................................... 20% Examen mi-semestriel ....................... 30% Examen final ..................................... 40% Références bibliographiques : - J. Vélu : Méthodes mathématiques pour l'informatique (Dunod, 2000, 4ème édition) - Tous les ouvrages concernant la logique Intégration de la foi L’importance de la capacité de choisir et de décider. Les avantages de l’obéissance aux instructions. Eléments de pédagogie : Ils consistent en un cours théorique complété par des séances de travaux dirigés. Le cours théorique est une initiation aux fondements méthodologiques. Il est assorti d'exemples destinés à illustrer les principes. La participation active des étudiants au cours devrait permettre à eux de pouvoir pleinement profiter des travaux dirigés qui complètent le cours théorique et d'être pris dans une démarche de recherche. Les travaux dirigés reposent sur un recueil d'exercices. Dr Rindra Rakotomahefa Logique et Algorithme | 2021 - 4 Plan du cours Date Activité Exigence 09 février 2021 Partie 1 : Notion de la logique 16 février 2021 Chapitre 1 : Vocabulaire usuel Projet/recherche #1 23 février 2021 Chapitre 2 : Calculs propositionnels 02 mars 2021 Partie 2 : Méthodologie Chapitre 1 : Introduction Chapitre 2 : Résolution d’un problème Test #1 09 mars 2021 Chapitre 3 : Types de processus a. Processus séquentiel Test #2 16 mars 2021 b. Processus conditionnel Projet/recherche #2 23 mars 2021 b. Processus conditionnel (suite) 30 mars 2021 Semaine d’examen Examen semestriel 06 avril 2021 Correction de l’examen b. Processus conditionnel (suite) 13 avril 2021 c. Processus répétitif Test #3 20 avril 2021 c. Processus répétitif (suite) Projet/recherche #3 27 avril 2021 c. Processus répétitif (suite) 04 mai 2021 c. Processus répétitif (suite) Test #4 11 mai 2021 Chapitre 4 : Modules prédéfinies 18 mai 2021 Récapitulation et synthèse Projet/recherche #4 25 mai 2021 Préparation & semaine d'examen final Examen final Dr Rindra Rakotomahefa Logique et Algorithme | 2021 - 5 Logique – Vocabulaire usuel Introduction Les logiques sont utilisées en informatique pour : - MODELISER de manière formelle des “objets” rencontrés par les informaticiens (exemple : bases de données, bases de connaissances, pré-post conditions d’une procédure, etc.) - RAISONNER Après une phase de modélisation, l’informaticien doit être capable de se servir du modèle et raisonner sur celui-ci. (exemple : validation d’un modèle de données, prise de décision à partir de faits et d’une base de connaissances, preuve de correction d’une procédure/d’un programme) La logique est à la base de l’étude des raisonnements, c’est-à-dire des déductions que l’on peut faire sur les modèles formels. Axiome Un axiome est un énoncé supposé vrai à priori et que l’on ne cherche pas à démontrer. Ces énoncés ont en commun d’être « évidents » pour tout le monde. Proposition (ou assertion ou affirmation) Une proposition est un énoncé pouvant être vrai ou faux. Le mot proposition est clair : on propose quelque chose, mais cela reste à démontrer. Théorème Un théorème est une proposition vraie (et en tout cas démontrée comme telle). Corollaire Un corollaire à un théorème est un théorème qui est conséquence de ce théorème. Lemme Un lemme est un théorème préparatoire à l’établissement d’un théorème de plus grande importance. Conjecture Une conjecture est une proposition que l’on suppose vraie sans parvenir à la démontrer. Définition Une définition est un énoncé dans lequel on décrit les particularités d’un objet. On doit avoir conscience que le mot « axiome » est quelquefois synonyme de « définition ». Dr Rindra Rakotomahefa Logique et Algorithme | 2021 - 6 Logique – Calculs Propositionnels Négation d’une proposition Soit P une proposition. On définit sa négation, notée P (ou aussi nonP ou ⌉P), à partir de sa table de vérité. P Non P V F F V Les connecteurs logiques Le connecteur logique OU / OR Soient P et Q deux propositions. On peut définir les propositions « P ou Q », notée P v Q, et « P et Q », notée P ^Q par la table de vérité : P Q P OU Q V V F F V F V F V V V F Le connecteur logique ET / AND Soient P et Q deux propositions. On peut définir les propositions « P et Q », notée P ^ Q par la table de vérité : P Q P ET Q V V F F V F V F V F F F L’implication logique Si P et Q sont deux propositions, on définit l’implication logique : P ⇒ Q par sa table de vérité. P Q P ⇒ Q V V F F V F V F V F V V L’équivalence logique Deux propositions équivalentes P et Q sont deux propositions simultanément vraies et simultanément fausses. Ainsi, la table de vérité de l’équivalence logique P ⇔ Q est : Dr Rindra Rakotomahefa Logique et Algorithme | 2021 - 7 P Q P ⇔Q V V F F V F V F V F F V Remarque : C.N.S, ssi, il faut et il suffit Les expressions « Condition nécessaire et suffisante (CNS) », « si et seulement si (ssi) », « il faut et il suffit » signifient toutes « logiquement équivalent » ou encore « ⇔». Mais plus précisément, dans chacune de ces expressions, quel morceau correspond à « ⇒ » et quel autre morceau correspond à « ⇐ » ? La réponse est fournie par le tableau suivant : Les quantificateurs ∀ et ∃ On se donne un ensemble E et P(x) une proposition dont les valeurs de vérité sont fonction des éléments x de E. • La proposition : « Pour tous les éléments x de E, la proposition P(x) est vraie » s’écrit : « ∀x ∈ E, P(x) » • La proposition : « il existe au moins un élément x de E tel que la proposition P(x) est vraie » s’écrit : « ∃x ∈ E/ P(x) » ou aussi « ∃x ∈ E, P(x) » • La proposition : « il existe un et un seul élément x de E tel que la proposition P(x) est vraie » s’écrit : « ∃!x ∈ E, P(x) » ∀ s’appelle le quantificateur universel et ∃ s’appelle le quantificateur existentiel Propriétés des quantificateurs avec une variable 1) (∀x ∈ E, P(x) ^ Q(x)) ⇔ ((∀x ∈ E/ P(x)) ^ (∀x ∈ E, Q(x))). 2) (∀x ∈ E, P(x) v Q(x)) ⇐ ((∀x ∈ E/ P(x)) v (∀x ∈ E, Q(x))). 3) (∃x ∈ E, P(x) ^ Q(x)) ⇒ ((∃x ∈ E, P(x)) ^ (∃x ∈ E, Q(x))). 4) (∃x ∈ E, P(x) v Q(x)) ⇔ ((∃x ∈ E, P(x)) v (∃x ∈ E, Q(x))). 5) non(∀x ∈ E, P(x)) ⇔ (∃x ∈ E, nonP(x)) 6) non(∃x ∈ E, P(x)) uploads/Philosophie/ syllabus-logique-et-algorithme-2021.pdf