Arten von Algorithmen – Wissens-Hypermarkt. B6

Stichworte:

• Algorithmus
• Eigenschaften des Algorithmus
  • Diskretion
  • Klarheit
  • Sicherheit
  • Wirksamkeit
  • Massencharakter
• Testamentsvollstrecker

• Eigenschaften des Darstellers
  • Umfang der zu lösenden Aufgaben
  • Mittwoch
  • Betriebsart
  • Befehlssystem
• formale Ausführung des Algorithmus

3.1.1. Algorithmuskonzept

Jeder Mensch löst im Alltag, im Studium oder im Beruf eine Vielzahl von Problemen unterschiedlicher Komplexität. Komplexe Probleme erfordern viel Nachdenken, um eine Lösung zu finden. Ein Mensch löst einfache und vertraute Aufgaben automatisch, ohne nachzudenken. In den meisten Fällen kann die Lösung jedes Problems in einfache Phasen (Schritte) unterteilt werden. Für viele dieser Aufgaben (Software installieren, einen Schrank zusammenbauen, eine Website erstellen, ein technisches Gerät bedienen, ein Flugticket über das Internet kaufen usw.) wurden bereits Schritt-für-Schritt-Anleitungen entwickelt und angeboten, die sequentiell sind deren Umsetzung zum gewünschten Ergebnis führen kann.

Beispiel 1. Das Problem „Ermitteln Sie das arithmetische Mittel zweier Zahlen“ wird in drei Schritten gelöst:

• denke an zwei Zahlen;
• Fügen Sie zwei Zahlen hinzu.
• Teilen Sie den resultierenden Betrag durch 2.

Beispiel 2. Die Aufgabe „Geld auf Ihr Telefonkonto einzahlen“ gliedert sich in folgende Schritte:

• Gehen Sie zum Zahlungsterminal.
• Wählen Sie einen Telekommunikationsbetreiber aus.
• Eine Telefonnummer eingeben;
• Überprüfen Sie, ob die eingegebene Nummer korrekt ist.
• eine Banknote in den Geldscheinprüfer einführen;
• Warten Sie auf eine Nachricht über die Gutschrift des Geldes auf Ihrem Konto.
• einen Scheck erhalten.

Beispiel 3. Die Phasen der Lösung des Problems „Zeichne einen lustigen Igel“ werden grafisch dargestellt:

Das arithmetische Mittel ermitteln, Geld auf ein Telefonkonto einzahlen und einen Igel zeichnen sind auf den ersten Blick völlig unterschiedliche Vorgänge. Sie haben jedoch ein gemeinsames Merkmal: Jeder dieser Prozesse wird durch eine Reihe kurzer Anweisungen beschrieben, deren strikte Einhaltung es Ihnen ermöglicht, das gewünschte Ergebnis zu erzielen. Die in den Beispielen 1-3 angegebenen Befehlsfolgen sind Algorithmen zur Lösung der entsprechenden Probleme. Der Ausführende dieser Algorithmen ist eine Person.

Der Algorithmus kann eine Beschreibung einer bestimmten Berechnungsfolge (Beispiel 1) oder Schritte nichtmathematischer Natur (Beispiele 2-3) sein. In jedem Fall müssen jedoch vor der Entwicklung die Ausgangsbedingungen (Ausgangsdaten) und das zu erreichende Ergebnis (Ergebnis) klar definiert werden. Wir können sagen, dass ein Algorithmus eine Beschreibung der Abfolge von Schritten zur Lösung eines Problems ist, die von den Ausgangsdaten bis zum erforderlichen Ergebnis führt.

Im Allgemeinen lässt sich das Funktionsdiagramm des Algorithmus wie folgt darstellen (Abb. 3.1):

Reis. 3.1.
Allgemeines Schema des Algorithmus

Algorithmen sind die Regeln der Addition, Subtraktion, Multiplikation und Division von Zahlen, grammatikalische Regeln, Regeln geometrischer Konstruktionen usw., die in der Schule gelernt werden.

Animationen „Arbeiten mit einem Algorithmus“, „Größter gemeinsamer Teiler“, „Kleinstes gemeinsames Vielfaches“ (http://school-collection.edu.ru/) helfen Ihnen, sich an einige Algorithmen zu erinnern, die im Russisch- und Mathematikunterricht gelernt wurden.

Beispiel 4. Ein Algorithmus führt dazu, dass aus einer Zeichenkette eine neue Kette wie folgt entsteht:

1. Die Länge (in Zeichen) der Quellzeichenfolge wird berechnet.
2. Wenn die Länge der ursprünglichen Kette ungerade ist, wird die Zahl 1 rechts zur ursprünglichen Kette hinzugefügt, andernfalls ändert sich die Kette nicht.
3. Die Symbole werden paarweise ausgetauscht (das erste mit dem zweiten, das dritte mit dem vierten, das fünfte mit dem sechsten usw.).
4. Die Zahl 2 wird rechts von der resultierenden Kette hinzugefügt.

Die resultierende Kette ist das Ergebnis des Algorithmus.

Wenn also die Anfangskette A#B war, dann ist das Ergebnis des Algorithmus die Kette #A1B2, und wenn die Anfangskette ABC@ war, dann ist das Ergebnis des Algorithmus die Kette BA@B2.

3.1.2. Algorithmus-Ausführer

Jeder Algorithmus ist für einen bestimmten Darsteller konzipiert.

Es gibt formelle und informelle Künstler. Ein formeller Darsteller führt immer denselben Befehl auf die gleiche Weise aus. Ein informeller Vollstrecker kann einen Befehl auf unterschiedliche Weise ausführen.

Betrachten wir die Gruppe der formalen Darsteller genauer. Formale Darsteller sind äußerst vielfältig, für jeden von ihnen lassen sich jedoch folgende Merkmale spezifizieren: Umfang der zu lösenden Aufgaben (Zweck), Umgebung, Kommandosystem und Arbeitsweise.

Spektrum der zu lösenden Aufgaben. Jeder Darsteller ist dazu geschaffen, eine bestimmte Reihe von Problemen zu lösen – Symbolketten zu konstruieren, Berechnungen durchzuführen, Zeichnungen auf einer Ebene zu erstellen usw.

Künstlerumgebung. Der Bereich, die Umgebung und die Bedingungen, in denen der Darsteller tätig ist, werden üblicherweise als Umgebung des jeweiligen Darstellers bezeichnet. Die Quelldaten und Ergebnisse eines jeden Algorithmus gehören immer zur Umgebung des Ausführenden, für den der Algorithmus bestimmt ist.

Executor-Befehlssystem. Eine Anweisung an einen Ausführenden, eine separate abgeschlossene Aktion auszuführen, wird als Befehl bezeichnet. Die Menge aller Befehle, die von einem Executor ausgeführt werden können, bildet das Befehlssystem für diesen Executor (SKI). Der Algorithmus wird unter Berücksichtigung der Fähigkeiten eines bestimmten Darstellers zusammengestellt, also im Befehlssystem des Darstellers, der ihn ausführen wird.

Performer-Betriebsarten. Für die meisten Künstler stehen Direktsteuerungs- und Programmsteuerungsmodi zur Verfügung. Im ersten Fall wartet der Darsteller auf Befehle einer Person und führt jeden empfangenen Befehl sofort aus. Im zweiten Fall erhält der Ausführende zunächst eine vollständige Befehlsfolge (Programm) und führt dann alle diese Befehle automatisch aus. Einige Darsteller arbeiten nur in einem der genannten Modi.

Schauen wir uns Beispiele von Künstlern an.

Beispiel 5. Darsteller Die Schildkröte bewegt sich auf dem Computerbildschirm und hinterlässt dabei eine Spur in Form einer Linie. Das Befehlssystem der Schildkröte besteht aus zwei Befehlen:

Vorwärts n (wobei n eine ganze Zahl ist) – bewirkt, dass sich die Schildkröte n Schritte in Bewegungsrichtung bewegt – in die Richtung, in die Kopf und Körper zeigen;

Rechts m (wobei m eine ganze Zahl ist) – bewirkt, dass sich die Bewegungsrichtung der Schildkröte um m Grad im Uhrzeigersinn ändert.

Aufnahmewiederholung k [<Команда1> <Команда2> ... <Командаn>] bedeutet, dass die Befehlsfolge in Klammern k-mal wiederholt wird.

Überlegen Sie, welche Figur auf dem Bildschirm erscheinen wird, nachdem die Schildkröte den folgenden Algorithmus abgeschlossen hat.

Wiederholen Sie 12 [Rechts 4 5 Vorwärts 20 Rechts 45]

Beispiel 6. Das System der ausführenden Befehle des Computers besteht aus zwei Befehlen, denen Nummern zugewiesen sind:

1 - subtrahiere 1
2 - mit 3 multiplizieren

Der erste von ihnen verringert die Zahl um 1, der zweite erhöht die Zahl um das Dreifache. Beim Schreiben von Algorithmen werden der Kürze halber nur Befehlsnummern angegeben. Beispielsweise bedeutet Algorithmus 21212 die folgende Befehlsfolge:

mit 3 multiplizieren
subtrahiere 1
mit 3 multiplizieren
subtrahiere 1
mit 3 multiplizieren

Mit diesem Algorithmus wird die Zahl 1 in 15 umgewandelt: ((1-3-1)-3-1)-3 = 15.

Beispiel 7. Der Performer Robot arbeitet auf einem karierten Feld, zwischen benachbarten Zellen können sich Wände befinden. Der Roboter bewegt sich entlang der Zellen des Feldes und kann die folgenden Befehle ausführen, denen Nummern zugeordnet sind:

1 - Oben
2 - Unten
3 - Richtig
4 verbleibend

Bei der Ausführung jedes dieser Befehle bewegt sich der Roboter in der angegebenen Richtung zu einer benachbarten Zelle. Befindet sich in dieser Richtung zwischen den Zellen eine Wand, wird der Roboter zerstört. Was passiert mit dem Roboter, wenn er die Befehlsfolge 32323 ausführt (hier geben die Zahlen die Befehlsnummern an) und sich von Zelle A aus zu bewegen beginnt? Welche Befehlsfolge muss der Roboter ausführen, um von Zelle A zu Zelle B zu gelangen, ohne zusammenzubrechen, wenn er gegen die Wände stößt?

Bei der Entwicklung eines Algorithmus:

1. die im Problem auftretenden Objekte werden identifiziert, die Eigenschaften der Objekte, die Beziehungen zwischen den Objekten und mögliche Aktionen mit den Objekten werden festgelegt;
2. die Ausgangsdaten und das gewünschte Ergebnis werden ermittelt;
3. die Reihenfolge der Aktionen des Ausführenden wird bestimmt, um den Übergang von den Ausgangsdaten zum Ergebnis sicherzustellen;
4. Die Abfolge der Aktionen wird mithilfe von Befehlen aufgezeichnet, die im Befehlssystem des Ausführenden enthalten sind.

Wir können sagen, dass ein Algorithmus ein Modell der Aktivität des Algorithmus-Ausführers ist.

3.1.3. Algorithmuseigenschaften

Nicht jede Anweisung, Anweisungsfolge oder jeder Aktionsplan kann als Algorithmus betrachtet werden. Jeder Algorithmus hat notwendigerweise die folgenden Eigenschaften: Diskretheit, Verständlichkeit, Sicherheit, Wirksamkeit und Massencharakter.

Die Eigenschaft der Diskretion bedeutet, dass der Weg zur Lösung eines Problems in einzelne Schritte (Aktionen) unterteilt ist. Zu jeder Aktion gehört eine entsprechende Anweisung (Befehl). Erst nach der Ausführung eines Befehls kann der Ausführende mit der Ausführung des nächsten Befehls beginnen.

Die Eigenschaft der Verständlichkeit bedeutet, dass der Algorithmus nur aus Befehlen besteht, die im Befehlssystem des Ausführenden enthalten sind, d. h. aus solchen Befehlen, die der Ausführende wahrnehmen kann und nach denen er die erforderlichen Handlungen ausführen kann.

Die Eigenschaft der Gewissheit bedeutet, dass der Algorithmus keine Befehle enthält, deren Bedeutung vom Ausführenden mehrdeutig interpretiert werden kann; Inakzeptabel sind Situationen, in denen nach der Ausführung des nächsten Befehls für den Ausführenden unklar ist, welcher Befehl im nächsten Schritt ausgeführt werden soll.

Die Effizienzeigenschaft bedeutet, dass der Algorithmus in der Lage sein muss, nach einer endlichen, möglicherweise sehr großen Anzahl von Schritten ein Ergebnis zu erhalten. Als Ergebnis gilt in diesem Fall nicht nur die durch die Problemstellung ermittelte Antwort, sondern auch die Schlussfolgerung über die Unmöglichkeit, dieses Problem aus irgendeinem Grund weiter zu lösen.

Die Eigenschaft der Massenproduktion bedeutet, dass der Algorithmus die Möglichkeit seiner Anwendung bieten muss, um jedes Problem aus einer bestimmten Klasse von Problemen zu lösen. Beispielsweise sollte der Algorithmus zum Finden der Wurzeln einer quadratischen Gleichung auf jede quadratische Gleichung anwendbar sein, der Algorithmus zum Überqueren der Straße sollte überall auf der Straße anwendbar sein, der Algorithmus zur Zubereitung von Medikamenten sollte auf die Zubereitung beliebiger Mengen davon anwendbar sein. usw.

Beispiel 8. Betrachten wir eine der Methoden zum Finden aller Primzahlen, die n nicht überschreiten. Diese Methode wird „Sieb des Eratosthenes“ genannt, benannt nach dem antiken griechischen Wissenschaftler Eratosthenes, der sie vorgeschlagen hat.

Um alle Primzahlen zu finden, die nicht größer als eine bestimmte Zahl n sind, müssen Sie nach der Methode von Eratosthenes die folgenden Schritte ausführen:

1. Schreiben Sie alle ganzen Zahlen von 2 bis n hintereinander auf (2, 3, 4, ..., n);
2. Rahmen 2 – die erste Primzahl;
3. Streichen Sie alle Zahlen aus der Liste, die durch die zuletzt gefundene Primzahl teilbar sind.
4. Finden Sie die erste nicht markierte Zahl (markierte Zahlen sind durchgestrichene Zahlen oder in einem Rahmen eingeschlossene Zahlen) und schließen Sie sie in einen Rahmen ein – dies wird eine weitere Primzahl sein;
5. Wiederholen Sie die Schritte 3 und 4, bis keine unmarkierten Nummern mehr vorhanden sind.

Mit der Animation „Das Sieb des Eratosthenes“ (http://school-collection.edu.ru/) können Sie sich eine visuellere Vorstellung von der Methode zum Finden von Primzahlen machen.

Der betrachtete Aktionsablauf ist ein Algorithmus, da er folgende Eigenschaften erfüllt:

• Diskretion – der Prozess zum Finden von Primzahlen ist in Schritte unterteilt;
• Verständlichkeit – jeder Befehl ist für einen Schüler der 9. Klasse, der diesen Algorithmus ausführt, verständlich;
• Gewissheit – jeder Befehl wird vom Ausführenden eindeutig interpretiert und ausgeführt; es gibt Anweisungen zur Reihenfolge der Befehlsausführung;
• Wirksamkeit – nach einer bestimmten Anzahl von Schritten wird das Ergebnis erreicht;
• Massencharakter – die Aktionsfolge gilt für jedes natürliche n.

Die betrachteten Eigenschaften des Algorithmus ermöglichen uns eine genauere Definition des Algorithmus.

3.1.4. Möglichkeit der Automatisierung menschlicher Aktivitäten

Die Entwicklung eines Algorithmus ist in der Regel eine arbeitsintensive Aufgabe, die fundiertes Wissen, Einfallsreichtum und viel Zeit erfordert.

Um ein Problem mithilfe eines vorgefertigten Algorithmus zu lösen, muss der Ausführende lediglich die gegebenen Anweisungen strikt befolgen.

Beispiel 9. Von einem Stapel, der mehr als drei Gegenstände enthält, nehmen zwei Spieler abwechselnd jeweils einen oder zwei Gegenstände. Sieger ist, wer bei seinem nächsten Zug alle restlichen Gegenstände einsammeln kann.

Betrachten wir einen Algorithmus, nach dem der erste Spieler mit Sicherheit einen Sieg sichert.

1. Wenn die Anzahl der Gegenstände im Stapel ein Vielfaches von 3 ist, geben Sie dem Gegner den Vortritt, andernfalls beginnt das Spiel.
2. Addiere bei deinem nächsten Zug jedes Mal die Anzahl der von deinem Gegner genommenen Gegenstände zu 3 (die Anzahl der verbleibenden Gegenstände muss ein Vielfaches von 3 sein).

Der Darsteller darf sich nicht mit der Bedeutung dessen befassen, was er tut, und nicht begründen, warum er sich so und nicht anders verhält, das heißt, er kann formal handeln. Die Fähigkeit des Darstellers, formal zu handeln, bietet die Möglichkeit, menschliche Aktivitäten zu automatisieren. Dafür:

1. der Prozess der Lösung eines Problems wird als eine Abfolge einfacher Operationen dargestellt;
2. Es wird eine Maschine (automatisches Gerät) erstellt, die in der Lage ist, diese Vorgänge in der im Algorithmus angegebenen Reihenfolge auszuführen.
3. Eine Person wird von Routinetätigkeiten befreit, die Ausführung des Algorithmus wird einem automatischen Gerät anvertraut.

Das Wichtigste

Ein Ausführender ist ein Objekt (Person, Tier, technisches Gerät), das in der Lage ist, eine bestimmte Reihe von Befehlen auszuführen. Ein formeller Darsteller führt immer denselben Befehl auf die gleiche Weise aus. Für jeden formalen Darsteller können Sie angeben: den Umfang der zu lösenden Aufgaben, die Umgebung, das Befehlssystem und die Betriebsart.

Ein Algorithmus ist eine Beschreibung einer für einen bestimmten Ausführenden bestimmten Abfolge von Aktionen, die von Ausgangsdaten zum gewünschten Ergebnis führt und die Eigenschaften Diskretion, Verständlichkeit, Sicherheit, Wirksamkeit und Massencharakter aufweist.

Die Fähigkeit des Darstellers, formal zu handeln, bietet die Möglichkeit, menschliche Aktivitäten zu automatisieren.

Fragen und Aufgaben

1. Wie heißt ein Algorithmus?
2. Finden Sie Synonyme für das Wort „Rezept“.
3. Nennen Sie Beispiele für Algorithmen, die Sie in der Schule gelernt haben.
4. Wer kann der Ausführende des Algorithmus sein?
5. Geben Sie ein Beispiel für einen formellen Künstler. Geben Sie ein Beispiel, wenn eine Person als formeller Darsteller auftritt.
6. Welche Befehle sollte ein Roboter ausführen: a) eine Kassiererin in einem Geschäft; b) ein Hausmeister; c) ein Wachmann?
7. Was bestimmt das Aufgabenspektrum des „Computer“-Darstellers?
8. Betrachten Sie das Textverarbeitungsprogramm auf Ihrem Computer als Ausführenden. Beschreiben Sie das Aufgabenspektrum, das dieser Künstler und sein Umfeld lösen.
9. Was ist ein Team, ein System von Darstellerbefehlen?
10. Listen Sie die Haupteigenschaften des Algorithmus auf.
11. Wozu kann das Fehlen einer Eigenschaft in einem Algorithmus führen? Nenne Beispiele.
12. Warum ist es wichtig, einen Algorithmus formal ausführen zu können?
13. Die Zahlenfolge wird nach folgendem Algorithmus aufgebaut: Die ersten beiden Zahlen der Folge werden gleich 1 angenommen; Jede nächste Zahl in der Folge wird als gleich der Summe der beiden vorherigen Zahlen angenommen. Schreiben Sie die ersten 10 Terme dieser Sequenz auf.
14. Einige Algorithmen erhalten wie folgt eine neue Kette aus einer Zeichenfolge. Zuerst wird die ursprüngliche Zeichenkette geschrieben, danach wird die ursprüngliche Zeichenkette in umgekehrter Reihenfolge geschrieben, dann wird der Buchstabe geschrieben, der im russischen Alphabet nach dem Buchstaben folgt, der in der ursprünglichen Kette an letzter Stelle stand. Wenn die letzte Stelle in der ursprünglichen Kette der Buchstabe Z ist, wird als nächster Buchstabe der Buchstabe A geschrieben. Die resultierende Kette ist das Ergebnis des Algorithmus. Wenn die ursprüngliche Zeichenkette beispielsweise DOM war, ist das Ergebnis des Algorithmus die Kette DOMMODN. Gegeben ist die Zeichenkette COM. Wie viele Buchstaben O wird es in der Symbolkette geben, die man erhält, wenn man den Algorithmus auf diese Kette anwendet und den Algorithmus dann erneut auf das Ergebnis seiner Arbeit anwendet?
15. Finden Sie eine Animation der Schritte des Eratosthenes-Algorithmus im Internet. Verwenden Sie den Algorithmus von Eratosthenes, um alle Primzahlen zu finden, die 50 nicht überschreiten.
16. Was wird das Ergebnis der Ausführung des Algorithmus durch Turtle sein (siehe Beispiel 5)?
    Wiederholen Sie 8 [Rechts 45 Vorwärts 45]
17. Schreiben Sie einen Algorithmus für den Calculator-Executor (Beispiel 6) auf, der nicht mehr als 5 Befehle enthält:
    a) von der Nummer 3 die Nummer 16 erhalten;
    b) Erhalt der Nummer 25 von der Nummer 1.
18. Das System der Executor-Befehle Der Konstruktor besteht aus zwei Befehlen, denen Nummern zugeordnet sind:
    1 - 2 zuweisen
    2 - durch 2 dividieren

    Nach dem ersten wird 2 zur Zahl rechts addiert, nach dem zweiten wird die Zahl durch 2 geteilt. Wie wird die Zahl 8 umgewandelt, wenn der Darsteller den Algorithmus 22212 ausführt? Erstellen Sie im Befehlssystem dieses Executors einen Algorithmus, nach dem die Zahl 1 in die Zahl 16 umgewandelt wird (der Algorithmus sollte nicht mehr als 5 Befehle enthalten).

19. In welcher Zelle sollte sich der Roboter-Ausführende (Beispiel 7) befinden, um nach der Ausführung des Algorithmus 3241 dorthin zurückzukehren?

Algorithmus und seine Eigenschaften.

Algorithmus- eine klare und präzise Anweisung an den Ausführenden, die endgültige Befehlsfolge auszuführen, die von den Anfangsdaten zum gewünschten Ergebnis führt.

Algorithmus-Ausführer- Dies ist das Objekt oder Subjekt, das der Algorithmus steuern soll.

Das Befehlssystem des Darstellers (SCS) ist der gesamte Befehlssatz, den der Darsteller ausführen kann.

Eigenschaften des Algorithmus: Verständlichkeit, Genauigkeit, Endlichkeit.

Klarheit: Der Algorithmus besteht nur aus Befehlen, die im SKI des Ausführenden enthalten sind.

Genauigkeit: Jeder Befehl des Kontrollalgorithmus bestimmt die eindeutige Aktion des Darstellers.

Abschluss (oder Leistung): Die Ausführung des Algorithmus muss in endlich vielen Schritten zu einem Ergebnis führen.

Umgebung des Darstellers: die Umgebung, in der der Darsteller tätig ist.

Für einige gilt immer eine bestimmte Abfolge von Handlungen des Darstellers Quelldaten. Um beispielsweise ein Gericht nach einem kulinarischen Rezept zuzubereiten, benötigt man die entsprechenden Produkte (Daten). Um ein mathematisches Problem (Lösung einer quadratischen Gleichung) zu lösen, benötigen Sie anfängliche numerische Daten (Gleichungskoeffizienten).

Vollständiger Datensatz: ein notwendiger und ausreichender Datensatz, um die Aufgabe zu lösen (das gewünschte Ergebnis zu erzielen).

Methoden zum Schreiben von Algorithmen.

Die gängigsten Methoden sind: Grafik, verbal und in der Form Computerprogramme.

Grafische Methode beinhaltet die Verwendung bestimmter grafischer Symbole – Blöcke.

Blockname	Blockbezeichnung	Inhalt
Verfahren		Datenverarbeitung
Entscheidungsfindung		Ein logischer Block zur Überprüfung der Wahrheit oder Falschheit einer bestimmten Bedingung
Datentransfer		Eingabe oder Ausgabe von Informationen
Start stop		Beginn oder Ende des Programms
Änderung		Organisation eines zyklischen Prozesses – Zykluskopf

Die Ansammlung von Blöcken bildet die sogenannte Algorithmus-Flussdiagramm.

Mündliche Aufnahme Algorithmen konzentrieren sich in erster Linie auf den menschlichen Darsteller und ermöglichen eine unterschiedliche Aufzeichnung von Anweisungen, die Aufzeichnung muss jedoch recht genau sein.

Beim Schreiben von Algorithmen in das Formular Programme Computer verwenden Programmiersprachen – Systeme zur Kodierung von Anweisungen und Regeln für ihre Verwendung. Das Schreiben von Algorithmen in Form von Programmen zeichnet sich durch einen hohen Formalisierungsgrad aus.

Algorithmen zum Arbeiten mit Mengen. Grundlegende algorithmische Strukturen.

Eine Menge ist ein einzelnes Informationsobjekt, das einen Namen, einen Wert und einen Typ hat.

Der Ausführende von Algorithmen zur Arbeit mit Größen kann eine Person oder ein spezielles technisches Gerät, beispielsweise ein Computer, sein. Ein solcher Künstler muss vorhanden sein Erinnerung zum Lagern von Mengen.

Mengen können konstant oder variabel sein.

Konstanter Wert (konstant)ändert seinen Wert während der Ausführung des Algorithmus nicht. Eine Konstante kann durch ihren eigenen Wert (Zahlen 10, 3,5) oder durch einen symbolischen Namen (Zahl ) bezeichnet werden.

Variablenwert kann den Wert während der Ausführung des Algorithmus ändern. Eine Variable wird immer durch einen symbolischen Namen bezeichnet (X, A, R5 usw.).

Mengentyp definiert die Wertemenge, die ein Wert annehmen kann, und die Menge der Aktionen, die mit diesem Wert ausgeführt werden können. Grundtypen von Größen: ganzzahlig, reell, symbolisch, logisch.

Ausdruck- ein Datensatz, der die Reihenfolge der Aktionen für Mengen definiert. Ein Ausdruck kann Konstanten, Variablen, Operationszeichen und Funktionen enthalten. Beispiel:

A + B; 2*X-Y; K + L - sin(X)

Ein Zuweisungsbefehl ist ein Befehl eines Ausführenden, der dazu führt, dass eine Variable einen neuen Wert erhält. Befehlsformat:

Variablenname>:=Ausdruck>

Der Zuweisungsbefehl wird in der folgenden Reihenfolge ausgeführt: Zuerst wird er berechnet, dann wird der resultierende Wert einer Variablen zugewiesen.

Beispiel. Lassen Sie Variable A den Wert 6 haben. Welchen Wert erhält Variable A nach der Ausführung des Befehls: A:= 2 * A - 1?
Lösung. Die Berechnung des Ausdrucks 2*A - 1 mit A=6 ergibt die Zahl 11. Das bedeutet, dass der neue Wert der Variablen A gleich 11 sein wird.

Im Folgenden wird davon ausgegangen Der Ausführende von Algorithmen zur Arbeit mit Mengen ist ein Computer. Jeder Algorithmus kann aus Befehlen erstellt werden Zuordnungen, Eingang, Ausgabe, Verzweigung Und Zyklus.

Eingabebefehl- ein Befehl, mit dem Variablenwerte über Eingabegeräte (z. B. eine Tastatur) eingestellt werden.

Beispiel: Eingang A – Eingabe des Werts der Variablen A über die Computertastatur.

Ausgabebefehl: Ein Befehl, der den Wert einer Größe auf einem Computerausgabegerät (z. B. einem Monitor) anzeigt.

Beispiel: Abschluss X – der Wert der X-Variablen wird auf dem Bildschirm angezeigt.

Zweigbefehl- teilt den Algorithmus abhängig von einer Bedingung in zwei Pfade auf; dann geht die Ausführung des Algorithmus zur allgemeinen Fortsetzung über. Die Verzweigung kann vollständig oder unvollständig sein. Beschreibung der Verzweigung in Blockdiagrammen und in algorithmischer Sprache:

Hier bedeutet eine Serie einen oder mehrere aufeinanderfolgende Befehle; kv – Ende der Verzweigung.

Schleifenbefehl stellt die wiederholte Ausführung einer Befehlsfolge (Schleifenkörper) basierend auf einer bestimmten Bedingung sicher.

Schleife mit Vorbedingung- eine Schleife, deren Ausführung wiederholt wird, bis die Schleifenbedingung wahr ist:

Schleife mit Parameter- wiederholte Ausführung des Schleifenkörpers, während der ganzzahlige Parameter die Menge aller Werte vom Anfang (In) bis zum Ende (Ik) durchläuft:

Beispiel. Gegeben sind zwei einfache Brüche. Erstellen Sie einen Algorithmus, um einen Bruch zu erhalten, der das Ergebnis ihrer Division ist.
Lösung. In algebraischer Form sieht die Lösung des Problems so aus:
a/b: c/d = a*d/b*c = m/n
Die Ausgangsdaten sind vier ganzzahlige Größen: a, b, c, d. Das Ergebnis sind zwei ganze Zahlen m und n.

alg Brüche dividieren
intakt a, b, c, d, m, n
Eingabe starten A B C D
m:=a*d
n:=b*c
Ausgabe „Zähler=", m
Ausgabe „Denominator=", n
Koi

Bitte beachten Sie, dass zur Ausgabe von Text (beliebige Zeichenfolge) dieser im Befehl in Anführungszeichen geschrieben werden muss Abschluss.

1. Efimova O., Morozov V., Ugrinovich N. Kurs in Computertechnologie mit den Grundlagen der Informatik. Lehrbuch für das Gymnasium. - M.: LLC „AST Publishing House“; ABF, 2000
2. Problembuch-Workshop in der Informatik. In 2 Bänden/Hrsg. I. Semakina, E. Henner. - M.: Labor für Grundwissen, 2001.
3. Ugrinovich N. Informatik und Informationstechnologien. 10-11 Klassen - M.: Labor für Grundwissen, JSC "Moscow Textbooks", 2001

Aufgaben und Tests zum Thema „Algorithmen und Executoren“

• Zeichner des Künstlermanagements - Algorithmen 6. Klasse

  Lektionen: 4 Aufgaben: 9 Tests: 1

• 2 Aufgaben: 9 Tests: 1

Lieber Student!

Kenntnisse zum Thema „Algorithmen und Executoren“ sind vor allem für das weitere Studium der Programmierung notwendig. Als Grundlage für das Programmierstudium wurde die Programmiersprache QBasic gewählt. Wir haben die Idee, Visual Basic oder eine andere objektorientierte Programmiersprache in unseren Kurs einzubeziehen, aufgegeben, da dieser Ansatz in den meisten weiterführenden Schulen der Russischen Föderation noch nicht weit verbreitet ist. Darüber hinaus basiert die objektorientierte Programmierung auf den Prinzipien der klassischen Dos-Programmierung.

Unser Kurs ist für den allgemeinbildenden Studiengang konzipiert. Bei der Vorbereitung auf Aufnahmeprüfungen im Fach Informatik an Universitäten müssen Sie sich mit den Besonderheiten des Programmierstudiums an einer bestimmten Universität vertraut machen. In manchen Fällen ist eine vertiefte Auseinandersetzung mit einer Reihe von Themen erforderlich, beispielsweise „Arrays“. Darauf sollten Sie beim Studium der Programmierliteratur achten und ggf. die methodischen Empfehlungen zur Prüfungsvorbereitung nutzen, die derzeit an den meisten Hochschulen veröffentlicht werden.

Zusammenfassend stellen wir fest, dass das Erreichen von „Kunstflug“ im Programmieren nur durch ständiges Üben und Lösen spezifischer Anwendungsprobleme möglich ist.

Theoretische Informationen

Algorithmus ist eine Beschreibung einer Abfolge von Aktionen (Plan), deren strikte Ausführung in einer endlichen Anzahl von Schritten zur Lösung eines gegebenen Problems führt.

Eigenschaften von Algorithmen:

1. Diskretion (der Algorithmus muss aus bestimmten Aktionen bestehen, die in einer bestimmten Reihenfolge folgen);

2. Determinismus (jede Aktion muss in jedem Fall streng und eindeutig definiert sein);

3. Endlichkeit (jede Aktion und der Algorithmus als Ganzes müssen abgeschlossen werden können);

4. Massivität (derselbe Algorithmus kann mit unterschiedlichen Quelldaten verwendet werden);

5. Effizienz (keine Fehler, der Algorithmus sollte für alle gültigen Eingabewerte zum richtigen Ergebnis führen).

Arten von Algorithmen:

1. Linearer Algorithmus (Beschreibung von Aktionen, die einmal in einer bestimmten Reihenfolge ausgeführt werden);

2. Zyklischer Algorithmus (Beschreibung von Aktionen, die eine bestimmte Anzahl von Malen wiederholt werden müssen oder bis die Aufgabe abgeschlossen ist);

3. Verzweigungsalgorithmus (ein Algorithmus, bei dem je nach Bedingung entweder die eine oder andere Abfolge von Aktionen ausgeführt wird)

Beispiele für Problemlösungen

Darsteller Der Zeichner bewegt sich auf der Koordinatenebene und hinterlässt dabei eine Spur in Form einer Linie. Der Zeichner kann den Befehl ausführen Gehe zu (a, b)(wobei a,b ganze Zahlen sind) und den Zeichner von einem Punkt mit den Koordinaten (x, y) zu einem Punkt mit den Koordinaten (x + a, y + b) bewegt. Sind die Zahlen a, b positiv, erhöht sich der Wert der entsprechenden Koordinate; wenn es negativ ist, nimmt es ab.

Befindet sich der Zeichner beispielsweise an einem Punkt mit den Koordinaten (9, 5), dann ist der Befehl Wechseln zu

(1, -2) verschiebt den Zeichner zu Punkt (10, 3).

Wiederholen Sie k-mal

Team1 Team2 Team3

Ende

bedeutet, dass die Reihenfolge der Befehle Team1 Team2 Team3 wird k-mal wiederholt. Dem Verfasser wurde der folgende Algorithmus zur Ausführung vorgelegt:

3 Mal wiederholen

Verschiebung um (-2, -3) Verschiebung um (3, 2) Verschiebung um (-4, 0)

Ende

Durch welchen Befehl kann dieser Algorithmus ersetzt werden, sodass der Zeichner am selben Punkt landet, an dem er nach der Ausführung des Algorithmus steht?

1) Gehe zu (-9, -3)

2) Gehen Sie zu (-3, 9)

3) Gehe zu (-3, -1)

4) Gehe zu (9, 3)

Lösung:

Diese Aufgabe lässt sich am besten sequentiell lösen.

In einer Schleife führt der Drafter eine Folge von Befehlen aus

– Bewegen um (-2, -3)

– Gehe zu (3, 2)

– Gehe zu (-4, 0),

was durch einen Befehl ersetzt werden kann: Bewegen um (-2+3-4, -3+2+0), d.h. Gehen Sie zu (-3, -1).

Da die Schleife dreimal wiederholt wird, wird der resultierende Befehl Shift by (-3, -1) dreimal ausgeführt. Das bedeutet, dass der Zyklus durch den Befehl Shift by (-3*3, -1*3) ersetzt werden kann, d.h. Gehen Sie zu (-9, -3). Somit erhalten wir den Befehl Move to (-9, -3), mit dem der gesamte Algorithmus ersetzt werden kann.

Aufgaben zum Training

1. Darsteller Der Zeichner bewegt sich auf der Koordinatenebene und hinterlässt dabei eine Spur in Form einer Linie. Der Zeichner kann den Befehl ausführen Gehe zu (a, b)(wobei a, b ganze Zahlen sind) und den Zeichner von einem Punkt mit den Koordinaten (x, y) zu einem Punkt mit den Koordinaten (x + a, y + b) bewegt. Sind die Zahlen a, b positiv, erhöht sich der Wert der entsprechenden Koordinate; wenn negativ, nimmt ab.

Wenn sich der Zeichner beispielsweise an einem Punkt mit den Koordinaten (4, 2) befindet, verschiebt der Befehl „Zu (2, −3) verschieben“ den Zeichner zum Punkt (6, −1).

Wiederholen Sie k-mal

Team1 Team2 Team3

Ende

bedeutet, dass die Reihenfolge der Befehle Team1 Team2 Team3 wird wieder passieren k einmal.

Dem Verfasser wurde der folgende Algorithmus zur Ausführung vorgelegt:

2 Mal wiederholen

Bewegen Sie sich um (−6, −4)

Nach Abschluss dieses Algorithmus kehrte der Zeichner zum Ausgangspunkt zurück. Welcher Befehl sollte anstelle des Befehls eingegeben werden? Team1?

1) Verschiebung um (−2, −1)

2) Gehe zu (1, 1)

3) Verschiebung um (−4, −2)

4) Gehe zu (2, 1)

2. Gehe zu (a, b)

Wenn sich der Zeichner beispielsweise an den Koordinaten (4, 2) befindet, verschiebt der Befehl „Zu (2, −3) verschieben“ den Zeichner zum Punkt (6, −1).

Wiederholen Sie k-mal

Team1 Team2 Team3

Ende

Team1 Team2 Team3 wird wieder passieren k einmal.

4 Mal wiederholen

Befehl1 Gehe zu (3, 3) Gehe zu (1,−2) Ende

Verschiebung um (−8, 12)

Team1?

1) Verschiebung um (−2, −4)

2) Verschiebung um (4,−13)

3) Gehen Sie zu (2, 4)

4) Verschiebung um (−8, −16)

3. Darsteller Der Zeichner bewegt sich auf der Koordinatenebene und hinterlässt dabei eine Spur in Form einer Linie. Der Zeichner kann den Befehl ausführen Gehe zu (a, b)(wobei a, b ganze Zahlen sind) und den Zeichner von einem Punkt mit den Koordinaten (x, y) zu einem Punkt mit den Koordinaten (x + a, y + b) bewegt. Sind die Zahlen a, b positiv, erhöht sich der Wert der entsprechenden Koordinate; wenn negativ, nimmt ab.

Wiederholen Sie k-mal

Team1 Team2 Team3

Ende

bedeutet, dass die Reihenfolge der Befehle Team1 Team2 Team3 wird wieder passieren k einmal.

Dem Verfasser wurde der folgende Algorithmus zur Ausführung vorgelegt:

3 Mal wiederholen

Gehe zu (3, 9)

Nach Abschluss dieses Algorithmus kehrte der Zeichner zum Ausgangspunkt zurück. Welcher Befehl sollte anstelle des Befehls eingegeben werden? Team1?

1) Wechsel zu (3, 4)

2) Verschiebung um (−5, −10)

3) Verschiebung um (−9, −12)

4) Verschiebung um (−3, −4)

4. Darsteller Der Zeichner bewegt sich auf der Koordinatenebene und hinterlässt dabei eine Spur in Form einer Linie. Der Zeichner kann den Befehl ausführen Gehe zu (a, b)(wobei a, b ganze Zahlen sind) und den Zeichner von einem Punkt mit den Koordinaten (x, y) zu einem Punkt mit den Koordinaten (x + a, y + b) bewegt. Sind die Zahlen a, b positiv, erhöht sich der Wert der entsprechenden Koordinate; wenn negativ, nimmt ab.

Wenn sich der Zeichner beispielsweise an einem Punkt mit den Koordinaten (4, 2) befindet, verschiebt der Befehl „Zu (2, −3) verschieben“ den Zeichner zum Punkt (6, −1).

Wiederholen Sie k-mal

Team1 Team2 Team3

Ende

bedeutet, dass die Reihenfolge der Befehle Team1 Team2 Team3 wird wieder passieren k einmal.

Dem Verfasser wurde der folgende Algorithmus zur Ausführung vorgelegt:

3 Mal wiederholen

Befehl1 Gehe zu (3, 2) Gehe zu (2, 1) Ende

Gehe zu (−9, −6)

Nach Abschluss dieses Algorithmus kehrte der Zeichner zum Ausgangspunkt zurück. Welcher Befehl sollte anstelle des Befehls eingegeben werden? Team1?

1) Verschiebung um (−6, −3)

2) Gehe zu (4, 3)

3) Verschiebung um (−2, −1)

4) Gehe zu (2, 1)

5. Darsteller Der Zeichner bewegt sich auf der Koordinatenebene und hinterlässt dabei eine Spur in Form einer Linie. Der Zeichner kann den Befehl ausführen Gehe zu (a, b)(wobei a, b ganze Zahlen sind) und den Zeichner von einem Punkt mit den Koordinaten (x, y) zu einem Punkt mit den Koordinaten (x + a, y + b) bewegt. Sind die Zahlen a, b positiv, erhöht sich der Wert der entsprechenden Koordinate; wenn negativ, nimmt ab.

Wiederholen Sie k-mal

Team1 Team2 Team3

Ende

bedeutet, dass die Reihenfolge der Befehle Team1 Team2 Team3 wird wieder passieren k einmal.

Dem Verfasser wurde der folgende Algorithmus zur Ausführung vorgelegt:

2 Mal wiederholen

Befehl1 Gehe zu (3, 3) Gehe zu (1, −2) Ende

Verschiebung um (4, −6)

Nach Abschluss dieses Algorithmus kehrte der Zeichner zum Ausgangspunkt zurück. Welcher Befehl sollte anstelle des Befehls eingegeben werden? Team1?

1) Verschiebung um (6, −2)

2) Verschiebung um (−8, 5)

3) Verschiebung um (−12, 4)

4) Verschiebung um (−6, 2)

6. Darsteller Der Zeichner bewegt sich auf der Koordinatenebene und hinterlässt dabei eine Spur in Form einer Linie. Der Zeichner kann den Befehl ausführen Gehe zu (a, b)(wobei a, b ganze Zahlen sind) und den Zeichner von einem Punkt mit den Koordinaten (x, y) zu einem Punkt mit den Koordinaten (x + a, y + b) bewegt. Sind die Zahlen a, b positiv, erhöht sich der Wert der entsprechenden Koordinate; wenn negativ, nimmt ab.

Wenn sich der Zeichner beispielsweise an einem Punkt mit den Koordinaten (4, 2) befindet, verschiebt der Befehl „Zu (2, −3) verschieben“ den Zeichner zum Punkt (6, −1).

Wiederholen Sie k-mal

Team1 Team2 Team3

Ende

bedeutet, dass die Reihenfolge der Befehle Team1 Team2 Team3 wird wieder passieren k einmal.

Dem Verfasser wurde der folgende Algorithmus zur Ausführung vorgelegt:

4 Mal wiederholen

Befehl1 Gehe zu (1, 3) Gehe zu (1, −2) Ende

Verschiebung um (−4, −12)

Nach Abschluss dieses Algorithmus kehrte der Zeichner zum Ausgangspunkt zurück. Welcher Befehl sollte anstelle des Befehls eingegeben werden? Team1?

1) Verschiebung um (1,−2)

2) Wechsel zu (12, 4)

3) Gehen Sie zu (2, 11)

4) Verschiebung um (−1, 2)

7. Darsteller Der Zeichner bewegt sich auf der Koordinatenebene und hinterlässt dabei eine Spur in Form einer Linie. Der Zeichner kann den Befehl ausführen Gehe zu (a, b)(wobei a, b ganze Zahlen sind) und den Zeichner von einem Punkt mit den Koordinaten (x, y) zu einem Punkt mit den Koordinaten (x + a, y + b) bewegt. Sind die Zahlen a, b positiv, erhöht sich der Wert der entsprechenden Koordinate; wenn negativ, nimmt ab.

Wenn sich der Zeichner beispielsweise an einem Punkt mit den Koordinaten (4, 2) befindet, verschiebt der Befehl „Zu (2, −3) verschieben“ den Zeichner zum Punkt (6, −1).

Wiederholen Sie k-mal

Team1 Team2 Team3

Ende

bedeutet, dass die Reihenfolge der Befehle Team1 Team2 Team3 wird wieder passieren k einmal.

Dem Verfasser wurde der folgende Algorithmus zur Ausführung vorgelegt:

4 Mal wiederholen

Befehl1 Gehe zu (3, 2) Gehe zu (2, 1) Ende

Gehe zu (−12, −8)

Nach Abschluss dieses Algorithmus kehrte der Zeichner zum Ausgangspunkt zurück. Welcher Befehl sollte anstelle des Befehls eingegeben werden? Team1?

1) Verschiebung um (−8, −4)

2) Verschiebung um (−2, −1)

3) Gehen Sie zu (7, 5)

4) Gehe zu (2, 1)

8. Vorwärts n Richtig m

Wiederholen Sie 9 [Vorwärts 50 Rechts 60]

1) regelmäßiges Sechseck

2) regelmäßiges Dreieck

3) offene gestrichelte Linie

4) regelmäßiges Sechseck

9. Darsteller Die Schildkröte bewegt sich auf dem Computerbildschirm und hinterlässt dabei eine Spur in Form einer Linie. Zu jedem bestimmten Zeitpunkt sind die Position des Darstellers und die Richtung seiner Bewegung bekannt. Der Darsteller hat zwei Befehle: Vorwärts n(wobei n eine ganze Zahl ist), wodurch sich die Schildkröte n Schritte in Bewegungsrichtung bewegt; Richtig m(wobei m eine ganze Zahl ist), was zu einer Änderung der Bewegungsrichtung um m Grad im Uhrzeigersinn führt. Aufzeichnen Wiederholen Sie k [Befehl1 Befehl2 Befehl3] bedeutet, dass die Befehlsfolge in Klammern k-mal wiederholt wird.

Der Schildkröte wurde der folgende Algorithmus zur Ausführung gegeben: Wiederholen Sie 7 [Vorwärts 70 Rechts 120]. Welche Form erscheint auf dem Bildschirm?

1) regelmäßiges Sechseck

2) offene gestrichelte Linie

3) regelmäßiges Siebeneck

4) regelmäßiges Dreieck

10. Darsteller Die Schildkröte bewegt sich auf dem Computerbildschirm und hinterlässt dabei eine Spur in Form einer Linie. Zu jedem bestimmten Zeitpunkt sind die Position des Darstellers und die Richtung seiner Bewegung bekannt. Der Darsteller hat zwei Befehle: Vorwärts n(wobei n eine ganze Zahl ist), wodurch sich die Schildkröte n Schritte in Bewegungsrichtung bewegt; Richtig m(wobei m eine ganze Zahl ist), was zu einer Änderung der Bewegungsrichtung um m Grad im Uhrzeigersinn führt. Aufzeichnen Wiederholen Sie k [Befehl1 Befehl2 Befehl3] bedeutet, dass die Befehlsfolge in Klammern k-mal wiederholt wird.

Der Schildkröte wurde der folgende Algorithmus zur Ausführung gegeben: Wiederholen Sie 9 [Vorwärts 70 Rechts 90]. Welche Form erscheint auf dem Bildschirm?

2) regelmäßiges Sechseck

3) regelmäßiges Achteck

4) regelmäßiges Viereck

11. Darsteller Die Schildkröte bewegt sich auf dem Computerbildschirm und hinterlässt dabei eine Spur in Form einer Linie. Zu jedem bestimmten Zeitpunkt sind die Position des Darstellers und die Richtung seiner Bewegung bekannt. Der Darsteller hat zwei Befehle: Vorwärts n(wobei n eine ganze Zahl ist), wodurch sich die Schildkröte n Schritte in Bewegungsrichtung bewegt; Richtig m(wobei m eine ganze Zahl ist), was zu einer Änderung der Bewegungsrichtung um m Grad im Uhrzeigersinn führt. Aufzeichnen Wiederholen Sie k [Befehl1 Befehl2 Befehl3] bedeutet, dass die Befehlsfolge in Klammern k-mal wiederholt wird.

Der Schildkröte wurde der folgende Algorithmus zur Ausführung gegeben: Wiederholen Sie 5 [Vorwärts 80 Rechts 60]. Welche Form erscheint auf dem Bildschirm?

1) regelmäßiges Fünfeck

2) regelmäßiges Dreieck

3) regelmäßiges Sechseck

4) offene gestrichelte Linie

12. Darsteller Die Schildkröte bewegt sich auf dem Computerbildschirm und hinterlässt dabei eine Spur in Form einer Linie. Zu jedem bestimmten Zeitpunkt sind die Position des Darstellers und die Richtung seiner Bewegung bekannt. Der Darsteller hat zwei Befehle: Vorwärts n(wobei n eine ganze Zahl ist), wodurch sich die Schildkröte n Schritte in Bewegungsrichtung bewegt; Richtig m(wobei m eine ganze Zahl ist), was zu einer Änderung der Bewegungsrichtung um m Grad im Uhrzeigersinn führt. Aufzeichnen Wiederholen Sie k [Befehl1 Befehl2 Befehl3] bedeutet, dass die Befehlsfolge in Klammern k-mal wiederholt wird.

Der Schildkröte wurde der folgende Algorithmus zur Ausführung gegeben: Wiederholen Sie 5 [Vorwärts 80 Rechts 90]. Welche Form erscheint auf dem Bildschirm?

1) offene gestrichelte Linie

2) regelmäßiges Sechseck

3) regelmäßiges Fünfeck

4) regelmäßiges Viereck

Theoretische Informationen

Beispiele für Problemlösungen

Aufgaben zum Training

Theoretische Informationen

Beispiele für Problemlösungen

Aufgaben zum Training

Theoretische Informationen

Beispiele für Problemlösungen

Aufgaben zum Training

Theoretische Informationen

Beispiele für Problemlösungen

Aufgaben zum Training

Theoretische Informationen

Beispiele für Problemlösungen

Aufgaben zum Training

Theoretische Informationen

Beispiele für Problemlösungen

Aufgaben zum Training

Theoretische Informationen

Beispiele für Problemlösungen

Aufgaben zum Training

Theoretische Informationen

Beispiele für Problemlösungen

Aufgaben zum Training

Theoretische Informationen

Beispiele für Problemlösungen

Aufgaben zum Training

Das Wort „Algorithmus“ leitet sich vom Namen des arabischen Mathematikers al-Khwarizmi aus dem 9. Jahrhundert ab, der die Regeln für die Durchführung arithmetischer Operationen formulierte.

Algorithmus– eine genaue und verständliche Anweisung an den Ausführenden, die endgültige Befehlsfolge auszuführen, die von den Anfangsdaten zum Anfangsergebnis führt.

Beispiele: Tagesablauf, Reihenfolge des Kochens, Anweisungen usw.)

Algorithmus-Ausführer– das ist derjenige, der den Algorithmus ausführt (Mensch, Tier, Maschine, Computer).

Executor-Befehlssystem- Dies ist der gesamte Befehlssatz, den der Ausführende ausführen kann (versteht). Der Algorithmus kann nur aus Befehlen erstellt werden, die im System der Executor-Befehle enthalten sind.

Zum Beispiel, Darsteller Der Roboter kann Befehle vorwärts, rückwärts, links, rechts und malen ausführen. Es bewegt sich über ein Zellfeld, das von einer Wand begrenzt wird und Wände enthält. Der Roboter kann nicht durch die Wand gehen.

Eigenschaften des Algorithmus:

1.Leistung (Gliedmaßen)– die Fähigkeit, aus den Ausgangsdaten in einer endlichen Anzahl von Schritten ein Ergebnis zu erhalten. (Wenn Sie beispielsweise den Algorithmus zum Addieren von zwei Zahlen ausführen, sollte die Summe erhalten werden).

2.Massencharakter– die Fähigkeit, den Algorithmus auf eine große Anzahl unterschiedlicher Quelldaten anzuwenden. (Sie können beispielsweise zwei beliebige Zahlen addieren, wenn Sie den Additionsalgorithmus kennen.)

3.Determinismus(Gewissheit, Genauigkeit) – jeder Befehl muss die Aktion des Ausführenden eindeutig bestimmen.

4.Verständlichkeit– Der Befehl muss in einer für den Computer verständlichen Sprache verfasst sein.

5.Diskretion– Aufteilung des Algorithmus in separate Befehle.

Möglichkeiten, den Algorithmus zu schreiben:

1) In natürlicher Sprache – Aufzeichnung in Form einzelner Befehle in einer für Menschen verständlichen Sprache.

2) Grafik – in der Sprache der Flussdiagramme, unter Verwendung geometrischer Formen (Oval, Rechteck, Parallelogramm, Raute).

3) In einer algorithmischen Sprache – einer Sprache zum Schreiben von Algorithmen für den Programmierunterricht. Befehle sind auf Russisch verfasst.

4) In einer Programmiersprache – ein Programm. Programmiersprachen: Basic, Pascal, C, Visual Basic.

B7.Grundlegende algorithmische Strukturen: Folgen, Verzweigen, Schleife; Bild auf Blockdiagrammen. Aufgaben in Unteraufgaben aufteilen. Hilfsalgorithmen.

Algorithmische Designs. Innerhalb von Algorithmen lassen sich Gruppen von Schritten unterscheiden, die sich in der inneren Struktur unterscheiden – algorithmische Konstruktionen.

Grundlegende algorithmische Konstruktionen sind lineare Abfolgen von Schritten (oder Folgeschritten), Verzweigungen und Schleifen.

Ein Algorithmus, bei dem Befehle sequentiell nacheinander ausgeführt werden, wird aufgerufen linearer Algorithmus.

So sieht ein linearer Algorithmus in Blockdiagrammsprache aus:

Beispiel: Algorithmus zum Einschalten des Computers:

1. Schalten Sie den Computer ein (drücken Sie die Taste am Überspannungsschutz).
2. Schalten Sie Monitor und Drucker ein.
3. Drücken Sie die Power-Taste an der Systemeinheit.
4. Warten Sie, bis das Betriebssystem geladen ist und der Desktop angezeigt wird.
5. Machen Sie sich an die Arbeit.

Bei diesem Algorithmus müssen alle Aktionen nacheinander ausgeführt werden: Sie können nicht mit der Arbeit beginnen, wenn der Strom oder der Monitor nicht eingeschaltet ist.

In die algorithmische Struktur“ Verzweigung" inbegriffen Zustand Je nachdem, ob die Bedingung wahr ist, wird die eine oder andere Befehlsfolge (Serie) ausgeführt.

Eine Bedingung ist eine Aussage, die wahr oder falsch sein kann. In der Bedingung werden zwei Zahlen, zwei Strings, zwei Variablen oder String-Ausdrücke mithilfe von Vergleichsoperatoren (>,<, =, >=, <=).

Aufzeichnung in algorithmischer Sprache: IfCondition Then Series 1 (If Zustand wahr, dann wahr Episode 1, Wenn Zustand false, dann wird nichts ausgeführt). Beispiel: Wenn heute Sonntag ist, besteht keine Notwendigkeit, zur Schule zu gehen. Vollständige Form der Verzweigung

In algorithmischen Strukturen Zyklus enthält eine Reihe von Befehlen, die wiederholt ausgeführt werden. Diese Befehlsfolge wird aufgerufen Körper der Schleife.

Es gibt zwei Arten zyklischer algorithmischer Strukturen:

• Gegenschleifen, in dem der Schleifenkörper eine bestimmte Anzahl von Malen ausgeführt wird;
• Bedingte Schleifen, bei dem der Schleifenkörper solange ausgeführt wird, wie die Bedingung erfüllt ist.

Schleife mit Zähler– wird verwendet, wenn im Voraus bekannt ist, wie viele Wiederholungen des Schleifenkörpers durchgeführt werden müssen.