Algorithme logiciel d'actions. Algorithmes et programmes. Analyse du temps d'exécution de l'algorithme

17.04.2019

Algorithme- un système d'instructions précises et compréhensibles, une séquence définie d'opérations élémentaires sur des données initiales, dont la mise en œuvre assure la solution de problèmes de ce type.

Propriétés de l'algorithme :

-discrétion- la séquence de résolution de problèmes (processus) doit être divisée en une séquence d'étapes individuelles.

-clarté- l'algorithme doit être compréhensible pour l'interprète. À cet égard, l'algorithme doit être développé en mettant l'accent sur l'interprète spécifique, c'est-à-dire L'algorithme peut inclure des commandes provenant des systèmes de commande d'un exécuteur donné.

-déterminisme- étant compréhensible, l'algorithme ne doit pas contenir de commandes dont la signification peut être perçue de manière ambiguë. La violation de ces exigences par les compilateurs d'algorithmes conduit au fait qu'un même programme, lorsqu'il est exécuté par différents exécuteurs, ne produit pas les mêmes résultats.

-efficacité– consiste dans le fait qu'avec l'exécution exacte de toutes les commandes de l'algorithme, le processus de résolution des problèmes doit s'arrêter en un nombre fini d'étapes et en même temps il faut obtenir le résultat déterminé lors de la définition des problèmes.

-caractère de masse- l'adéquation de l'algorithme à la résolution de problèmes d'une certaine classe.

Façons d’écrire l’algorithme :

-verbal– méthode du langage naturel.

-graphique-description de l'algorithme à l'aide de diagrammes.

Le processus d’exécution d’opérations ou de groupes d’opérations

saisie des données initiales, sortie des résultats

Décision - choix du sens d'exécution

La modification est l'exécution d'opérations qui modifient des commandes ou des groupes de commandes qui modifient des programmes.

Connecteurs de ligne sur une seule page.

Connecteurs interpages.

-langage de programmation– pratique pour entrer dans un ordinateur.

-pseudocode est un langage qui utilise la structure et la syntaxe d'un langage assez formalisé et qui permet en même temps des constructions de natures. Langue.

Types d'algorithmes et principes de base pour composer des algorithmes.

-Linéaire– un algorithme dans lequel les commandes sont exécutées séquentiellement les unes après les autres dans l'ordre de leur apparition naturelle, quelles que soient les conditions. S1, s2, S3…Sn

-ramification (ramification)- il s'agit d'un processus dans lequel sa mise en œuvre se déroule dans l'une parmi plusieurs directions prédéterminées, en fonction des données initiales ou des résultats intermédiaires.

Construction conditionnelle complète (ramification complète)

· Construction conditionnelle incomplète

· Choisissez parmi plusieurs

-cyclique– un algorithme dans lequel une séquence peut être exécutée plus d'une fois.

Boucle avec paramètre

· Boucle avec condition préalable. Il se peut qu'il ne soit jamais exécuté. Le corps de la boucle doit contenir un opérateur qui modifie la valeur d'une variable incluse dans le bloc Q.

· Boucle avec postcondition. S'exécute au moins une fois.

Principes de base de l'algorithmique :

1. Identifiez les données sources, les résultats et attribuez-leur des noms.

2. Méthode de résolution de problèmes.

3. Divisez la méthode de résolution des problèmes en étapes.

4. Avec une représentation graphique de l'algorithme, chaque étape se présente sous la forme d'un bloc correspondant - un schéma de l'algorithme et l'ordre de leur exécution sont indiqués par des lignes de communication.

5. Dans le schéma résultant pour toute option de calcul.

Prévoir l'émission de résultats ou de messages concernant leur absence.

Offrez la possibilité, après avoir effectué une opération, de vous déplacer d'une manière ou d'une autre vers le bloc final.

40.Structures algorithmiques de base

Nous avons déjà examiné les concepts de base de la programmation et nous rapprochons un peu plus du sujet (mais seulement de plus près, nous programmerons plus tard).

Regardons les principales structures des algorithmes, et il y en a six :

· Suivant. Il s'agit d'une séquence de blocs (ou groupes de blocs) d'un algorithme. Dans le programme, les éléments suivants sont présentés sous forme d'exécution séquentielle d'opérations

·
Branchement. Cette structure algorithmique est utilisée lorsque, selon la condition, il est nécessaire d'effectuer l'une ou l'autre action

·
By-pass. Cette structure est un cas particulier de branchement, lorsqu'il n'y a aucune action dans l'une des branches.

·
Choix multiples. Cette structure est une généralisation du branchement, où il est nécessaire d'effectuer une parmi plusieurs actions en fonction de la valeur de la variable A.

LEÇON OUVERTE DE MATHÉMATIQUES

"Algorithme. Programme d'action"

2ème année « Ecole 2100 »

Objectifs de la leçon : 1. Prouver qu'en utilisant un algorithme général, vous pouvez effectuer un grand nombre de tâches particulières différentes ; 2. Renforcer la capacité d'agir selon un algorithme en effectuant l'une ou l'autre tâche ; 3. Renforcer la capacité à distinguer différents types d'algorithmes : linéaires, ramifiés, cycliques ; 4. À l'aide d'un exemple, prouver la présence d'actions selon l'algorithme dans la vie quotidienne.

Objectifs de la leçon : 1. Résoudre divers types de tâches à l'aide d'algorithmes d'action ; 2. Justifier le choix de ce type d'algorithme.

PROGRESSION DE LA LEÇON :

Moment d'organisation– vérifier l'état de préparation pour la leçon, créer l'ambiance du succès.

Vérification des devoirs –élaboration d'un algorithme pour « Collecter une mallette pour l'école ».

Échauffement mathématique :

Combien y a-t-il de centaines, de dizaines et d’unités dans le nombre 534 ? (Dans 534 il y a 5 centaines, 53 dizaines, 534 unités). Écrivez ce numéro dans votre cahier de différentes manières.

(534 = 5 cent 34 unités = 53 des. 4 unités = 534 unités)

Recueillez le nombre à partir de la somme des termes numériques et notez-le.

700 + 30 + 4 = (734) 500 + 6 = (506)

Dans une série de chiffres, trouvez le numéro « supplémentaire » et expliquez votre choix.

720, 540, 306, 50, 910, 300.

(Tous les numéros sauf 50 , - à trois chiffres ; tous les chiffres sauf 306 , - rond; dans tous les nombres sauf 300 un zéro à la fois).

Alors, après un petit échauffement, êtes-vous prêt à avancer ? Pour garder votre combativité jusqu'à la fin du cours, notre ami Hibou aidera à le soutenir. (Je vous souhaite du succès ! Vous réussirez !)

Chaque jour, une personne fait un grand nombre de choses différentes. Il ne doit rien oublier. Comment pouvez-vous éviter de vous perdre et de manquer quelque chose d’important ? Y a-t-il quelque chose que vous pouvez recommander à quelqu'un pour faciliter sa journée ? (Notez toutes vos affaires en ordre dans un journal (un cahier dans lequel vous notez toutes vos activités quotidiennes) et suivez-les tout au long de la journée).

Que vous rappelle ce conseil ? Si nous disons toutes les actions dans l’ordre, qu’obtenons-nous ? (Algorithme). Et si nous enregistrons des actions et conseillons à quelqu’un d’utiliser ces enregistrements, qu’obtiendrons-nous ? (Programme d'action). Quelle est la différence entre un algorithme et un programme d’action ? (Un algorithme est un ordre oral d'actions et un programme d'action est un algorithme écrit).

Eh bien, êtes-vous prêt à nommer le sujet de notre leçon ? A quoi sera-t-il dédié ? "Algorithme. Programme d'action". Et dans quel but allons-nous en parler et accomplir des tâches aujourd'hui ? (Attirez l'attention des élèves sur les objectifs de la leçon).

Quelles tâches nous fixons-nous pour atteindre ces objectifs ? (Se référer aux objectifs de la leçon).

Avant de passer à nos tâches, je vous suggère de rappeler les concepts de base associés à notre sujet. (Les concepts de base sont affichés au tableau : algorithme, programme d'action, organigramme, types d'algorithmes : - linéaire, - ramifié, - cyclique).

Passons à la première tâche :

- calculer la somme des nombres 517 + 76 (593)

Quel algorithme allons-nous utiliser ? (« Ajout de colonne avec transition par chiffre »).

2 – ajouter des unités ;

3 – écrire les unités sous les unités et prendre en compte la transition par le chiffre ;

4 – ajouter des dizaines en tenant compte du passage dans le rang ;

5 – écrivez les dizaines sous les dizaines et tenez compte du passage par le chiffre

6 – ajouter des centaines en tenant compte du passage par le chiffre ;

En utilisant un algorithme général, nous pouvons calculer la somme de n’importe quel nombre. Prouvons-le. Tout seul calculer la somme des nombres 409 et 298 (707).

- calculer la différence entre les nombres 724 – 235(489)

Quel algorithme allons-nous utiliser ? (« Soustraction de nombres à trois chiffres avec transition par la valeur de position »).

1 – notez les nombres dans une colonne, chiffre en dessous du chiffre ;

2 – soustraire des unités : si nous pouvons soustraire, soustraire et écrire des unités sous unités, si nous ne pouvons pas, prendre 1 dizaine et la décomposer en 10 unités plus les unités qui existent déjà et soustraire des unités, écrire des unités sous unités ;

3 – on se souvient que nous avons pris 1 dizaine, soustrayons les dizaines : si nous pouvons soustraire, soustraire et écrire les dizaines sous les dizaines, si nous ne pouvons pas, nous prenons 1 centaine et la décomposons en 10 dizaines plus ces dizaines qui existent déjà et soustrayons les dizaines, écrivez les dizaines sous les dizaines ;

4 – rappelez-vous que nous avons emprunté 1 centaine, soustrayons des centaines et écrivons des centaines sous des centaines ; 5 – lisez le résultat.

Tout seul calculer la différence entre les nombres 961 – 583(378)

Maintenant, prouvez vos compétences et effectuez l'addition et la soustraction de « nombres féeriques » :

ΨÖ0 + Δ = (ΨÖΔ) Ω00 + ÖÖ = (ΩÖΛ)

ΥφΨ – φΨ = (Υ00) £0§ - £00 = (§)

Quelles règles supplémentaires vous aideront à faire face à cette tâche ?

(Si vous ajoutez 0 à n’importe quel nombre, vous obtenez le même nombre ; si vous soustrayez le même nombre à n’importe quel nombre, vous obtenez 0).

Votre algorithme de raisonnement a-t-il changé lors de la résolution d’exemples avec des « nombres féeriques » ?

Ainsi, nous avons prouvé qu'en utilisant un algorithme général d'actions, nous pouvons résoudre divers exemples.

Au tableau se trouvent des enregistrements des algorithmes que nous utilisions maintenant, mais pas sous forme orale, mais sous forme écrite, alors quel est le nom de ces enregistrements ? (Programmes d'actions). Quel est le nom d’un tel enregistrement d’un programme d’action ? (Schéma fonctionnel).

Déterminer à quel type de schéma fonctionnel de l'algorithme d'addition de nombres à trois chiffres ressemble ? (Linéaire). Qu'est-ce qu'un algorithme linéaire ? (Un algorithme dans lequel toutes les actions se succèdent dans un certain ordre. Dans certains cas, l'ordre des actions peut être modifié). Quel est le schéma fonctionnel de l'algorithme de soustraction de nombres à trois chiffres ? (Linéaire, ramifié, cyclique). Qu’est-ce qu’un algorithme branché ? (Un algorithme contenant une condition et un choix d'action). Qu’est-ce qu’un algorithme de round robin ? (Un algorithme dans lequel il y a un retour aux actions précédentes). Montrez dans le diagramme 2 les parties de chaque type d'algorithme.

Organigramme de l'algorithme 1 Organigramme de l'algorithme 2

PHYSMINUTE

Nous rencontrons des algorithmes non seulement lors de la résolution d'exemples. Donnez des exemples de tâches dans lesquelles il est également pratique d'utiliser l'algorithme. (Équations). Testons notre hypothèse. Qu'est-ce qu'une hypothèse ? (Hypothèse scientifique. Si l'hypothèse est confirmée, alors elle devient une règle ou une loi. Si elle n'est pas confirmée, alors nous émettons une nouvelle hypothèse).

Résolvons l'équation. Qu'est-ce qu'une équation ? (Égalité dans laquelle il y a une quantité inconnue, variable). Que signifie résoudre une équation ? (Trouver une valeur de la variable à laquelle notre égalité sera vraie).

X + 241 = 729

Nous appliquons l'algorithme.

1 – regardez le signe pour déterminer le tout et les parties ;

2 – nous désignons le tout et les parties et signons les composants de l'action ;

3 – déterminer quelle est la quantité inconnue ;

4 – sélectionnez la règle souhaitée ;

5 – notez la méthode de résolution ;

6 – calculer ;

7 – notez le résultat ;

8 – effectuer le contrôle.

De quel type d'algorithme s'agit-il ? (À linéaire). Sur la base de l'algorithme, nous résolvons l'équation.

1 limace. 2 limaces. somme

Nous sommes devenus convaincus que les algorithmes ne sont pas seulement nécessaires pour résoudre des exemples. Et si nous poursuivons ce travail, nous pourrons prouver qu'il existe un grand nombre de tâches différentes qui peuvent être effectuées sur la base de l'algorithme.

Mais est-ce seulement en mathématiques que l’on peut rencontrer des actions algorithmiques ? Je vous suggère de construire un modèle d'école du Monde de l'Intellect, qui nécessite des matériaux de construction spéciaux répondant à des exigences strictement définies.

L'adéquation de nos matériaux de construction doit être vérifiée à l'aide du plan d'action. (Travailler avec des blocs Dienesh).

J'ai des éléments de construction sur ma table, mais tous ne conviennent pas à notre construction. Nous n'aurons besoin que des blocs qui réussissent la sélection. Le programme d’action Architectes nous y aidera.

A l'aide de ce programme d'action, sélectionnez plusieurs blocs. Invitez les invités à participer à la sélection. Après avoir sélectionné plusieurs blocs, amenez les élèves à la conclusion que pour la construction nous n'avons besoin ni de blocs rouges ni de blocs ronds. Veuillez noter que nous poursuivrons ce travail et construirons certainement un modèle d’école « Monde de l’Intellect ».

Ce travail prouve que non seulement en mathématiques, mais aussi dans la vie de tous les jours, nous pouvons avoir besoin de la capacité de travailler avec un algorithme.

Revenons maintenant à nos buts et objectifs de la leçon. (Analyser si nous avons atteint chaque objectif et accompli les tâches assignées - RÉSULTAT DE LA LEÇON).

En guise de notes pour la leçon, je voudrais vous présenter des certificats et diplômes pour participer aux olympiades de mathématiques et d'informatique.

Devoir : créer un algorithme pour résoudre des problèmes.

Merci pour votre travail en classe. La leçon est terminée.

). Le développement d'un programme utilisant un tel système de programmation comprend deux étapes : 1) création des éléments de l'interface graphique du programme en mode visuel ; 2) développement du code du programme. Cette approche simplifie grandement la création de programmes, car développer manuellement une interface graphique (dans des langages procéduraux) est un processus complexe et chronophage.

La première étape pour comprendre l’importance d’étudier et de connaître les algorithmes est de définir avec précision ce que l’on entend par algorithme. Un algorithme en programmation est séquence d'actions claire et préciseécrit dans un langage de programmation. Selon le livre populaire Algorithms: Construction and Analysis (Cormen, Leiserson, Rivest, Stein), « un algorithme est toute procédure de calcul bien définie dont l'entrée reçoit une certaine quantité ou un certain ensemble de quantités, et le dont le résultat est une valeur de sortie ou un ensemble de valeurs. En d’autres termes, les algorithmes sont comme des feuilles de route pour atteindre un objectif clairement défini. Le code de calcul des termes de la séquence de Fibonacci est une implémentation d'un algorithme spécifique. Même une simple fonction d'addition de deux nombres est un algorithme, même s'il est simple.

Pour créer un algorithme (programme), vous devez savoir :

un ensemble complet de données de tâche initiales (état initial de l'objet) ;

le but de créer l'algorithme (l'état final de l'objet) ;

le système de commande de l'interprète (c'est-à-dire un ensemble de commandes que l'interprète comprend et peut exécuter).

L'algorithme (programme) résultant doit avoir l'ensemble de propriétés suivant :

discrétion(l'algorithme est divisé en étapes distinctes - commandes) ;

sans ambiguïté(chaque commande détermine la seule action possible de l'interprète) ;

clarté(toutes les commandes de l'algorithme sont incluses dans le système de commandes de l'exécuteur) ;

efficacité(l'interprète doit résoudre le problème en un nombre fini d'étapes).

La plupart des algorithmes ont également la propriété caractère de masse(en utilisant le même algorithme, vous pouvez résoudre de nombreux problèmes similaires).

Certains algorithmes, comme ceux permettant de calculer la séquence de Fibonacci, sont intuitifs et font appel à une pensée logique innée et à des compétences en résolution de problèmes. Cependant, la plupart d’entre nous feraient bien d’apprendre des algorithmes complexes afin de pouvoir, à l’avenir, les utiliser comme éléments de base pour résoudre plus efficacement des problèmes de logique. En fait, vous pourriez être surpris du nombre d’algorithmes complexes que les gens utilisent pour consulter leurs e-mails ou écouter de la musique. Cet article présente quelques idées de base sur l'analyse des algorithmes, avec des exemples pratiques illustrant l'importance de l'étude des algorithmes.

Un langage de programmation est un ensemble de règles permettant d'enregistrer des structures et des données algorithmiques.

Analyse du temps d'exécution de l'algorithme

L’un des aspects les plus importants de l’algorithme est sa rapidité. Il est souvent facile de proposer un algorithme qui résout un problème, mais si l'algorithme est trop lent, il est renvoyé pour révision. Étant donné que la vitesse exacte d'un algorithme dépend de l'endroit où l'algorithme s'exécute, ainsi que des détails de mise en œuvre, les informaticiens parlent généralement du temps d'exécution par rapport aux données d'entrée. Par exemple, si l'entrée est constituée de N entiers, alors l'algorithme peut avoir un temps d'exécution proportionnel à N 2 , qui est représenté par O(N 2 ). Cela signifie que si vous exécutez l'implémentation de l'algorithme sur un ordinateur avec une entrée de taille N, cela prendra C*N 2 secondes, où C est une constante qui ne change pas lorsque la taille de l'entrée change.

Cependant, le temps d’exécution de nombreux algorithmes complexes dépend non seulement de la taille des données d’entrée, mais également de nombreux autres facteurs. Par exemple, un algorithme permettant de trier un ensemble d’entiers peut s’exécuter beaucoup plus rapidement si l’ensemble est déjà trié. Il est d'usage de parler du pire des cas d'exécution et du cas d'exécution moyen. Le temps d’exécution dans le pire des cas est la durée maximale pendant laquelle un algorithme peut s’exécuter compte tenu de la « pire » de toutes les entrées possibles. Le cas d'exécution moyen est le temps d'exécution moyen de l'algorithme sur toutes les entrées possibles. Parmi les deux types de temps d’exécution, le pire des cas est le plus facile à raisonner et est donc plus souvent utilisé comme référence pour un algorithme donné. Le processus de détermination du temps d’exécution d’un algorithme dans le pire des cas et dans le cas moyen peut être assez complexe car Il n'est généralement pas possible d'exécuter l'algorithme pour toutes les entrées possibles.

Nous avons vu plus haut qu’un même algorithme peut être écrit de différentes manières. Vous pouvez écrire l'algorithme langage naturel. C'est ainsi que nous utilisons les recettes, les instructions, etc. Pour enregistrer des algorithmes destinés aux artistes formels, spéciaux langages de programmation. Tout algorithme peut être décrit graphiquement sous la forme d'un schéma fonctionnel. Un système de notation spécial a été développé à cet effet :

Désignation	Description	Remarques
	Début et fin de l'algorithme
	Entrée et sortie de données.	La sortie de données est parfois appelée différemment :
	Action	Dans les algorithmes informatiques, cela est utilisé pour désigner l'affectation
	Fourchette	Fork - un composant nécessaire pour implémenter des branches et des boucles
	Démarrer une boucle avec un paramètre
	Processus typique	En programmation - procédures ou sous-programmes
	Transitions entre les blocs

Donnons un exemple de description de l'algorithme de sommation de deux quantités sous forme de schéma bloc :

Cette façon de décrire l’algorithme est la plus visuelle et la plus compréhensible pour les humains. Par conséquent, les algorithmes d'exécution formels sont généralement développés d'abord sous la forme d'un organigramme, puis créent ensuite un programme dans l'un des langages de programmation.

Tri

Le tri est un bon exemple d’algorithme souvent utilisé par les programmeurs. Le moyen le plus simple de trier un groupe d’éléments est de commencer par supprimer le plus petit élément du groupe et de le placer en premier. Ensuite, le deuxième plus grand élément est supprimé et placé en deuxième position, et ainsi de suite. Malheureusement, le temps d'exécution de cet algorithme est O(N 2), ce qui signifie qu'il prendra un temps proportionnel au nombre d'éléments au carré. Si nous devions trier des milliards d’éléments, alors cet algorithme nécessiterait 10 18 opérations. Si nous supposons que les ordinateurs de bureau typiques effectuent environ 10 9 opérations par seconde, il faudra alors des années pour terminer le tri de ces milliards d'éléments.

Heureusement, il existe un certain nombre d’algorithmes plus avancés, tels que le tri rapide, le tri par tas et le tri par fusion. Ces algorithmes ont un temps d'exécution de O(N * Log(N)). Ainsi, le nombre d'opérations nécessaires pour trier des milliards d'éléments est réduit à des limites tellement raisonnables que même l'ordinateur de bureau le moins cher peut effectuer un tel tri. Au lieu d'un milliard d'opérations au carré (10 18), ces algorithmes ne nécessitent que 10 milliards d'opérations (10 10), soit 100 millions de fois plus rapide.

Chemin le plus court

Les algorithmes permettant de trouver le chemin le plus court d’un point à un autre sont étudiés depuis de nombreuses années. Il existe de nombreux exemples d'applications appliquées de ces algorithmes, mais pour des raisons de simplicité de présentation, nous nous en tiendrons à l'énoncé suivant : nous devons trouver le chemin le plus court d'un point A à un point B dans une ville comportant plusieurs rues et intersections. Il existe de nombreux algorithmes différents pour résoudre ce problème et ils ont tous leurs propres avantages et inconvénients. Avant de nous y plonger, examinons le temps d'exécution d'un simple algorithme de force brute. Si un algorithme considère tous les chemins possibles de A à B (qui ne forment pas de cycles), il est peu probable qu’il se termine de notre vivant, même si A et B se trouvent dans une petite ville. Le temps d'exécution de cet algorithme est exponentiel, qui est noté O(C N) pour certains C. Même pour de petites valeurs de C, C N devient un nombre astronomique lorsque N devient modérément grand.

L'un des algorithmes les plus rapides pour résoudre ce problème a un temps d'exécution de O(E+V*Log(V)), où E est le nombre de segments de route et V est le nombre d'intersections. L'algorithme prendra environ 2 secondes pour trouver le chemin le plus court dans une ville de 10 000 intersections et 20 000 segments de route (généralement environ 2 segments de route par intersection). Cet algorithme est connu sous le nom d'algorithme de Dijkstra, il est assez complexe et nécessite l'utilisation d'une structure de données de file d'attente prioritaire. Cependant, dans certains cas, même ce temps d'exécution est trop lent (prenons par exemple pour trouver le chemin le plus court de New York à San Francisco - il y a des millions d'intersections aux États-Unis), dans de tels cas, les programmeurs tentent d'améliorer le temps d'exécution en utilisant ainsi -appelée heuristique. Une heuristique est une approximation de quelque chose qui est pertinent pour une tâche. Dans un problème de chemin le plus court, par exemple, il peut être utile de connaître la distance entre un point et une destination. Sachant cela, vous pouvez développer un algorithme plus rapide (par exemple, l’algorithme de recherche A* fonctionne dans certains cas beaucoup plus rapidement que l’algorithme de Dijkstra). Cette approche n'améliore pas toujours le temps d'exécution de l'algorithme dans le pire des cas, mais dans la plupart des applications du monde réel, l'algorithme s'exécutera plus rapidement.

Algorithmes approximatifs

Parfois, même l’algorithme le plus avancé doté des heuristiques les plus avancées est trop lent sur l’ordinateur le plus rapide. Dans de tels cas, il est nécessaire de réduire la précision du résultat final. Au lieu d’essayer d’obtenir le chemin le plus court, vous pouvez vous limiter à un chemin qui est, par exemple, 10 % plus grand que le chemin le plus court.

En fait, il existe de nombreux problèmes importants pour lesquels les algorithmes actuellement connus produisent trop lentement le résultat optimal. Le groupe le plus connu de ces problèmes est appelé NP (polynôme non déterministe). Si un problème est appelé NP-complet ou NP-difficile, cela signifie que personne ne connaît une méthode suffisamment efficace pour obtenir la solution optimale. De plus, si quelqu'un développe un algorithme efficace pour résoudre un problème NP-difficile, alors cet algorithme peut être appliqué à tous les problèmes NP-difficiles.

Un bon exemple de problème NP-difficile est le problème du voyageur de commerce. Un vendeur souhaite visiter N villes, et il sait combien de temps il faut pour se rendre d’une ville à une autre. La question est de savoir à quelle vitesse pourra-t-il visiter toutes les villes ? L'algorithme connu le plus rapide pour résoudre ce problème est trop lent - et beaucoup pensent qu'il le sera toujours - donc les programmeurs recherchent des algorithmes suffisamment rapides pour donner une bonne solution, mais souvent pas optimale.

Algorithmes aléatoires

Une autre approche utilisée pour résoudre certains problèmes consiste à rendre l’algorithme aléatoire. Cette approche n'améliore pas le temps le plus défavorable de l'algorithme, mais fonctionne bien souvent dans le cas moyen. L'algorithme de tri rapide est un bon exemple d'utilisation de la randomisation. Dans le pire des cas, l'algorithme de tri rapide trie un groupe d'éléments en O(N 2), où N est le nombre d'éléments. Si la randomisation est utilisée dans cet algorithme, les chances que le pire des cas se produise deviennent négligeables et, en moyenne, l'algorithme de tri rapide s'exécute en un temps O(N*Log(N)). D'autres algorithmes garantissent le temps d'exécution de O(N*Log(N)) même dans le pire des cas, mais ils sont plus lents dans le cas moyen. Bien que les deux algorithmes aient un temps d'exécution proportionnel à N*Log(N), l'algorithme de tri rapide a un facteur constant plus petit - c'est-à-dire il nécessite C*N*Log(N), tandis que d'autres algorithmes nécessitent plus de 2*C*N*Log(N) opérations.

Un autre algorithme utilisant des nombres aléatoires recherche la médiane d'un groupe de nombres et sa durée d'exécution moyenne est O(N). C'est beaucoup plus rapide que l'algorithme qui trie les nombres et prend la moyenne, et s'exécute en O(N*Log(N)). Il existe des algorithmes déterministes (non aléatoires) qui peuvent trouver la médiane en un temps O(N), mais l'algorithme aléatoire est plus facile à comprendre et souvent plus rapide que ces algorithmes déterministes.

L'idée principale de l'algorithme de recherche médiane est de sélectionner un nombre aléatoire parmi les nombres et de compter combien de nombres dans le groupe sont inférieurs au nombre sélectionné. Disons qu'il y a N nombres, K d'entre eux sont inférieurs ou égaux au nombre sélectionné. Si K est inférieur à la moitié de N, alors nous savons que la médiane est le (N/2-K)ème nombre supérieur au nombre aléatoire, nous rejetons donc K nombres inférieurs ou égaux au nombre aléatoire. Supposons maintenant que nous voulions trouver le (N/2-K)ème plus petit nombre, au lieu de la médiane. L'algorithme est le même, nous sélectionnons simplement un nombre au hasard et répétons les étapes décrites.

Compression

Une autre classe d'algorithmes est conçue pour la compression des données. Cet algorithme n'a pas de résultat attendu (comme un algorithme de tri), mais optimise selon certains critères. Dans le cas de la compression de données, un algorithme (par exemple LZW) essaie de faire en sorte que les données occupent le moins d'octets possible, mais en même temps, afin qu'elles puissent être décompressées dans leur forme originale. Dans certains cas, ce type d’algorithme utilise les mêmes méthodes que d’autres algorithmes, ce qui donne un bon résultat, mais pas optimal. Par exemple, JPG et MP3 compressent les données de telle manière que le résultat final est de moins bonne qualité que l'original, mais également de plus petite taille. La compression MP3 ne préserve pas toutes les caractéristiques du fichier audio d'origine, mais elle tente de préserver suffisamment de détails pour fournir une qualité acceptable tout en réduisant considérablement la taille du fichier. Le format JPG suit le même principe, mais les détails sont sensiblement différents car... le but est de compresser l'image, pas l'audio.

Pourquoi avez-vous besoin de connaître toutes sortes d’algorithmes ?

Pour utiliser correctement les algorithmes, il est important de connaître tous les types d’algorithmes mentionnés. Si vous devez développer un logiciel important, vous devriez alors pouvoir estimer la vitesse de votre algorithme. La précision de votre estimation dépend de votre maîtrise de l’analyse du temps d’exécution des algorithmes. De plus, il est nécessaire de connaître les détails des algorithmes, ce qui nous permettra de prédire les cas particuliers dans lesquels le programme ne fonctionnera pas rapidement ou produira des résultats inacceptables.

Bien sûr, il y aura des moments où vous tomberez sur des problèmes jusqu’alors inexplorés. Dans de tels cas, vous devez proposer un nouvel algorithme ou appliquer l’ancien algorithme d’une nouvelle manière. Plus vous en savez sur les algorithmes, plus vous avez de chances de trouver une bonne solution à un problème. Dans de nombreux cas, un nouveau problème peut facilement être réduit à un ancien, mais pour ce faire, vous devez avoir une compréhension fondamentale des anciens problèmes.

À titre d'exemple, considérons le fonctionnement des commutateurs réseau. Le commutateur est connecté à N câbles et reçoit les paquets de données provenant de ces câbles. Le commutateur doit d'abord analyser les paquets, puis les renvoyer via le câble approprié. Un commutateur, comme un ordinateur, fonctionne en mode discret : les paquets sont envoyés à intervalles discrets plutôt qu'en continu. Un commutateur rapide s'efforce d'envoyer autant de paquets que possible pendant chaque intervalle, sinon ils s'accumuleront et le commutateur plantera. Le but de l'algorithme est d'envoyer le nombre maximum de paquets pendant chaque intervalle, et également de garantir un ordre dans lequel les paquets arrivant plus tôt que les autres sont également envoyés plus tôt que les autres. Dans ce cas, il s’avère qu’un algorithme appelé « correspondance stable » est adapté pour résoudre ce problème, même si à première vue cela n’est pas évident. De telles connexions entre problème et solution ne peuvent être découvertes qu’en utilisant des connaissances algorithmiques déjà existantes.

Exemples réels

Il existe de nombreux exemples de solutions à des problèmes réels qui nécessitent les algorithmes les plus récents. Presque tout ce que vous faites sur un ordinateur dépend d’algorithmes que quelqu’un a mis beaucoup de temps à développer. Même les programmes les plus simples n’existeraient pas sans les algorithmes qui fonctionnent en arrière-plan pour gérer la mémoire et charger les données du disque dur.

Il existe des dizaines d'exemples d'utilisation d'algorithmes complexes, mais nous aborderons deux problèmes dont la solution nécessite les mêmes compétences que la résolution de certains problèmes sur TopCoder. Le premier problème est connu sous le nom de problème de débit maximum, et le second implique la programmation dynamique, une technique qui peut souvent résoudre des problèmes à une vitesse apparemment impossible.

Algorithme pour trouver le débit maximum

Le problème de trouver le débit maximum est d’utiliser le réseau existant pour déplacer au mieux quelque chose d’un endroit à un autre. Ce problème particulier s’est posé pour la première fois dans les années 1950 à propos des lignes ferroviaires de l’Union soviétique. Les États-Unis voulaient savoir à quelle vitesse l’Union soviétique pourrait transporter des matériaux vers ses États satellites d’Europe de l’Est via son réseau ferroviaire.

En outre, les États-Unis voulaient savoir quelle partie des rails pouvait être détruite le plus facilement afin de couper les États satellites du reste de l'Union soviétique. Il s’est avéré que les deux problèmes étaient étroitement liés et que la résolution du problème du débit maximum résolvait également le problème de la coupure minimale, ce qui révélerait finalement le moyen le moins coûteux de couper l’Union soviétique de ses satellites.

Le premier algorithme efficace pour trouver le débit maximum a été inventé par les scientifiques Ford et Fulkerson. L'algorithme a ensuite été nommé algorithme de Ford-Fulkerson et est l'un des algorithmes les plus célèbres dans le domaine de l'informatique. Au cours des 50 dernières années, l’algorithme a subi un certain nombre d’améliorations, le rendant plus rapide (même si certaines de ces améliorations sont redoutables par leur complexité).

La tâche étant clairement définie, de nombreuses applications différentes ont été découvertes. L’algorithme est directement connecté à Internet, où il est important de transporter un maximum de données d’un point à un autre. Le problème se pose également dans divers processus métiers et constitue une partie importante de la recherche opérationnelle. Par exemple, s'il y a N employés et N tâches à accomplir, mais que tous les employés ne peuvent pas gérer toutes les tâches, alors trouver le flux maximum donnera une solution pour affecter N employés à des tâches de telle sorte que chaque tâche soit terminée à condition que Peut-être . Le problème de graduation de TopCoder SRM 200 est un bon exemple de problème de flux maximum.

Comparaison de séquence

De nombreux codeurs n’ont jamais eu à mettre en œuvre un algorithme utilisant la programmation dynamique au cours de toute leur carrière. Cependant, la programmation dynamique est utilisée dans un certain nombre d’algorithmes importants. L'un des algorithmes consiste à trouver les différences entre deux séquences, que la plupart des programmeurs ont probablement utilisées, même s'ils ne l'ont peut-être pas compris. Cet algorithme calcule le nombre minimum d'insertions, de suppressions et de modifications requises pour convertir la séquence A en séquence B.

Par exemple, considérons les séquences « AABAA » et « AAAB ». Pour convertir la première séquence en seconde, le plus simple est de supprimer le B du milieu et de changer le dernier A en B. Cet algorithme a de nombreuses applications, notamment certains problèmes liés à la détection de l'ADN et du plagiat. Cependant, de nombreux programmeurs l'utilisent principalement pour comparer les versions du même fichier de code source. Si les éléments de la séquence sont des lignes d'un fichier, alors cet algorithme permet de savoir quelles lignes doivent être supprimées, insérées, modifiées afin de convertir une version du fichier en une autre.

Sans programmation dynamique, il faut passer par un nombre exponentiel de transformations pour passer d’une séquence à une autre. Cependant, la programmation dynamique réduit le temps d'exécution de l'algorithme à O(N*M), où N et M sont le nombre d'éléments dans deux séquences.

Conclusion

Comme il existe de nombreux problèmes différents, il existe autant d’algorithmes différents pour les résoudre. Cependant, il y a de fortes chances que le problème que vous essayez de résoudre soit similaire à un autre problème d’une certaine manière. En développant une compréhension approfondie d’un large éventail d’algorithmes, vous serez en mesure de sélectionner le bon algorithme et de l’appliquer pour résoudre un problème. De plus, résoudre des problèmes lors de compétitions sur TopCoder vous aidera à perfectionner vos compétences dans ce domaine. Beaucoup de ces problèmes semblent artificiels et irréalistes, mais ils nécessitent le même ensemble de connaissances algorithmiques que celles requises quotidiennement dans le monde réel.

Programmation

Tâche

1.Action

2. Processus

3 ALGORITHME instructions.

4. PROGRAMME

Niveau inférieur compilateur ou interprète.

Compilateur

Interprète

Données d'entrée (périphérique d'entrée) -> Mémoire (programme) (données internes) -><->Processeur.

Deux composants principaux d'un ordinateur :

1) MÉMOIRE données

Capacité (taille);

2) PROCESSEUR

Représentation des données dans la mémoire de l'ordinateur. Le concept de variable, constante, type, plage de valeurs.

Dans les algorithmes et les programmes, les données se présentent sous forme de constantes et de variables.

CONSTANTE est une valeur constante déterminée par sa valeur.

VARIABLE- une grandeur dont la valeur peut changer au cours du processus de calcul.

Variable du programme est une zone de mémoire nommée et une constante de programme est une zone de mémoire sans nom où une valeur d'un certain type est stockée. La particularité des variables du programme est qu'elles ont toujours des valeurs spécifiques et ces valeurs peuvent être modifiées plusieurs fois lors des calculs.

Le type d’une constante est déterminé par la forme sous laquelle elle est écrite. Le type d'une variable est déterminé par l'ensemble des valeurs qu'elle peut prendre.

Les principaux types utilisés dans les algorithmes des machines sont intact, des choses, enregistrer Et allumé.

Les valeurs des variables entières sont des nombres : 0, 1, -1, 2, -2,..., qui sont représentés exactement dans la mémoire de la machine.

Les valeurs des variables réelles sont des nombres réels, écrits sous forme de fractions décimales : 0,5, 1,2*10^6. Les nombres réels en mémoire sont présentés avec arrondi.

Les valeurs des variables booléennes sont les valeurs booléennes : vrai (1) et faux (0).

Les valeurs des variables de lettres sont des lettres ou des chaînes de lettres de certains alphabets - russe, latin, etc. : "upchk!!!11", "x=".

Lorsqu'elles sont placées dans la mémoire de la machine, chaque constante et variable se voit attribuer une section de mémoire distincte. Le nom de la variable est l'adresse de cette section.

Chaque instruction de programme occupe également une zone mémoire dont la longueur dépend du type d'instruction.

En raison de la zone limitée où se trouvent les variables et les constantes, il est impossible de placer et de former des chaînes de chiffres et de lettres de n'importe quelle taille. Par conséquent, pour chaque ordinateur et chaque langue, un nom. valeurs maxcel - entier max, minvesch, maxvesch et maxlit. Les calculs dont les résultats se situent en dehors de ces plages entraîneront des exceptions machine.

La principale propriété de ces types de données est l'indivisibilité de leurs valeurs. Chaque valeur est un objet qui ne se décompose pas en composants. Ces objets sont représentés dans la mémoire de la machine par de simples variables.

Les variables composées de plusieurs composantes sont appelées variables structurelles. Une variable avec une structure de tableau est un ensemble de composants - des variables du même type. Pour désigner des composants, le nom d'une variable tableau est utilisé avec un index qui indique de manière unique l'objet souhaité.

Exigences pour la qualité d'un produit logiciel. Critères de qualité de base.

Une condition nécessaire à la production de masse et à la mise en œuvre de systèmes logiciels est l'organisation de la production industrielle de ces systèmes. Il doit donc y avoir une technologie de programmation, c'est-à-dire une méthode de conduite du processus de production de logiciels qui garantit la planification, le développement et la livraison des systèmes logiciels à temps. Les programmes doivent être soumis à des exigences en tant que produit industriel pouvant être utilisé en dehors de l'organisation de développement et qui doit être fourni pour la réplication, la mise en œuvre, la maintenance et le développement.

Les exigences suivantes sont imposées au produit logiciel :

1. Performances- la possibilité d'exécuter le programme sur une machine existante.

2. Exactitude (exactitude)- stricte conformité des résultats obtenus lors de l'exécution du programme avec les exigences de l'énoncé du problème pour toute donnée initiale acceptable.

3. Fiabilité- aucun échec lors de l'exécution du programme, même pour des données mal codées ou invalides.

4. Efficacité- temps minimal pour obtenir une solution au problème dans son ensemble, comprenant à la fois le temps d'exécution du programme et le temps de développement, de test et de débogage du programme et des données.

5.Documents- disponibilité des instructions d'utilisation et des descriptions de la logique interne du programme.

6. Mobilité- indépendance du programme par rapport à la mise en œuvre spécifique.

7. Ergonomie- le programme vous permet de minimiser les efforts de l'utilisateur dans la préparation des données initiales, le traitement des données et l'évaluation des résultats obtenus.

8. Lisibilité- le programme doit être compréhensible.

Énoncé du problème.

2. Analyse de la problématique et préparation des spécifications du programme- à ce stade, le problème est analysé, sa formulation est clarifiée et les exigences du programme sont élaborées. Une description complète et précise du programme est créée, appelée sa spécification. Habituellement, quatre points principaux sont précisés : les données d'entrée/sortie, la méthode et les anomalies. Spécification de la tâche- document. Sert de tâche pour développer un programme (le développeur du programme doit en extraire tout ce qu'il a besoin de savoir sur la tâche qui lui est confiée) ; fait partie d'un accord entre le client du programme et son développeur, une description de la tâche qui est acceptable pour le client, qui n'est pas nécessairement compétent en programmation ; il doit être utilisé pour vérifier le programme terminé (si le programme développé résout le problème).

3. Conception d'algorithmes et de structures de données et conception de tests- à ce stade, la structure générale du programme est formée. L'approche fondamentale du développement de programmes et de systèmes logiciels est la conception descendante. La conception descendante repose sur l'idée de révéler progressivement les détails du programme conçu à mesure qu'il passe de l'objectif général formulé au plus haut niveau dans l'énoncé du problème au niveau des objets exprimés en termes « compréhensibles par un ordinateur ». » L'algorithme est écrit dans un métalangage conçu pour décrire la logique interne du programme, ainsi que pour capturer les décisions de conception pour organiser les calculs.

4. Codage de l'algorithme dans un langage de programmation- à ce stade l'algorithme est traduit d'un métalangage vers un langage de programmation.

5. Débogage (y compris tests), prévention des erreurs - le but de cette étape est d'obtenir un programme correct, c'est-à-dire un programme dans lequel il n'y a pas d'erreurs de conception (erreurs pouvant survenir à toutes les étapes du développement du programme, y compris les erreurs qui apparaissent en raison d'un écart entre les exigences du client et les actions de l'entrepreneur). Techniques de débogage : contrôle visuel, contrôle syntaxique, contrôle de la structure du programme, tests.

6.Documents- un processus de développement de programme correctement structuré vous permet de recevoir la documentation en parallèle, de sorte qu'à la fin du débogage, presque toute la documentation nécessaire soit obtenue.

Exécution du programme.

Les 4 premières étapes sont réalisées séquentiellement. La cinquième étape est répartie sur toutes les étapes - chacune se termine par la préparation de la documentation.

La technologie est un ensemble de méthodes, ainsi que de règles et procédures pour leur application, qui garantissent la production d'un produit de qualité dans les délais.

La technologie de programmation moderne est invariante par rapport à un langage, une classe de problèmes et un ordinateur spécifiques.

Technologie de programmation structurée :

1. Conception descendante des algorithmes et des données.

2. Séquence stricte des étapes de programmation.

3. Respect des exigences de qualité des produits.

Saisie de données

Pour saisir les données sources, la procédure ReadLn est le plus souvent utilisée :

LireLn(A1,A2,...AK);

La procédure lit les valeurs K des données source et attribue ces valeurs aux variables A1, A2, ..., AK.

Lors de la saisie des données sources, une transformation se produit de la forme externe de représentation à la forme interne, déterminée par le type de variables. Les variables qui composent la liste d'entrée peuvent être de type entier, réel ou caractère. La lecture de données source booléennes n'est pas autorisée en Pascal.

Les valeurs des données sources peuvent être séparées les unes des autres par des espaces et en appuyant sur les touches Tab et Entrée.

Il n'est pas permis de séparer les nombres saisis par des virgules !

<оператор #1>;
<оператор #2>;
<оператор #3>;
. . .

Jusqu'à <условие>

Cela se lit comme ceci : "Exécuter l'instruction n°1, l'instruction n°2. : jusqu'à ce que la condition soit remplie."

Cycle PENDANT :

alors que est un cycle dans lequel la condition est devant le corps. De plus, le corps de la boucle est exécuté si et seulement si la condition vrai; dès que la condition devient FAUX, l'exécution de la boucle s'arrête.

Tandis que a le format :

alors que < условие> faire<оператор 1>; (Au revoir... fais....)

Cette boucle ne convient que pour une seule instruction, si vous souhaitez utiliser plusieurs instructions dans votre code, vous devez les mettre entre crochets - commencer Et fin; .

21. Implémentation d'une boucle paramétrique en Pascal. Syntaxe et sémantique, restrictions d'utilisation.

Souvent, certaines actions doivent être répétées plus d'une fois et le nombre de répétitions peut être calculé à l'avance. Par exemple, traitez les éléments d'un tableau de manière séquentielle. Pour implémenter efficacement ce type d'algorithmes en PL, citons boucles avec paramètre.

Les instructions de boucle sont utilisées pour répéter plusieurs instructions en leur sein. Dans le langage Turbo Pascal, on distingue les opérateurs de boucle de type progression arithmétique (opérateur de boucle avec un compteur FOR) avec des pas de +1 ou -1 et les opérateurs de boucle de type itératif (While et Repeat)

Un opérateur de boucle de type progression arithmétique est utilisé si le nombre de répétitions de la boucle et l'étape de modification du paramètre de boucle +1 ou -1 sont connus à l'avance.

Pour<параметр цикла>:=<выражение1>à <выражение 2> faire <оператор(тело цикла>; - étape de modification du paramètre de cycle +1

Jusqu'à - -1

Var f1:texte

attribuer(f1,"fichier.txt");

réinitialiser (f1);

La procédure de saisie du tableau peut avoir différents degrés de polyvalence

1) l'initialisation des fichiers et la saisie de la longueur du tableau ont lieu dans le programme principal ;

(comme dans l'exemple ci-dessous) ; et l'entrée du tableau est dans la procédure ;

(entrée: f– nom personnel, n– longueur du tableau ; sortie: X- tableau)

Procédure Input1_mas (var f : texte ; n : ind ; var X : mas) ;

2) les fichiers sont initialisés dans le programme principal et la longueur du tableau ainsi que le tableau lui-même sont saisis dans la procédure ;

(entrée: f– nom f.p., sortie : n– longueur du tableau ; X- tableau)

Procédure Input2_mas (var f : texte ; var n : ind ; var X : mas ) ;

3) les noms de fichiers externes sont saisis dans le programme principal, et l'initialisation des fichiers et la saisie de la longueur du tableau et du tableau lui-même sont saisis dans la procédure ;

(entrée: Nomf– nom de fichier externe, sortie : n– longueur du tableau ; X- tableau)

Procédure Input3_mas (Namef : str8 ; var n : ind ; var X : mas) ;

4) la procédure effectue toutes les opérations : saisie des noms de fichiers externes, initialisation des fichiers et saisie de la longueur du tableau et du tableau lui-même

(entrée : --, sortie : n– longueur du tableau ; X- tableau)

Procédure Input4_mas (var n : ind ; var X : mas) ;

Parce que réel Le (vrai) tableau est défini externe nom de fichier Nomf Et longueur n tableau, alors ce sont ces variables qu'il est souhaitable de gérer dans le programme principal. De ce point de vue, l’option la plus préférable est :

5) les noms de fichiers externes et les longueurs de tableau sont saisis dans le programme principal, et l'initialisation des fichiers et l'entrée du tableau lui-même sont saisis dans la procédure ;

(entrée: Nomf– nom du fichier externe, n– longueur du tableau ; sortie: X- tableau)

Procédure Input5_mas (Namef : str8 ; n : ind ; var X : mas) ;

Concepts de base de la programmation. Action, processus, algorithme, programme.

Programmation est un moyen de résoudre des problèmes à l’aide d’un PC.

Tâche- il s'agit d'une question à laquelle il faut répondre, ou d'une exigence à remplir, en fonction des conditions et en tenant compte des restrictions spécifiées dans la tâche.

1.Action-engagé par un certain objet et conduit à un résultat spécifique (personnage, heure)

Le concept le plus important est l’ACTION. Une action est effectuée sur un objet et conduit à un certain résultat. Si une action peut être décomposée en ses éléments constitutifs, elle est alors appelée un PROCESSUS. Sinon, il s'agit d'une action élémentaire.

2. Processus- une action décomposable en actions élémentaires.

Série (l'un après l'autre) parallèle (simultanément)

appelé PROCESSEUR. un interprète qui exécute des actions élémentaires selon des instructions (humaines, automatiques, informatiques).

3 . Chaque action peut être décrite à l'aide d'un langage ou d'un système de formules. ALGORITHME- ceci est une description du processus, c'est-à-dire description d'une séquence d'actions élémentaires conduisant à un résultat spécifique. Chaque action élémentaire est appelée. instructions.

4. PROGRAMME appelé algorithme écrit dans un langage qu’un ordinateur peut comprendre. La différence entre un algorithme général et un programme machine est que dans ce dernier les règles de comportement doivent être précisées dans les moindres détails et il doit être compilé en stricte conformité avec les règles d'enregistrement définies pour la machine utilisée.

Il existe plusieurs niveaux de langage. Niveau inférieur- langage machine interne (code machine : 0 et 1). Un programme en langage de haut niveau peut être entré dans une machine, mais ne peut pas être exécuté. Un programme qui traduit (traduit) un programme d'un langage de haut niveau vers le langage interne d'une machine est appelé traducteur : compilateur ou interprète.

Compilateur- un programme qui traduit du code d'un langage de haut niveau vers un langage machine : d'abord traduction, puis exécution du programme (Pascal).

Interprète traduit chaque action et l'exécute immédiatement, opérateur par opérateur (Basic).

2. Structure fonctionnelle d'un ordinateur. Appareils informatiques de base, leurs caractéristiques fonctionnelles.

Données d'entrée (périphérique d'entrée) -> Mémoire (programme) (données internes) -> Données de sortie (périphérique de sortie). Deux flèches en mémoire<->Processeur.

Deux composants principaux d'un ordinateur :

1) MÉMOIRE(mémoire). La mémoire contient des objets codés sur lesquels des actions sont effectuées. Ces objets codés sont appelés. données. Principales caractéristiques de la mémoire :

Capacité (taille);

La vitesse à laquelle les données sont écrites et récupérées de la mémoire.

2) PROCESSEUR est un appareil qui remplit 2 fonctions principales :

Effectue des actions sur les données ;

Contrôle la séquence d'actions dans les programmes.

Pendant que le processeur est en cours d'exécution, les instructions et les données du programme sont récupérées (lues) de la mémoire et les résultats sont écrits (écrits) dans la mémoire.

Que. La mémoire joue le rôle de « chambre de stockage » pour le processeur et est utilisée à la fois pour le stockage des programmes et pour le stockage des données.

Les données internes traitées par le programme sont constituées de données d'entrée, de sortie et intermédiaires.

Les données d'entrée, dont les valeurs sont connues à partir des conditions problématiques, entrent dans la mémoire de la machine à partir du périphérique d'entrée à la demande du programme.

Les données de sortie résultant de la résolution du problème sont émises par le programme sous une forme lisible par l'homme vers le périphérique de sortie.

Les données intermédiaires, qui sont le résultat des calculs intermédiaires du programme, constituent l'environnement interne du programme.

Algorithme? un ensemble d'instructions décrivant l'ordre des actions de l'interprète pour obtenir le résultat de la résolution d'un problème en un nombre fini d'actions. Dans l’ancienne interprétation, au lieu du mot « ordre », le mot « séquence » était utilisé, mais à mesure que le parallélisme dans le fonctionnement informatique se développait, le mot « séquence » a commencé à être remplacé par le mot plus général « ordre ». Cela est dû au fait que le fonctionnement de certaines instructions de l'algorithme peut dépendre d'autres instructions ou des résultats de leur travail.

Ainsi, certaines instructions doivent être exécutées strictement après que les instructions dont elles dépendent soient terminées. Les instructions indépendantes, ou rendues indépendantes par l'achèvement des instructions dont elles dépendent, peuvent être exécutées dans un ordre aléatoire, en parallèle, ou simultanément, si le processeur et le système d'exploitation utilisés le permettent.

Un algorithme signifie une description exacte d'un certain processus, des instructions pour sa mise en œuvre. Le développement d’algorithmes est un processus complexe et long. Algorithmisation ? Il s'agit d'une technique permettant de développer (composer) un algorithme permettant de résoudre des problèmes sur un ordinateur. Le schéma fonctionnel de l'algorithme généralisé du programme est présenté dans la figure 3.9.

Figure 3.9 - Schéma fonctionnel de l'algorithme du programme

Pour enregistrer l'algorithme de résolution d'un problème, les méthodes visuelles suivantes pour les représenter sont utilisées :

· description verbale et formelle ;

· schéma fonctionnel (schéma de symboles graphiques) ;

· langages algorithmiques ;

· diagrammes d'opérateurs ;

· pseudocode ;

Développement de produits logiciels

Depuis l'avènement de la plateforme .NET (vers 2001), les bibliothèques de classes de base incluent une API appelée Windows Forms, représentée principalement par l'assembly System.Windows.Forms.dll. La boîte à outils Windows Forms fournit les types nécessaires pour créer des interfaces utilisateur graphiques pour les ordinateurs de bureau, créer des contrôles personnalisés, gérer les ressources (telles que les lignes et les icônes) et effectuer d'autres tâches rencontrées lors de la programmation pour les ordinateurs de bureau. Il existe également une API supplémentaire appelée GDI+ (représentée par l'assembly System.Drawing.dll), qui fournit des types supplémentaires permettant au programmeur de générer des graphiques 2D, d'interagir avec les imprimantes réseau et de traiter les données graphiques.

Windows Forms (et GDI+) sont natifs de la plate-forme .NET 4.0 et seront probablement présents pendant un certain temps (peut-être longtemps) dans le cadre de la bibliothèque de classes de base. Certes, après la sortie de .NET 3.0, Microsoft a publié une toute nouvelle API d'outil appelée Windows Présentation Foundation (WPF).

Sans aucun doute, l’espace de noms Windows Forms le plus important est System.Windows.Forms. Les types de cet espace de noms peuvent être répartis dans les grandes catégories suivantes :

· Infrastructures de base. Il s'agit de types qui représentent les opérations de base des programmes qui utilisent Windows Forms (Formulaire et Application) et de divers types conçus pour interagir avec les contrôles ActiveX existants, ainsi que pour interagir avec les nouveaux contrôles WPF personnalisés ;

· Éléments de contrôle. Ces types sont utilisés pour créer des interfaces utilisateur graphiques (telles que Button, MenuStrip, ProgressBar et DataGridView), qui dérivent toutes de la classe de base Control. Les contrôles sont personnalisables au moment de la conception et visibles (par défaut) au moment de l'exécution ;

· Composants. Il s'agit de types qui ne sont pas dérivés de la classe de base Control, mais qui peuvent néanmoins fournir des fonctionnalités visuelles aux programmes Windows Forms (par exemple, ToolTip et ErrorProvider). De nombreux composants (par exemple, Timer et System.ComponentModel.BackgroundWorker) ne sont pas visibles au moment de l'exécution, mais peuvent toujours être personnalisés au moment de la conception ;

· Fenêtres de dialogue standard. Windows Forms est livré avec plusieurs boîtes de dialogue prédéfinies pour les opérations courantes (par exemple, OpenFileDialog, PrintDialog et ColorDialog).

Dans le monde Windows Forms, le type Form représente n'importe quelle fenêtre d'une application, y compris la fenêtre principale de niveau supérieur, les fenêtres enfants des applications MDI (Multiple Document Interface) et les boîtes de dialogue modales et non modales. Le type Form contient de nombreuses fonctionnalités héritées de ses classes ancêtres, ainsi que des nombreuses interfaces qu'il implémente.

De nombreuses autres classes de base et interfaces sont nécessaires pour générer entièrement un type de formulaire, mais même un développeur Windows Forms professionnel n'a pas besoin de connaître les rôles de tous les membres de toutes les classes ou interfaces implémentées.

Pour créer un nouveau projet dans Visual Studio, sélectionnez « Nouveau » - « Projet », dans la fenêtre qui apparaît, sélectionnez « Application Windows Form » et remplissez les champs proposés.

Pour transmettre la requête SQL au serveur et renvoyer le résultat sous forme d'un ensemble de lignes (requêtes de sélection), la méthode « GetSQLData » présentée ci-dessous a été implémentée.

La méthode prend une chaîne de requête comme paramètre et a un type « DataTable » comme valeur de retour ? tableau de données.

DataTable statique publique GetSQLData (requête de chaîne)

DataSetds = new DataSet();

maConnexion.Open();

attraper (exception e1)

SqlDataAdapter dataAdapter = new SqlDataAdapter(comm);

ds = nouveau DataSet();

dataAdapter.Fill(ds);

MessageBox.Show("Erreur");

maConnexion.Close();

attraper (exception e3)

retourner ds.Tables ;

Pour transmettre une requête SQL au serveur sans renvoyer de résultat (requêtes d'insertion, de modification et de suppression), la méthode « SetSQLData » présentée ci-dessous a été implémentée. La méthode prend une chaîne de requête comme paramètre et n'a aucun type de retour.

public static void SetSQLData (requête de chaîne)

SqlConnection myConnection = new SqlConnection(Config.ConnectionString);

maConnexion.Open();

attraper (exception e1)

MessageBox.Show(e1.ToString());

SqlCommand comm = new SqlCommand(query);

comm.CommandType = System.Data.CommandType.Text;

comm.Connection = maConnexion ;

comm.ExecuteNonQuery();

maConnexion.Close();

attraper (exception e3)

MessageBox.Show(e3.ToString());

Pour garantir que l'utilisateur n'a pas besoin de saisir une chaîne de connexion à la base de données, il est également nécessaire de créer une classe et un fichier de configuration qui stockeraient et permettraient de modifier les paramètres de l'application. À ces fins, la classe « Config » et le fichier de configuration « App.config » ont été créés respectivement.

chaîne statique publique ConnectionString = GetParam("ConnectionStringSql");

chaîne publique Connexion

renvoie la chaîne de connexion ;

ConnectionString = valeur ;

chaîne statique publique GetPathTo (string ParamName)

retourner Application.StartupPath +

ConfigurationManager.OpenExeConfiguration(ConfigurationUserLevel.None).AppSettings.Settings.Value;

La variable "Connexion" de cette classe est la chaîne de connexion au serveur. Au lancement, il est initialisé à partir du fichier de paramètres grâce à la méthode « GetParam » présentée ci-dessous.

chaîne statique publique GetParam (string ParamName)

retourner ConfigurationManager.OpenExeConfiguration(ConfigurationUserLevel.None).AppSettings.Settings.Value;

"App.config" - un fichier XML contenant des variables et leurs valeurs explicitement ou implicitement spécifiées. Le texte du document XML des paramètres utilisateur généré est présenté ci-dessous.

connectionString="Chaîne de connexion valide;" />

Les gestionnaires de divers événements d'élément sont créés dans l'onglet « Événements ». Par exemple, l'événement « OnClick » signifie « cliquer sur un bouton ». Après avoir double-cliqué sur l'événement requis, le code du formulaire avec un gestionnaire déclaré s'ouvrira, dans lequel vous devrez ajouter du code pour gérer l'événement émergent.

Ajoutons le code suivant au gestionnaire d'événements OnClick pour appeler un autre formulaire de candidature :

bouton vide privé1_Click (expéditeur de l'objet, EventArgs e)

NouveauTest obj = nouveau NouveauTest();

obj.ShowDialog();

Nous appellerons tous les formulaires de candidature de la même manière. Pour lire la sélection dans le tableau de notre formulaire, nous ajouterons la méthode « Load_Tables » à son code.

listView1.Items.Clear();

DateHeure d = new DateTime();

pour (int je = 1; je< dt.Columns.Count; i++)

listView1.Items.Add(élément);

La ligne « requête » dans cette méthode est une requête pour sélectionner la base de données. Vous pouvez maintenant commencer à concevoir et à implémenter d’autres formes d’application.

Vous pouvez ajouter un formulaire au projet en cours à partir de la fenêtre contextuelle « Explorateur de solutions » ou via le menu « Projet » - « Ajouter un formulaire Windows ». Dans la fenêtre qui apparaît, saisissez le nom du formulaire à créer et cliquez sur « Ajouter ».

Les tâches pour ces éléments sur ce formulaire seront les suivantes :

1. GroupBox - regroupement de champs similaires pour saisir ou sélectionner des informations ;

2. TextBox - un champ pour saisir manuellement les informations qui seront ensuite utilisées dans les demandes ;

3. Étiquette - une indication pour l'utilisateur sur la signification d'un champ particulier ainsi que sur les données qui doivent être saisies ;

4. Bouton - confirmation de l'action de l'utilisateur, lue par le système.

Si vous sélectionnez l'un ou l'autre élément « RadioButton » (« Étudiant » ou « Enseignant »), les champs de saisie des données de l'élève ou de l'enseignant seront respectivement déverrouillés. En cliquant sur le bouton « Commencer », l'autorisation est effectuée.

Le formulaire de demande suivant est le formulaire permettant d'ajouter et de modifier des données de test.

Les données des champs « Nom », « Nombre de questions » et « Enseignant » sont lues et envoyées au serveur SQL à l'aide d'une requête d'insertion dans la méthode « SetSQLData » de la classe « Connexion ».

En cas de succès ou d'échec, un message correspondant sera affiché à l'utilisateur.

Lors du chargement du formulaire, notre liste déroulante « Enseignant » (l'élément « ComboBox ») doit être initialisée et remplie avec un certain ensemble de valeurs que l'utilisateur peut sélectionner. Pour cela, ajoutez la méthode « LoadComboboxes » au code du formulaire dont le code est donné ci-dessous.

vide privé LoadComboboxes()

query = "Sélectionner un enseignant parmi les enseignants" ;

DataTable dt = Connection.GetSQLData(query);

comboBox1.DataSource = dt;

comboBox1.DisplayMember = "Enseignant";

MessageBox.Show("Erreur de chargement du répertoire<Преподаватели>");

Le formulaire suivant de la demande est le rapport « Résultats des tests ». Nous ajoutons un formulaire comme décrit précédemment, plaçons l'élément « ListView » sur le formulaire et donnons au formulaire l'apparence suivante.

Ce rapport regroupe toutes les tentatives des étudiants inscrits pour réussir les tests en utilisant le système. Pour lire le tableau reçu du serveur SQL, ajoutez la méthode ci-dessous au code du formulaire.

private void Load_Tables (requête de chaîne)

listView1.Items.Clear();

DataTable dt = Connection.GetSQLData(query);

foreach (ligne DataRow dans dt.Rows)

DateHeure d = new DateTime();

Élément ListViewItem = new ListViewItem(row.ToString());

pour (int je = 1; je< dt.Columns.Count; i++)

si (i == dt.Columns.Count - 1)

d = Convert.ToDateTime(ligne[i]);

item.SubItems.Add(d.ToShortDateString());

item.SubItems.Add(row[i].ToString());

listView1.Items.Add(élément);

Le formulaire suivant est le formulaire de test de connaissances. L'élément « DateTimePicker » est placé sur le formulaire pour suivre avec précision les heures de début et de fin du test. Cet élément est masqué à l'utilisateur et n'est pas affiché.

Pour travailler à modifier les questions et réponses du test, nous allons ajouter un autre formulaire et lui donner l'apparence suivante.

De la même manière, d'autres formes de système automatisé de test des connaissances pour la discipline « Langue russe » ont été créées et mises en œuvre. Les fonctionnalités du programme sont présentées plus en détail dans la section « Guide de l'utilisateur » et dans l'annexe « Liste des codes de programme ».