Diapositive 1
Diapositive 2
Qu'est-ce qu'un modèle algorithmique ? Pourquoi un algorithme est-il appelé un modèle et que modélise-t-il ? Un algorithme est une instruction claire et précise à un interprète spécifique pour effectuer la séquence finale d'actions menant à un objectif défini. L'objectif est atteint grâce à l'activité d'un interprète.
Diapositive 3
Étapes de l'activité : Détermination de l'objectif ; Ordonnancement des travaux de l'entrepreneur; Le travail de l'interprète; Obtenir le résultat. Où se situe l'algorithme ici ? Un algorithme est un plan détaillé du travail de l'interprète ; c'est une description de la séquence d'actions que l'interprète doit effectuer.
Diapositive 4
L'algorithme est un modèle d'information de l'activité de l'interprète. Ce modèle sera appelé algorithmique. Riz. Étapes du mouvement du but au résultat. Détermination du but Construction d'un plan-algorithme Travail de l'exécuteur Obtention du résultat Modèle du travail de l'exécuteur
Diapositive 5
Système de commandes de l'exécuteur Pour construire un véritable plan-algorithme, vous devez connaître les capacités de l'exécuteur. Ces capacités sont déterminées par le SKI. Lors de la composition d'un algorithme, il ne faut pas dépasser le cadre SQI. Il est plus facile de construire un algorithme pour un automate contrôlé par logiciel que pour un humain. Pour un automate, SKI est un ensemble de commandes strictement défini dans un langage formalisé pour décrire des algorithmes. Ces langages sont appelés langages de programmation et l'algorithme est appelé programme. Le SKI d'une personne ne peut pas être entièrement décrit.
Diapositive 6
Un exemple de modèle algorithmique. Tâche : deviner un nombre entier à partir d'une plage donnée en utilisant la méthode de demi-division. Le premier joueur devine un nombre entier à partir d'une plage de nombres donnée, par exemple de 1 à 100. Le second doit deviner le nombre en utilisant le moins de questions.
Diapositive 7
Algorithme pour un interprète humain. Algorithme Deviner le nombre Donné : la plage de nombres de A à B Il faut : deviner le nombre X conçu par le joueur en utilisant l'algorithme de demi-division Début 1. Poser la question : Est-ce que X est inférieur à la valeur moyenne entre A et B? 2. Si la réponse est « oui », alors prenez la partie entière de la moyenne comme valeur de B. 3. Si la réponse est « non », alors prenez l'entier le plus proche supérieur à la moyenne comme valeur de A. 4. Si les valeurs de A et B sont égales, leur valeur totale est le nombre requis X. 5. Si les valeurs de A et B ne sont pas égales, revenez à l'exécution du paragraphe 1. Fin
Diapositive 8
Diapositive 9
Algorithme pour un exécuteur informatique. Langage algorithmique Alg Demi division Entier A, B, X Début Saisie A, B, X Tant que A B, répéter Hc Si X≤ (A + B) / 2 Alors B : = CAL ((A + B) / 2) Sinon A : = BUT ((A + B) / 2) +1 Kts Conclusion A Fin
Diapositive 10
Programmation structurée La structure de l'algorithme construit est une boucle avec des branchements imbriqués. Tout algorithme peut être construit à partir d'une combinaison de trois structures algorithmiques de base : séquence, branche et boucle. Cette déclaration est la base d'une technique appelée programmation structurée. Si l'algorithme est structuré, alors il est facile de passer de la description de l'algorithme au programme.
Diapositive 11
Le traçage d'algorithme est un modèle du fonctionnement du processeur. Pour tester la justesse d'un algorithme, il n'est pas du tout nécessaire de le traduire dans un langage de programmation. Une personne peut également tester l'algorithme - en traçant. Lors de l'exécution d'un traçage manuel, une personne simule le travail du processeur, en exécutant chaque commande et en entrant les résultats de l'exécution de la commande dans une table de traçage. Choisissons un intervalle de nombres devinables de 1 à 8. Laissez le joueur concevoir le nombre 3.
Diapositive 12
Numéro d'étape Commande d'algorithme Variables Actions effectuées X A B 1 Entrée A, B, X 3 1 8 2 A ≠ B 1 ≠ 8, oui 3 X ≤ (A + B) / 2 3 ≤ 4,5, oui 4 B : = CIBLE ((A + B) / 2) B : = 4 5 A ≠ B 1 ≠ 4, oui 6 X ≤ (A + B) / 2 3 ≤ 2.5 Numéro d'étape Commande d'algorithme Variables Actions effectuées XAB 1 Entrée A, B, X 3 1 8 2 A ≠ B 1 ≠ 8, oui 3 X ≤ (A + B) / 2 3 ≤ 4,5, oui 4 B : = CEL ((A + B) / 2) 3 1 4 V : = 4 5 A ≠ B 1 ≠ 4, oui 6 X ≤ (A + B) / 2 3 ≤ 2,5, non
Qu'est-ce qu'un modèle algorithmique Un algorithme est une instruction claire et précise à un interprète spécifique pour effectuer une séquence finale d'actions menant à un objectif défini. Les étapes de l'activité depuis la définition de l'objectif (fixation de la tâche) jusqu'à l'obtention du résultat sont les suivantes : 1) Définition de l'objectif 2) Ordonnancement du travail de l'exécuteur 3) Le travail de l'exécuteur 4) Obtention du résultat L'algorithme est un modèle d'information de l'activité de l'exécuteur. Ce modèle sera appelé algorithmique.
Système de commandes de l'exécuteur Pour construire un plan réel - un algorithme qui s'avère réalisable, vous devez connaître exactement les capacités de l'exécuteur. Ces capacités sont déterminées par le système de commandement de l'interprète (SKI). Lors de la composition d'un algorithme, il ne faut pas dépasser le cadre SQI. C'est la propriété de l'intelligibilité de l'algorithme. Pour un automate, SKI est un ensemble fini de commandes strictement défini par les concepteurs. Par conséquent, l'algorithme est une description exacte de son fonctionnement et l'automate effectue le travail en suivant formellement les instructions de l'algorithme. Pour piloter un automate ou un ordinateur, il n'est pas difficile de proposer un langage formalisé pour décrire des algorithmes. De tels langages sont appelés langages de programmation et un algorithme présenté dans un langage de programmation est appelé programme.
Un exemple de modèle algorithmique Le premier joueur devine un nombre entier dans une plage de nombres donnée, par exemple de 1 à 100. Le second doit deviner ce nombre en utilisant le moins de questions. Algorithme pour deviner le nombre par la méthode de la demi-division, axé sur l'interprète humain. Algorithme Deviner le nombre Donné : la plage des nombres va de A à B Il faut : deviner le nombre X, conçu par le joueur, en utilisant l'algorithme de demi-division Début 1) Poser la question : Est-ce que X est inférieur au valeur moyenne entre A et B ? 2) Si la réponse est "OUI", alors prenez la partie entière de la moyenne comme valeur B. 3) Si la réponse est "NON", alors prenez comme valeur A l'entier le plus proche supérieur à la moyenne. 4) Si les valeurs de A et B sont égales, alors leur valeur totale est le nombre X souhaité. 5) Si les valeurs de A et B ne sont pas égales, revenez à l'étape 1. Fin Cet algorithme est focalisé sur un interprète humain, pas un ordinateur.
Algorithme "Demi division" Alg Demi division Entier A, B, X Début Saisie A, B, X Pendant AB, répéter Hc Si X (A + B) / 2 Alors B : = Entier ((A + B) / 2) Sinon , A : = Int ((A + B) / 2) +1 KV Kts Sortie A Fin Début Fin Entrée A, B, X Sortie A AB X (A + B) / 2 B : = INT ((A + B ) / 2) A : = BUT ((A + B) / 2) +1 non oui non oui
Organigramme Un organigramme est un graphe orienté qui indique l'ordre dans lequel un exécuteur exécute les instructions d'un algorithme. Les blocs - les sommets de ce graphique - désignent des commandes individuelles qui sont données à l'exécuteur, et les arcs indiquent la séquence de transitions d'une commande à une autre. Dans les rectangles des diagrammes, les commandes sont écrites - actions, dans les losanges - conditions qui déterminent la direction de l'exécution ultérieure des commandes ; en parallélogrammes - commandes d'entrée ou de sortie d'informations; dans les ovales - le début ou la fin de l'exécution de l'algorithme. Ici, vous pouvez parler du chemin du graphe pendant l'exécution de l'algorithme. Tout chemin part du haut "Début" et se termine par une sortie vers le haut "Fin". En interne, le chemin peut être différent en fonction des données initiales et des résultats de la vérification des conditions. Un schéma fonctionnel est une forme graphique, un langage algorithmique est deux formes différentes de représentation d'un modèle algorithmique.
Programmation structurée La structure de l'algorithme construit est une boucle avec des branchements imbriqués. Tout algorithme peut être construit à partir d'une combinaison de trois structures algorithmiques de base : séquence, branche et boucle. Cette déclaration est la base d'une technique appelée programmation structurée. Les langages de programmation modernes permettent de passer facilement d'une description d'algorithme à un programme si l'algorithme est structuré. Par conséquent, le modèle le plus rationnel de l'activité de l'interprète est le modèle algorithmique structurel.
Traçage d'algorithmes - un modèle de fonctionnement du processeur Pour vérifier l'exactitude d'un algorithme, il n'est pas du tout nécessaire de le traduire dans un langage de programmation et d'exécuter des tests sur un ordinateur. Une personne peut également tester l'algorithme - en traçant. Lors de l'exécution d'un traçage manuel, une personne simule le travail du processeur, en exécutant chaque commande de l'algorithme et en entrant les résultats de l'exécution de la commande dans une table de traçage. C'est un modèle du fonctionnement du processeur lors de l'exécution d'un programme. Le programme est exécuté par étapes (première colonne du tableau). La colonne Commande d'algorithme affiche le contenu du registre de commande du processeur. Où la prochaine commande est placée. La colonne "Variables" affiche le contenu des cellules mémoire du calculateur (ou registres mémoire du processeur) réservées aux valeurs des variables. La colonne "Action effectuée" reflète les actions effectuées par l'unité arithmétique et logique du processeur.
Sujet de la leçon : « L'algorithme comme modèle d'activité ».
Objectif : expliquer un nouveau sujet de manière intéressante et compréhensible.
Familiariser les étudiants avec le sujet : « Le concept d'algorithme. Types d'algorithmes et leurs propriétés » ;
Les étudiants doivent connaître le concept d'un algorithme, les propriétés des algorithmes ;
Les élèves devraient être capables de fournir des exemples d'algorithmes.
Pendant les cours :
1. Moment d'organisation.
2. Apprendre un nouveau sujet.
Commençons par répéter le concept d'un algorithme en regardant un exemple. Disons que vous voulez découper un modèle de voiture dans du papier. Le résultat dépendra en grande partie de vos compétences et de votre expérience. Cependant, il sera beaucoup plus facile d'atteindre votre objectif si vous définissez d'abord un plan d'action, tel que le suivant :
1. Étudiez l'image de la voiture sur le modèle existant.
2. Dessinez les portes, la carrosserie sur papier.
3. Découpez des croquis.
4. Essayez de coudre des croquis ensemble, corrigez les erreurs.
5. Collez les parties du modèle.
En suivant le plan préparé, toute personne, même sans capacité artistique, mais ayant de la patience, obtiendra certainement un bon résultat. Un tel plan avec une description détaillée des actions nécessaires pour obtenir le résultat attendu est appelé un algorithme.
Le concept d'algorithme. ( Fournir des informations supplémentaires)
L'émergence des algorithmes est associée à la naissance des mathématiques. Il y a plus de 1000 ans (en 825), un scientifique de la ville de Khorezm Abdullah (ou Abu Jafar) Muhammad bin Musa al-Khorezmi a créé un livre sur les mathématiques, dans lequel il décrivait des méthodes pour effectuer des opérations arithmétiques sur des nombres à plusieurs chiffres. Le mot « algorithme » lui-même est apparu en Europe après la traduction en latin du livre de ce mathématicien d'Asie centrale, dans lequel son nom était écrit « Algorithmes ».
Algorithme- une description de la séquence d'actions (plan), dont la mise en œuvre stricte conduit à la résolution de la tâche en un nombre fini d'étapes.
Algorithmisation- le processus d'élaboration d'un algorithme (plan d'action) pour résoudre un problème.
Exemples d'algorithmes :
Tout appareil acheté en magasin est fourni avec une notice d'utilisation.
Chaque chauffeur doit connaître le code de la route.
La production de masse de voitures n'est devenue possible que lorsque l'ordre d'assemblage de la voiture sur le convoyeur a été inventé.
Propriétés des algorithmes.
Nous rencontrons des algorithmes à chaque étape. Nous effectuons certaines d'entre elles mécaniquement, sans même y penser. Lors de l'exécution de certaines actions, nous ne soupçonnons même pas que nous effectuons un certain algorithme.
Ces exemples ne sont rien de plus qu'un algorithme. Malgré la différence significative dans l'essence des actions de ces exemples, on peut trouver beaucoup de points communs. Ces caractéristiques générales sont appelées propriétés de l'algorithme. Considérons-les.
Discrétion(de Lat. discretus - divisé, discontinu) - il s'agit d'une décomposition de l'algorithme en une série d'actions complètes séparées (étapes). Les algorithmes ci-dessus ont en commun la nécessité de respecter strictement la séquence d'actions. Essayons d'inverser les deuxième et troisième actions dans le premier exemple. Vous pouvez bien sûr exécuter cet algorithme, mais il est peu probable que la porte s'ouvre. Et si nous échangeons, supposons, les cinquième et deuxième actions dans le deuxième exemple, l'algorithme devient irréalisable.
Déterminisme(du latin déterminé - certitude, précision) - toute action de l'algorithme doit être déterminée de manière stricte et sans ambiguïté dans chaque cas.
Par exemple, si des bus de différents itinéraires s'arrêtent, l'algorithme doit indiquer un numéro d'itinéraire spécifique - 5. De plus, vous devez spécifier le nombre exact d'arrêts à parcourir, disons trois.
Membre- chaque action séparément et l'algorithme dans son ensemble doivent pouvoir se terminer. Dans les exemples fournis, chaque action décrite est réelle et peut être exécutée. Par conséquent, l'algorithme a une limite, c'est-à-dire qu'il est fini.
Caractère de masse- le même algorithme peut être utilisé avec des données d'entrée différentes.
Efficacité- il n'y avait pas d'erreurs dans l'algorithme.
Types d'algorithmes.
Il existe 4 types d'algorithmes : linéaire, cyclique, de branchement, auxiliaire.
Linéaire algorithme (séquentiel) - une description des actions qui sont effectuées une fois dans un ordre donné.
Les algorithmes pour déverrouiller les portes, faire du thé, faire un sandwich sont linéaires. Un algorithme linéaire est utilisé pour évaluer une expression arithmétique si elle n'utilise que l'addition et la soustraction.
Algorithme cyclique- une description des actions qui doivent être répétées un nombre spécifié de fois ou jusqu'à ce qu'une condition spécifiée soit remplie. La liste des actions répétitives est appelée le corps de la boucle.
De nombreux processus dans le monde environnant sont basés sur la répétition répétée de la même séquence d'actions. Le printemps, l'été, l'automne et l'hiver arrivent chaque année. La vie végétale suit les mêmes cycles tout au long de l'année. En comptant le nombre de tours complets de l'aiguille des minutes ou des heures, une personne mesure le temps.
État- une expression qui se situe entre le mot "si" et le mot "alors" et prend le sens de "vrai" ou de "faux".
Algorithme de bifurcation- un algorithme dans lequel, selon la condition, l'une ou l'autre séquence d'actions est effectuée.
Exemples d'algorithmes de branchement : s'il pleut, vous devez ouvrir le parapluie ; si vous avez mal à la gorge, la marche doit être annulée; si un billet de cinéma ne coûte pas plus de dix roubles, achetez un billet et prenez place dans la salle, sinon (si le prix du billet est supérieur à 10 roubles), rentrez chez vous.
Dans le cas général, le schéma de l'algorithme de branchement ressemblera à ceci : "si la condition, alors..., sinon...". Cette représentation de l'algorithme est appelée la forme complète.
Forme incomplète, dans laquelle les actions sont ignorées : "si condition, alors...".
Algorithme d'aide- un algorithme qui peut être utilisé dans d'autres algorithmes en spécifiant uniquement son nom.
Devoirs. § seize,
1. Trouvez vos propres exemples pour chaque type d'algorithme.
2. Créez un algorithme pour traverser la route avec et sans feux de circulation.
Résumé de la leçon.
Enfants, qu'avez-vous appris de nouveau aujourd'hui ?
Aujourd'hui, nous avons appris ce qu'est un algorithme, appris les types et les propriétés des algorithmes
Qu'est-ce qu'un modèle algorithmique ? Pourquoi un algorithme est-il appelé un modèle et que modélise-t-il ? n Un algorithme est une instruction claire et précise à un interprète spécifique pour effectuer la séquence finale d'actions menant à un objectif défini. C'est-à-dire que l'objectif est atteint grâce à l'activité d'un certain interprète.
Étapes de l'activité : n n Définition du but ; Ordonnancement des travaux de l'entrepreneur; Le travail de l'interprète; Obtenir le résultat. Où se situe l'algorithme ici ? Un algorithme est un plan détaillé du travail de l'interprète ; c'est une description de la séquence d'actions que l'interprète doit effectuer.
Par conséquent, l'algorithme est un modèle d'information de l'activité de l'interprète. Ce modèle sera appelé algorithmique. Riz. Étapes du mouvement du but au résultat. Détermination du but Construction du plan de l'algorithme Modèle du travail du performeur Travail du performeur Obtention du résultat
Système de commandes de l'exécuteur Pour construire un véritable plan-algorithme, vous devez connaître les capacités de l'exécuteur. Ces capacités sont déterminées par le SKI. Lors de la composition d'un algorithme, il ne faut pas dépasser le cadre SQI. Il est plus facile de construire un algorithme pour un automate contrôlé par logiciel que pour un humain. Pour un automate, SKI est un ensemble de commandes strictement défini dans un langage formalisé pour décrire des algorithmes. Ces langages sont appelés langages de programmation et l'algorithme est appelé programme. Le SKI d'une personne ne peut pas être entièrement décrit.
Un exemple de modèle algorithmique. Tâche : deviner un nombre entier à partir d'une plage donnée en utilisant la méthode de demi-division. Le premier joueur devine un nombre entier à partir d'une plage de nombres donnée, par exemple de 1 à 100. Le second doit deviner le nombre en utilisant le moins de questions.
Algorithme pour un interprète humain. Algorithme Deviner le nombre Donné : la plage de nombres de A à B Il faut : deviner le nombre X conçu par le joueur en utilisant l'algorithme de demi-division Début 1. Poser la question : Est-ce que X est inférieur à la valeur moyenne entre A et B? 2. Si la réponse est « oui », alors prenez la partie entière de la moyenne comme valeur de B. 3. Si la réponse est « non », alors prenez comme valeur A l'entier le plus proche supérieur à la moyenne. 4. Si les valeurs de A et B sont égales, leur valeur totale est le nombre X souhaité. 5. Si les valeurs de A et B ne sont pas égales, revenez à l'exécution du paragraphe 1. Fin
Algorithme pour un exécuteur informatique. Début du schéma fonctionnel Entrée A, B, X non A ≠ B oui non X≤ (A + B) / 2 B = CEL ((A + B) / 2) A = CEL ((A + B) / 2) + 1 Conclusion A Fin
Algorithme pour un exécuteur informatique. Langage algorithmique Alg Demi division Entier A, B, X Début Saisie A, B, X Tant que A B, répéter Hc Si X≤ (A + B) / 2 Alors B : = CAL ((A + B) / 2) Sinon A : = BUT ((A + B) / 2) +1 Kts Conclusion A Fin
Programmation structurée La structure de l'algorithme construit est une boucle avec des branchements imbriqués. Tout algorithme peut être construit à partir d'une combinaison de trois structures algorithmiques de base : séquence, branche et boucle. Cette déclaration est la base d'une technique appelée programmation structurée. Si l'algorithme est structuré, alors il est facile de passer de la description de l'algorithme au programme.
Le traçage d'algorithme est un modèle du fonctionnement du processeur. Pour tester la justesse d'un algorithme, il n'est pas du tout nécessaire de le traduire dans un langage de programmation. Une personne peut également tester l'algorithme - en traçant. Lors de l'exécution d'un traçage manuel, une personne simule le travail du processeur, en exécutant chaque commande et en entrant les résultats de l'exécution de la commande dans une table de traçage. Choisissons un intervalle de nombres devinables de 1 à 8. Laissez le joueur concevoir le nombre 3.
Numéro d'étape Commande de l'algorithme Variables X A 3 1 Actions effectuées B 1 Entrée A, B, X 2 A ≠ B 1 ≠ 8, oui 3 X ≤ (A + B) / 2 3 ≤ 4, 5, oui 4 B : = BUT ( (A + B) / 2) 5 A ≠ B 1 ≠ 4, oui 6 X ≤ (A + B) / 2 3 ≤ 2, 5, non 3 1 8 4 B : = 4
7 A : = BUT ((A + B) / 2 + 1) 3 8 A ≠ B 3 ≠ 4, oui 9 X ≤ (A + B) / 2 3 ≤ 3, 5, oui 10 B : = BUT (( A + B) / 2) 11 A ≠ B 3 ≠ 3, non 12 Conclusion A Réponse : 3 3 4 3 A : = 3 B : = 3
Le traçage d'algorithme est un modèle du fonctionnement du processeur. n n Le programme est exécuté par étapes (première colonne du tableau). La colonne Commande d'algorithme affiche le contenu du registre de commande du processeur, où la commande suivante est placée. La colonne "Variables" affiche le contenu des cellules mémoire allouées aux valeurs des variables. La colonne "Action effectuée" reflète les actions effectuées par l'unité arithmétique et logique du processeur.
Conclusion : n Ainsi, l'algorithme ainsi que la table de trace simulent complètement le processus de traitement de l'information dans l'ordinateur.
Système de concepts de base Algorithme - modèle d'activité L'objet de la modélisation - l'activité ciblée de l'interprète. Interprète humain Interprète automate (y compris un ordinateur) SKI non formalisé Formes de présentation d'algorithmes Schéma fonctionnel Langage algorithmique pédagogique Langage de programmation Le traçage d'algorithme est une exécution étape par étape d'un algorithme avec une version test des données initiales. "Traçage manuel" - remplissage de la table de trace. La table de trace est un modèle du fonctionnement du processeur pendant l'exécution de l'algorithme.
Devoir § 16 lire, répondre aux questions 3, 4, 5, 8, 11 (toutes les 3 questions posées)
Présenter sous forme de diagramme Dans l'environnement Word Présenter cet algorithme sous forme de diagramme à l'aide de l'entier de démarrage automatique alg a, ba : = 2 b : = 0 nts tandis que a 10 a : = a + 2 b : = b + 3 * a kc broche b con
