Ein Algorithmus, der von einem Computer ausgeführt wird, heißt. Ausführung eines Algorithmus mit einem festen Satz von Anweisungen. Fragen zur Selbstkontrolle
MBOU „Glinnovskaya-Sekundarschule“
Bezirk Novooskolsky
Region Belgorod
Plan – Zusammenfassung der Lektion
(9.Klasse)
„Algorithmen, Konzepte von Algorithmen, Eigenschaften von Algorithmen. Ausführer des Algorithmus“
Hergestellt von:
Informatik lernen
Tarasova N.G.
2011
Thema: Das Konzept der Algorithmen, Eigenschaften des Algorithmus. Ausführer von Algorithmen, System von Ausführerbefehlen. Methoden zur Aufzeichnung von Algorithmen. Formale Ausführung von Algorithmen.
Unterrichtsart: Einarbeitung in neues Material.
Ziele:
- Fördern Sie die Entwicklung des algorithmischen Denkens;
- Geben Sie das Konzept eines Algorithmus an, sprechen Sie über seine Eigenschaften, geben Sie eine Klassifizierung von Algorithmen an;
- Stellen Sie die Form der Aufzeichnungsalgorithmen vor – Flussdiagramm.
Ausrüstung : Projektor, Präsentation.
Während des Unterrichts
1 Org. Moment
Begrüßung, Einsteigen, Appell.
2 Aktualisierung des Supportmaterials
Leute, sagt mir bitte, wie versteht ihr das Wort Algorithmus? Wo begegnet uns dieses Konzept?
3 Präsentation des Materials
Der Begriff „Algorithmus“ hat seinen Ursprung in der Mathematik. Die Entstehungsgeschichte ist wie folgt. Im 9. Jahrhundert lebte der Wissenschaftler al(al)-Khorezmi (vollständiger Name: Muhammad ben Musa al-Khorezmi, d. h. Muhammad, der Sohn von Musa aus Khorezm), Mathematiker, Astronom und Geograph in Bagdad. In einem seiner Werke beschrieb er das dezimale Zahlensystem und formulierte erstmals die Regeln für die Durchführung arithmetischer Operationen mit ganzen Zahlen und gewöhnlichen Brüchen. Das arabische Original dieses Buches ging verloren, die lateinische Übersetzung aus dem 12. Jahrhundert blieb jedoch erhalten, nach der Westeuropa mit dem dezimalen Zahlensystem und den Regeln zur Durchführung arithmetischer Operationen vertraut wurde.
Al-Khwarizmi versuchte sicherzustellen, dass die von ihm formulierten Regeln verständlich waren. Dies war im 9. Jahrhundert schwierig zu erreichen, als mathematische Symbole (Operationszeichen, Klammern, Buchstabensymbole usw.) noch nicht entwickelt waren. Es gelingt ihm jedoch, einen klaren Stil strenger mündlicher Anweisungen zu entwickeln, der dem Leser keine Möglichkeit gibt, sich den Vorgaben zu entziehen oder irgendwelche Handlungen zu überspringen.
Die Regeln in den Büchern von cm-Khorezmi in der lateinischen Übersetzung begannen mit den Worten „Algorizmi sagte.“ In anderen lateinischen Übersetzungen wurde der Autor als Algorithmus bezeichnet. Im Laufe der Zeit geriet man in Vergessenheit, dass Algorizmi (Algorithmus) der Autor der Regeln ist, und diese Regeln wurden Algorithmen genannt. Viele Jahrhunderte lang wurden Algorithmen entwickelt, um immer neue Problemklassen zu lösen, aber das Konzept eines Algorithmus selbst hatte keine genaue mathematische Definition.
Derzeit ist das Konzept eines Algorithmus geklärt und wurde im 20. Jahrhundert im Rahmen einer Wissenschaft namens Algorithmentheorie entwickelt.
Algorithmus - präzise und verständliche Anweisungen an den Ausführenden, eine Abfolge von Aktionen zur Lösung der Aufgabe durchzuführen.
Algorithmus - klar organisierte sequentielle Aktion, die zu einem bestimmten Ergebnis führt.
Der Ausführer des Algorithmus ist etwas Abstraktes oder Realesein System, das in der Lage ist, eine durch einen Algorithmus (technisch, biologisch oder biotechnisch) vorgeschriebene Aktion auszuführen.
Technischer Leiter– Geldautomat;
Biologisch - eine Person, ein lebender Organismus;
Biotechnologie - künstliche Intelligenz.
Eigenschaften von Algorithmen
Diskretion (Getrenntheit, Diskontinuität) – der Algorithmus muss als Folge von Schritten oder Stufen geschrieben werden.
Verständlichkeit Der Ausführende des Algorithmus muss wissen, wie dieser Algorithmus ausgeführt wird.
Sicherheit (Determinismus) Jede Regel des Algorithmus muss klar und eindeutig sein und darf keinen Raum für Willkür lassen.
Aufgrund dieser Eigenschaft ist die Ausführung des Algorithmus mechanischer Natur und erfordert keine zusätzlichen Anweisungen.
Effizienz(Endlichkeit) Der Algorithmus muss in endlich vielen Schritten zu einer Lösung des Problems führen.
Massencharakter Der Algorithmus wird in allgemeiner Form entwickelt, sodass er zur Lösung ähnlicher Probleme angewendet werden kann. In diesem Fall werden die Ausgangsdaten aus bestimmten Bereichen ausgewählt, die als Anwendungsbereich der Algorithmen bezeichnet werden.
Möglichkeiten, Algorithmen zu schreiben
Wenn die Eigenschaften Gewissheit und Diskretion mit einem gewissen Grad an Genauigkeit erhalten bleiben, d. h. Das Programm kann Schritte neu anordnen oder es enthält wünschenswerte, aber nicht obligatorische Schritte, dann ist dies kein Algorithmus, sondernalgorithmisches Rezept.
Jeder Algorithmus ist für einen bestimmten Zweck konzipiert Künstler. Es kann eine Person, ein Roboter, ein Computer usw. sein. Jeder Darsteller hat sein eigenes Befehlssystem. Beim Verfassen eines Algorithmus müssen Sie berücksichtigen, für welchen Ausführenden er konzipiert ist. Der Darsteller kann den Algorithmus ausführen, ohne sich mit der Bedeutung dessen, was er tut, auseinanderzusetzen, und warum er es tut, und trotzdem das gewünschte Ergebnis erzielen. In solchen Fällen spricht man von einer formalen Ausführung des Algorithmus.
Algorithmus-Aufzeichnungsformulare:
Verbal ist eine Beschreibung der aufeinanderfolgenden Phasen der Datenverarbeitung. Der Algorithmus ist eine beliebige Darstellung in natürlicher Sprache
Grafik - eine Folge miteinander verbundener Blöcke, von denen jeder der Ausführung einer oder mehrerer Aktionen entspricht.
Eine solche grafische Darstellung wird als Blockdiagramm bezeichnet – ein orientierter Graph, der die Reihenfolge der Ausführung der Befehle des Algorithmus angibt.
Grafische Formen von Aufzeichnungsalgorithmen:
Grundlegende algorithmische Strukturen
Folgende (lineare Algorithmus-)Schleifen
Verzweigung
Nachfolgend – Befehle werden nacheinander in der Reihenfolge ausgeführt, in der sie im Algorithmus geschrieben sind.((Beispiel. Algorithmus zum Öffnen der Wohnungstür: Schlüssel herausnehmen, hineinsteckenSchlüsselloch öffnen, so oft drehen, Schlüssel herausziehen, Tür öffnen. schließen Sie die Tür)
Verzweigung - Daten beeinflussen den Fortschritt des Algorithmus, d. h. je nach Zustandbestimmte Aktionen des Algorithmus werden ausgeführt.(Beispiel: Algorithmus zum „Einkommen“ in Ihre Wohnung: Rufen Sie in der Wohnung an; wenn jemand zu Hause ist, warten Sie, bis die Tür geöffnet wird undBetreten Sie die Wohnung, wenn niemand zu Hause ist, und holen Sie sich den Schlüssel. ...)
Zyklus (Wiederholung)- während der Ausführung des Algorithmus eine bestimmteSatz von Befehlen (Beispiel.(10 Teller waschen: Teller nehmen, waschen, in den Trockner geben, nehmenTeller abwaschen, in den Trockner geben usw., bis die Teller aufgebraucht sind.)
4 Anwendung des erworbenen Wissens
Aufgabe Algorithmusbefehle mit a=1, b=2, c=3 ausführen
Bitte deaktivieren Sie AdBlock auf dieser Website.
In dieser Lektion werden wir uns einige theoretische Konzepte ansehen, die das Konzept der Programmierung formalisieren. Gleichzeitig formulieren wir die Hauptaufgabe Ihrer Schulung genauer.
Zunächst empfehle ich Ihnen, ein wenig mit dem folgenden Kinderspielzeug zu spielen. Erledigen Sie die ersten fünf Aufgaben, gehen Sie zurück und lesen Sie die Lektion weiter.
Abb.1 Screenshot des Spielfeldes auf code.org
Ich hoffe, dass bei dir alles geklappt hat. Anhand dieses Beispiels beschreiben wir nun einige grundlegende Konzepte:
- Testamentsvollstrecker;
- Darsteller-Befehlssystem;
- Algorithmus.
Im Spielzeug steuern wir einen roten Vogel. Das Ziel jeder Stufe besteht darin, den Vogel zum Schwein zu bringen. Der Vogel kann bestimmte Befehle ausführen, zum Beispiel: vorwärts bewegen, links abbiegen, rechts abbiegen usw.
Eine Person, Maschine oder ein Gerät, die bestimmte Befehle ausführen kann, wird als Ausführender bezeichnet. Bei diesem Spielzeug ist der Darsteller offensichtlich ein Vogel. Der Satz von Befehlen, die der Ausführende versteht und ausführen kann, wird aufgerufen System von Ausführendenbefehlen.
Die Abfolge von Befehlen, die ein Ausführender ausführen muss, um ein Problem zu lösen, wird als Algorithmus bezeichnet.
Es ist notwendig, sich auf mehrere Punkte zu konzentrieren.
Der Ausführende kann nur die Befehle ausführen, die in seinem Befehlssystem enthalten sind.
Das heißt zum Beispiel, dass man dem Vogeldarsteller nicht schreiben kann: „Geh zum Schwein!“ Man kann es zwar genauer aufschreiben, aber es wird nichts passieren, denn... Der Ausführende solcher Befehle weiß es nicht.
Sie können die verfügbaren Befehle in jeder Reihenfolge aufschreiben, die Sie für richtig halten. Ihre Aufgabe als Programmierer besteht darin, eine große komplexe Aufgabe in kleine Einzelschritte zu unterteilen, die für den Ausführenden jeweils verständlich sind. Das Prinzip „Teile und herrsche“ ist wieder am Werk.
Der Darsteller tut genau das, was der Algorithmus ihm sagt.
Der Vogeldarsteller ist sehr zutraulich. Sie hinterfragt nicht, was Sie im Programm schreiben. Wenn Sie beispielsweise vergessen, den Vogel zu wenden, prallt er gegen die Wand. Daher müssen Sie alles selbst überwachen.
Ihre zukünftigen Programme werden oft nicht so funktionieren, wie Sie es beabsichtigt haben. Fehler passieren jedem. Hier ist es wichtig zu verstehen, dass nicht der Computer dumm ist, sondern Sie einen Fehler im Algorithmus gemacht haben. Seien Sie nicht wie schlechte Programmierer, bei denen immer das Programm für alles verantwortlich ist.
Kommen wir nun vom anschaulichen Beispiel zur Computerrealität. Wir schreiben Programme für den Computer, was bedeutet, dass der Computer in unserem Fall der Ausführende ist. Das Befehlssystem besteht aus Standardfunktionen und Konstrukten der C-Sprache.
Was ist das Hauptziel Ihrer Vermittlung der Grundlagen des Programmierens? Beherrschen Sie die Fähigkeit des algorithmischen Denkens. Das heißt, lernen Sie, die Lösung verschiedener Probleme in Form eines Algorithmus für einen bestimmten Darsteller (in unserem Fall einen Computer) aufzuschreiben.
Zusammenfassend also:
Computer Programm– ein Algorithmus zur Lösung eines Problems, geschrieben in einer Programmiersprache.
Ein Algorithmus ist eine genaue Beschreibung der Reihenfolge der Aktionen, die ein Ausführender ausführen muss, um ein Problem zu lösen.
Ein Executor ist eine Person oder ein Gerät, das einen bestimmten Befehlssatz verstehen und ausführen kann.
| § 2.1. Algorithmen und Ausführende
Lektion 14
§ 2.1. Algorithmen und Ausführende
Stichworte:
Algorithmus
Eigenschaften des Algorithmus (Diskretheit; Verständlichkeit; Gewissheit; Wirksamkeit; Massencharakter)
Testamentsvollstrecker
Eigenschaften des Ausführenden (Umfang der zu lösenden Aufgaben; Umgebung; Betriebsart; Befehlssystem)
formale Ausführung des Algorithmus
2.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:
1) Denken Sie an zwei Zahlen;
2) zwei geplante Zahlen hinzufügen;
3) Teilen Sie den resultierenden Betrag durch 2.
Beispiel 2. Die Aufgabe „Geld auf Ihr Telefonkonto einzahlen“ gliedert sich in folgende Schritte:
1) Gehen Sie zum Zahlungsterminal;
2) Wählen Sie einen Telekommunikationsbetreiber.
3) Geben Sie eine Telefonnummer ein;
4) Überprüfen Sie, ob die eingegebene Nummer korrekt ist.
5) eine Banknote in den Geldscheinprüfer einführen;
6) Warten Sie auf eine Nachricht über die Gutschrift des Geldes auf Ihrem Konto;
7) 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. Eines haben sie jedoch gemeinsam: Jeder dieser Prozesse wird durch eine Abfolge 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. 2.1).
Reis. 2.1. Allgemeines Schema des Algorithmus
Algorithmen sind die in der Schule erlernten Regeln der Addition, Subtraktion, Multiplikation und Division von Zahlen, viele grammatikalische Regeln, Regeln geometrischer Konstruktionen usw.
Die Animationen „Arbeiten mit einem Algorithmus“ (193576), „Größter gemeinsamer Teiler“ (170363), „Kleinstes gemeinsames Vielfaches“ (170390) helfen Ihnen, sich an einige Algorithmen zu erinnern, die im Russisch- und Mathematikunterricht gelernt wurden (http://sc.edu. ru /).
Beispiel 4. Ein Algorithmus führt dazu, dass aus einer Zeichenkette eine neue Kette wie folgt entsteht:
1. Die Länge (in Zeichen) der ursprünglichen Zeichenfolge 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 getauscht (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.
2.1.2. Algorithmus-Ausführer
Jeder Algorithmus ist für einen bestimmten Darsteller konzipiert.
Ein Ausführender ist ein Objekt (Person, Tier, technisches Gerät), das in der Lage ist, eine bestimmte Reihe von Befehlen auszuführen.
Unterscheiden 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ünstlerumfeld. 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 Turtle-Befehlssystem besteht aus den folgenden Befehlen:
1. 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;
2. Rechts m (wobei m eine ganze Zahl ist) – bewirkt eine Änderung der Bewegungsrichtung der Schildkröte um t Grad im Uhrzeigersinn.
Aufzeichnen Wiederholen Sie 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 45 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 erforderliche 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 Darstellers enthalten sind.
Wir können sagen, dass ein Algorithmus ein Modell der Aktivität des Algorithmus-Ausführers ist.
2.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.
Diskretes Eigentum 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.
Verständlichkeitseigenschaft 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 Aktionen ausführen kann.
Eigentum 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 als nächstes ausgeführt werden soll. Dadurch wird das Ergebnis des Algorithmus eindeutig durch den Ausgangsdatensatz bestimmt: Wenn der Algorithmus mehrmals auf denselben Ausgangsdatensatz angewendet wird, liefert die Ausgabe immer das gleiche Ergebnis.
Leistungseigenschaft bedeutet, dass der Algorithmus nach einer endlichen, möglicherweise sehr großen Anzahl von Schritten ein Ergebnis liefern muss. 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.
Eigenschaft mit Massencharakter bedeutet, dass der Algorithmus die Möglichkeit seiner Anwendung bieten muss, 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 eine natürliche Zahl n nicht überschreiten. Diese Methode wird „Sieb des Eratosthenes“ genannt, nach dem antiken griechischen Wissenschaftler Eratosthenes (3. Jahrhundert v. Chr.), 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 natürlichen Zahlen von 2 bis n (2, 3, 4, ..., n) hintereinander auf;
2) Rahmen 2 – die erste Primzahl;
3) Streichen Sie aus der Liste alle Zahlen durch, 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 „Sieb des Eratosthenes“ (180279), die in der Unified Collection of Digital Educational Resources veröffentlicht wurde, 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 8. Klasse, der diesen Algorithmus ausführt, verständlich.
Sicherheit- 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 ist das Ergebnis erreicht;
Massencharakter- Die Aktionsfolge gilt für jede natürliche Zahl n.
Die betrachteten Eigenschaften des Algorithmus ermöglichen uns eine genauere Definition des Algorithmus.
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.
2.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 beginnen Sie das Spiel, indem Sie 1 oder 2 Gegenstände nehmen, sodass die Anzahl der verbleibenden Gegenstände ein Vielfaches von 3 ist.
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
Testamentsvollstrecker- ein Objekt (Person, Tier, technisches Gerät), das in der Lage ist, bestimmte Befehle auszuführen.
Ein formeller Darsteller führt immer denselben Befehl auf die gleiche Weise aus. Für jeden formellen Testamentsvollstrecker können Sie Folgendes angeben: Umfang der zu lösenden Aufgaben, Umgebung, Befehlssystem und Betriebsart.
Algorithmus- eine Beschreibung des für einen bestimmten Ausführenden vorgesehenen Handlungsablaufs, der von den Ausgangsdaten zum gewünschten Ergebnis führt und die Eigenschaften Diskretion, Verständlichkeit, Gewissheit, Wirksamkeit und Massencharakter aufweist.
Handlungsfähigkeit des Darstellers formal bietet die Möglichkeit, menschliche Aktivitäten zu automatisieren.
Fragen und Aufgaben
1. Lesen Sie die Präsentationsmaterialien für den Absatz im elektronischen Anhang des Lehrbuchs. Ergänzt die Präsentation die im Text des Absatzes enthaltenen Informationen? Welche Folien könnten Sie Ihrer Präsentation hinzufügen?
2. Was nennt man einen Algorithmus?
3. Wählen Sie Synonyme für das Wort „Rezept“.
4. Nennen Sie Beispiele für Algorithmen, die Sie in der Schule gelernt haben.
5. Wer kann der Ausführende des Algorithmus sein?
6. Geben Sie ein Beispiel für einen formellen Künstler. Geben Sie ein Beispiel, wenn eine Person als formeller Darsteller auftritt.
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. Welche Befehle sollte ein Roboter für die folgenden Funktionen ausführen:
a) Kassierer in einem Geschäft;
b) ein Hausmeister;
c) ein Wachmann?
11. Listen Sie die Haupteigenschaften des Algorithmus auf.
12. Wozu kann das Fehlen einer Eigenschaft in einem Algorithmus führen? Nenne Beispiele.
13. Welche Bedeutung hat es, einen Algorithmus formal ausführen zu können?
14. 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. Finden Sie heraus, wie diese Sequenz heißt.
15. Ein bestimmter Algorithmus erhält 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. Steht der Buchstabe „I“ an letzter Stelle der ursprünglichen Kette, wird als nächster Buchstabe der Buchstabe „A“ geschrieben. Die resultierende Kette ist das Ergebnis des Algorithmus. Wenn die ursprüngliche Zeichenkette beispielsweise „HOUSE“ war, dann ist das Ergebnis des Algorithmus die Kette „DOMMODN“. Es wird die Zeichenfolge „COM“ angegeben. Wie viele Buchstaben „O“ wird es in der Zeichenkette geben, die man erhält, wenn man den Algorithmus auf diese Kette anwendet und den Algorithmus dann erneut auf das Ergebnis seiner Arbeit anwendet?
16. Suchen Sie im Internet nach einer Animation der Schritte des Algorithmus von Eratosthenes. Verwenden Sie den Algorithmus von Eratosthenes, um alle Primzahlen zu finden, die 50 nicht überschreiten.
17. Was wird das Ergebnis sein, wenn Turtle den Algorithmus ausführt (siehe Beispiel 5)?
18. Schreiben Sie einen Algorithmus für den Calculator-Executor auf (siehe Beispiel 6), 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.
19. System der Performer-Befehle Der Konstruktor besteht aus zwei Befehlen, denen Nummern zugewiesen 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).
20. In welcher Zelle sollte sich der Roboter-Ausführende (Beispiel 7) befinden, um nach der Ausführung des Algorithmus 3241 dorthin zurückzukehren?
Gratis Software:
KuMir-System – Eine Reihe von Bildungswelten (laden Sie das Programmarchiv von der Website herunter) oder besuchen Sie die KuMir-Seite ((http://www.niisi.ru/kumir/)
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:
- Schalten Sie den Computer ein (drücken Sie die Taste am Überspannungsschutz).
- Schalten Sie Monitor und Drucker ein.
- Drücken Sie die Power-Taste an der Systemeinheit.
- Warten Sie, bis das Betriebssystem geladen ist und der Desktop angezeigt wird.
- 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 einer Bedingung werden zwei Zahlen, zwei Strings, zwei Variablen oder String-Ausdrücke mithilfe von Vergleichsoperatoren (>,<, =, >=, <=).
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.
