ALGORITHMUS Algoritmo

ALGORITHMUS Algoritmo

(comp.) Justo Fernández López

Diccionario de lingüística español y alemán

www.hispanoteca.eu

Ein Algorithmus in einem formalen System ist ein Verfahren zur schrittweisen Umformung von Zeichenreihen, wobei man für jede Zeichenreihe Z feststellen kann, ob sie aus einer gegebenen Zeichenreihe Z₁ durch Anwendung des Algorithmus gewonnen werden kann oder nicht.

Im Bereich der Arithmetik ist ein Algorithmus ein schematisches Rechenverfahren zur Lösung eines bestimmten Problems.“

[Meschkowski, Herbert: Mathematisches Begriffslexikon. Mannheim: Bibliographisches Institut, 1971, S. 23]

[Meschkowski, Herbert: Mathematisches Begriffslexikon. Mannheim: Bibliographisches Institut, 1971, S. 133]

„Algorithmus: Programm oder Menge von Anwendungen, die explizit und schrittweise angibt, wie ein bestimmtes Problem zu lösen ist: «Um die Mehrwertsteuer zu einem Kaufpreis hinzuzufügen, multipliziere den Kaufpreis mit 15, dividiere die Zahl durch 100 und addiere das Ergebnis zum Kaufpreis.»

[Pinker, Steven: Der Sprachinstinkt. Wie der Geist die Sprache bildet. München: Knaur, 1998, S. 527]

Ein Algorithmus ist ein nach dem arabischen Algebraiker Al Chwarismi benanntes schematisches Rechenverfahren. So ist z.B. in der Mathematik die Methode des Dividierens, Multiplizierens, Addierens oder Substrahierens ein Algorithmus, ein Rechenschema. In etwa diesem Sinne ist auch P. M. Postals (1964, 1967², p.4) Umschreibung des Algorithmus als „mechanical procedure“ zu verstehen. In der (generativen) Linguistik bezeichnet der Terminus (nach N. Ruwet 1968, p. 35) „un ensemble d’instructions explicites, applicables mécaniquement“. Generative Grammatikmodelle sind insofern algorithmisch konzipiert, als der grammatische Mechanismus über eine Anfangskette und eine finite Menge von ‘Instruktionen’ (Regeln) verfügt, die neue Ketten aus der Anfangskette generieren.“

Ein Schlüssel zum Verständnis dazu, wie ein Computer rechnet, ist sicher der Begriff des Algorithmus. Allgemein gesagt ist ein Algorithmus eine Vorschrift, die eindeutig angibt, wie man sich in einer bestimmten Situation zu verhalten hat. So gesehen kann man viele Vorschriften des täglichen Lebens als Algorithmen auffassen. Im Bereich der Mathematik und Informatik betreffen Vorschriften in der Regel aber ausschließlich die Umformung von Zeichen. Ein Algorithmus ist hier eine Vorschrift, die eindeutig angibt, wie bestimmte Zeichen umgeformt werden. Algorithmen für die Umformung von Zeichen sind jedem aus der Schule bekannt. Wenn man Rechnen lernt, lernt man genau das: die Anwendung von Algorithmen. Die Berechnung einer Aufgabe besteht meist darin, dass man ein derartiges Verfahren auf eine Menge vorgegebener Zahlen anwendet und so zur gewünschten Lösung gelangt. So gesehen ist Rechnen nichts anderes als die Umformung von Zeichen nach festgelegten Regeln.

Für theoretische Zwecke ist die Forderung wichtig, dass der Algorithmus endlich sein muss. Er darf z.B. nicht aus einer unendlichen Liste von Anweisungen bestehen, sondern muss mit einer endlichen Anzahl auskommen. Für praktische Zwecke ist dieser Punkt weniger relevant, da man kaum in die Versuchung kommen wird, eine unendliche Vorschrift aufzustellen.

In einer Vorschrift zur Umformung von Zeichen muss natürlich angegeben werden, für welche Zeichen bzw. Zeichenkonfigurationen die Vorschrift gelten soll. Die Menge der Zeichen, auf die die Vorschrift anwendbar ist, wird als das Alphabet des Algorithmus bezeichnet. Das Alphabet eines Algorithmus darf nur endlich viele Elemente enthalten, da sonst die Forderung nach endlich vielen Anweisungen nicht erfüllbar wäre. Die Elemente müssen außerdem deutlich voneinander zu unterscheiden sein, da sonst unklar wäre, welche Regel anzuwenden ist. Das Alphabet eines Algorithmus besteht also aus endlich vielen, diskreten Objekten. [...]

In diesem Zusammenhang muss auch auf den Unterschied zwischen einem Algorithmus und einer Funktion hingewiesen werden. Eine Funktion ist eine Abbildung einer Menge (Definitionsbereich) auf eine andere Menge (Wertebereich), so dass jedem Element des Definitionsbereichs genau ein Element des Wertebereichs zugeordnet ist. Durch eine Funktion werden also Elemente von Mengen einander zugeordnet. Es ist vollkommen offen, um welche Elemente es sich dabei handelt.

Eine Funktion könnte beispielsweise jedem Ball aus einer Menge von Fußbällen eine Zahl zuordnen (z.B. die Anzahl der mit diesem Ball geschossenen Tore). Ein Algorithmus dagegen ordnet nichts einander zu, sondern ist eine Verhaltensvorschrift. Algorithmen werden in erster Linie dazu benutzt, Funktionen zu berechnen. Ein Algorithmus zur Berechnung der Funktion, die jedem Fußball aus einer bestimmten Menge die Anzahl der mit ihm erzielten Tore zuordnet, würde ein Verfahren darstellen, das angibt, wie man zu jedem der Fußbälle die Anzahl der mit ihm geschossenen Tore ermittelt.

Der Unterschied zwischen einer Funktion und einem Algorithmus ist also nicht, dass die Funktion nur abstrakte und der Algorithmus nur konkrete Entitäten betrifft, sondern vielmehr, dass die Funktion etwas ist (eine Zuordnung), während der Algorithmus etwas tut (er ordnet zu).“

[Helm, Gerhard: Symbolische und konnektionistische Modelle der menschlichen Informationsverarbeitung. Eine kritische Gegenüberstellung. Berlin u. a.: Springer-Verlag, 1991, S. 20-21]

Damit die (Turing-)Maschine in der richtigen Weise reagiert, muss man ihr genaue Regeln geben, die explizit in einer wohl definierten Sprache definiert sind. Denn die Maschine kann nicht wie ein Mensch selbst intelligente Entscheidungen treffen. Eine solche Menge von expliziten Regeln, die in jedem einzelnen Fall die Ausführung gewisser Operationen mechanisch gestatten, nennt man einen Algorithmus. (Heringen 1972: 39)

Intuitiv ist ein Algorithmus eine Menge von Regeln, die es uns gestattet, jede spezielle Operation, die einem gewissen Typ von Operationen entspricht, mechanisch auszuführen. Unter einem Algorithmus kann man auch ein mechanisches Verfahren verstehen, das, wenn es auf eine gewisse Klasse von Symbolen (Eingangssymbole) angewendet wird, möglicherweise ein Endsymbol liefert. (Gross/Lentin 1971: 42)

A term in computer science to refer to a program or procedure which, if it is carried out correctly, can be guaranteed to obtain the solution to a particular problem. Not all problems can be solved algorithmically. In that event, the solution may be obtained by means of heuristic procedures – roughly speaking, by means of systematized trial-and-error techniques. (Lyons (ed.) 1970: 317).

Aufzählender Algorithmus: Sagt man, dass die Grammatik G einer über einem Vokabular V definierten Sprache ein aufzählender Algorithmus ist, dann heißt dies, dass es eine Turingmaschine Z_G gibt, die der Zahl 1 einen Satz φ₁, der Zahl 2 einen Satz φ₂, ..., jeder natürlichen Zahl n einen Satz φ_n zuordnet. Die Maschine Z_Gerzeugt daher die rekursiv aufzählbare Menge {φ₁, φ₂, ..., φ_n, ...}. (Gross/Lentin 1971: 93)“ [Abraham, W., S. 30]

„Algorithmus [Mask.; Pl. Algorithmen. Bezeichnung nach dem arab. Mathematiker Al Chwarism (um 825)]. Durch explizite Regeln festgelegtes effektives Rechenverfahren zur automatischen Lösung einer Klasse von gleichartigen Problemen. Ein A. besteht aus einem geordneten System von Grundoperationen und Anwendungsbedingungen, die gewährleisten, dass in einer endlichen Folge von Schritten aus beliebigen Eingabedaten eines Bereichs die entsprechenden Ausgabedaten (Lösungen) erzeugt werden. (Vgl. in der Mathematik die Rechenvorschriften für Multiplizieren, Wurzelziehen u. a.). Um eine mathematisch präzise Definition eines bestimmten A. zu erhalten, kann man eine mathematisch exakt beschriebene, hypothetische Maschine konzipieren, die diesen A. schrittweise nachvollzieht und dadurch überprüft.“ [Bußmann, S. 67-68]

„Algorithmus. Verfahren zu eindeutigen und mechanischen/automatischen Lösung von Aufgaben, das durch eine bestimmte Reihenfolge von Operationen realisiert wird; eine Menge expliziter Regeln, die die mechanische Ausführung bestimmter Operationen ermöglichen (z. B. die Regeln der Multiplikation, Division usw.); eine Folge von Befehlen, deren Befolgung zur Ermittlung, bzw. Konstruktion eines Objekts führt. Zu seiner Realisierung durch elektronische Maschinen/Automaten muss der A. völlig explizit sein; ein solcher (für die Maschine verständlicher) A. ist ein Programm. Häufig wiederkehrende oder Standardbefehle werden durch rekursive Regeln erfasst. Für eine technische Verwendung müssen Modelle und Kalküle als A. ausgeführt sein. Vgl. elektronische Satzanalyse. Bei der automatischen Übersetzung ist »die Gesamtheit der geordneten Regeln bei der Analyse des Eingabetextes« der A. der Analyse, »die Gesamtheit der geordneten Regeln bei der Synthese des Ausgabetextes« der A. der Synthese (Šaumjan, dt. 1971, S. 63).

· durch eine endliche Anzahl von Schritten zu einem bestimmten Resultat führt,

Nach Ju. D. Apresjan hat die moderne Linguistik vom Deskriptivismus den methodologisch wichtigen Gedanken übernommen, dass die natürlichste Form eines linguistischen Modells ein A. ist.

E. Bach weist darauf hin, dass man in der amerikanischen Linguistik der 20er und 30er Jahre allgemein bestrebt war, Grundbegriffe operational zu bestimmen, d. h. Prozeduren zu ihrer Rechtfertigung anzugeben. Dabei erhoffte man sich einen A. (eine Reihe mechanischer Prozeduren), der zu einer korrekten Sprach. und Strukturbeschreibung führt. Nicht viele Forscher hätten eine solche These in ihrer weitgehendsten Form akzeptiert, doch zeige die Literatur der 40er und 50er Jahre, dass diese Vorstellung vielen linguistischen Ansätzen zugrunde lag. Von Y. Bar-Hillel ist nachgewiesen worden, dass es keinen A. für die Reduktion von Sätzen auf Formen mit minimaler Komplexität gibt.“

[Lewandowski, Th.: Linguistisches Wörterbuch. Heidelberg, 1973; Bd. 1, S. 30-31]

„Das Wort „Algorithmus“ leitet sich vom Namen des mittelalterlichen persischen Mathematikers Abu Ja’far Mohammed ibn Mûsâ al-Khowârizm her; er schrieb um das Jahr 825 ein einflussreiches mathematisches Lehrbuch mit dem Titel Kitab al-jabr w’al-muqabala. Die heutige Schreibweise „Algorithmus“ anstelle des früheren, dem Namen ähnlicheren „Algorism“ erklärt sich vermutlich aus der Assoziation mit dem Wort „Arithmetik“. (Übrigens stammt das Wort „Algebra“ von dem arabischen „aljabr“ im Buchtitel).

Beispiele für Algorithmen kannte man jedoch schon lange vor al-Khowârizm. Einer der bekanntesten stammt aus der griechischen Antike und wurde um das Jahr 300 vor unserer Zeitrechnung von Euklid entwickelt. Der Euklidische Algorithmus ist ein Verfahren, den größten gemeinsamen Teiler zweier Zahlen zu bestimmen. Wir wollen uns ansehen, wie er funktioniert - am besten anhand von zwei konkreten Zahlen, etwa 1365 und 3654:

Die letzte Zahl, durch die wir dividiert haben, also 21, ist der gesucht größte gemeinsame Teiler. Der Euklidische Algorithmus selbst ist das systematische Verfahren, mit dem wir diesen Teiler bestimmt haben.“

[Pernrose, Roger: Computerdenken. Des Kaisers neue Kleider oder Die Debatte um Künstliche Intelligenz, Bewusstsein und die Gesetze der Physik. Heidelberg: Spektrum der Wissenschaft, 1991, S. 28-29]

„Erinnern wir uns an den oben beschriebenen Euklidischen Algorithmus: Die Größe der Zahlen, mit denen er arbeiten kann, ist im Prinzip unbegrenzt. Der Algorithmus - das heißt die allgemeine Rechenvorschrift - bleibt unabhängig von der Größe der Zahlen immer derselbe. Für sehr große Zahlen kann der Vorgang in der Tat sehr lange dauern und ziemlich viel „Kritzelpapier“ für die Ausführung der eigentlichen Rechnungen verschlingen. Aber der Algorithmus bleibt für beliebig große Zahlen stets dieselbe finite Menge der endlich vielen Rechenbefehle.“

[Pernrose, Roger: Computerdenken. Des Kaisers neue Kleider oder Die Debatte um Künstliche Intelligenz, Bewusstsein und die Gesetze der Physik. Heidelberg: Spektrum der Wissenschaft, 1991, S. 33]

„Im Zusammenhang mit dieser Diskussion sollte ich darauf hinweisen, dass die Ausdrücke „Algorithmus“ und „algorithmisch“ sich auf alles beziehen, was sich (prinzipiell) auf einem Computer simulieren lässt. Das schließt gewiss „Parallelrechner“ ein, aber auch „neuronale Netzwerke“ (hochgradig parallele Supercomputer, so genannte connection machines).“

„Otra nota específica importante en el generativismo es la presentación de la gramática como un algoritmo, mecanismo matemático independiente que señala la pertenencia de toda secuencia gramaticalmente correcta a la gramática de una lengua. El término algoritmo le fue sugerido a N. Chomsky por la analogía con la matemática. Así como un niño no aprende de memoria todos los productos infinitos posibles a partir de los números naturales, sino que aprende las reglas de multiplicar (un algoritmo), del mismo modo un individuo no aprende todas las oraciones de una lengua, sino un conjunto de reglas para formarlas.

La formulación del concepto de algoritmo (= gramática) nos la ofrece N. Chomsky en los siguientes puntos:

(2) ante cualquier oración se plantea el problema de la pertenencia a S y de la posibilidad de un procedimiento mecánico con el que, dada una secuencia arbitraria x, al fin de una duración finita se pueda reconocer si x es o no miembro de S;

(3) si existe tal procedimiento mecánico, entonces se dice que S es decidible o que existe un algoritmo para decidir la pertenencia a S, o que el problema de decisión para S es recursivamente decidible.

Según Maurice Gross y Andrén Lentin (1967), el concepto intuitivo de algoritmo comporta las siguientes características: memorizar un algoritmo es obtener un conjunto de instrucciones mediante las cuales se alcance un conjunto indeterminado de resultados o se pueda, mediante él, comprobar los ya obtenidos. Algoritmo es un procedimiento mecánico que, aplicado a una cierta clase de símbolos (símbolos de entrada), nos da eventualmente un símbolo de salida.

(2) un operador (humano, mecánico, óptico o electrónico) que relaciones las instrucciones y efectúe el cálculo;

(3) dispositivos (papel, ruedas dentadas, memorias magnéticas, etc.) que permitan efectuar stocker e identificar las distintas etapas del cálculo;

(4) que los procesos sean esencialmente discretos, aunque las unidades manipuladas sean continuas;

(5) que la secuencia de operaciones elementales que se han de efectuar estén perfectamente delimitadas.“

[Báez San José, Valerio: Introducción crítica a la gramática generativa. Barcelona: Planeta, 1975, p. 36]

El término algoritmo, tomado de la cibernética, se emplea también en lingüística para aludir al procedimiento dirigido a resolver operaciones complejas, de forma automática e inequívoca, por medio de una serie de reglas u operaciones elementales formalizadas. Se trata pues, de la formalización de un procedimiento sistemático que, mediante un número finito de pasos, da como resultado la solución a un problema, o dicho con otras palabras, es un conjunto detallado de estados secuenciales que deben seguirse para producir un resultado concreto. En muchas escuelas lingüísticas, como la Gramática Generativa, se estima que el ’algoritmo’ es la forma más lógica y natural de representar los modelos lingüísticos. El término ’algoritmo’ se utiliza frecuentemente en la literatura computacional para designar el conjunto de pasos que formalizan un problema lingüístico y hacen posible que éste pueda resolverse de forma automatizada. La tarea del lingüista computacional consiste, por tanto, en describir cómo debe resolverse este problema lingüístico y para ello debe describir con detalle los diferentes pasos que deben seguirse para llegar al resultado esperado. Así, por ejemplo, para llevar a cabo el análisis sintáctico de una oración debemos contar con un ’algoritmo’ que establezca cómo deben asignarse las estructuras sintácticas a las diferentes partes de la oración en función de una gramática determinada. La rápida explosión de la lingüística computacional está extendiendo sus métodos a los demás componentes de la gramática.»

[Alcaraz Varó, Enrique / Martínez Linares, María Antonia: Diccionario de lingüística moderna. Barcelona: Editorial Ariel, 1997, p. 39]

“Alonzo Church demostró en 1936 la imposibilidad de hallar un procedimiento decisorio adecuado para la lógica elemental (incluyendo, por supuesto, la lógica cuantificacional poliádica).

El resultado obtenido por Church es, como el famoso resultado de Gödel (Über formal unentscheidbare Sätze der Principia mathematica und verwandte Systeme, 1931), uno de los «teoremas de limitación», que pusieron en crisis en los años treinta la ilimitada fe que hasta entonces se había venido depositando en los métodos axiomáticos y dieron lugar, al mismo tiempo, a una de las corrientes más fecundas de la investigación lógico-matemática de los últimos cuarenta años: la teoría de la computabilidad.

Desde principios de siglo David Hilbert había defendido el punto de vista (históricamente sostenido por Ramón Llull en la Edad Media y Leibniz en la Edad Moderna) de que todo problema lógico y matemático podría ser resuelto por procedimientos mecánicos. De ahí la importancia que adquirió hacia los años veinte, el llamado Entscheidungsproblem (problema de la decisión). De hecho, el problema de la decisión para el cálculo elemental de cuantores era, en el sentir de Hilbert, el problema fundamental de la lógica matemática.

Sorprendentemente, los hallazgos más interesantes en la investigación del problema de la decisión fueron hallazgos negativos que establecieron la existencia de problemas insolubles y las fatales limitaciones de sistemas axiomáticos de interés fundamental. En 1931 Kutl Gödel demostró que todo sistema axiomático que pretenda formalizar la aritmética elemental es incompleto. Y en 1936 Church probó primero la indecidibilidad de la aritmética, y luego, con ayuda de este resultado, la indecidibilidad de la lógica elemental (teorema de Church). Church propuso definir el concepto intuitivo y más bien vago de «función efectivamente calculable» mediante el concepto matemáticamente preciso y riguroso de «recursividad». Tal es el fin que persigue la llamada

Tesis de Church (1936): Toda función efectivamente calculable es una función recursiva.

Con la ayuda de su tesis probó Church que no es posible hallar una solución general para el problema de la decisión en teoría elemental de números, es decir, que el sistema formal de la aritmética es indecidible. [...]

En su contribución A note on the Entscheidungsproblem (1936) Church mostró que el sistema formal de teoría elemental de números no podía ser reducido al sistema formal de lógica elemental mediante una serie de transformaciones tendentes a eliminar los símbolos aritméticos; y a continuación hizo ver, como consecuencia de tal reducción, que si hubiera un procedimiento decisorio para toda la lógica elemental, lo habría para la teoría elemental de números. Pero teniendo en cuenta el anterior resultado de Church acerca de la indecidibilidad de la teoría elemental de números, queda establecida la indecidibilidad de la lógica elemental. [...]

Teorema de Church: El caso general del problema de la decisión de L es insoluble. Esto es: la lógica elemental de la cuantificación es indecidible.

El teorema de Church posee relevancia filosófica. Desde el punto de vista de la filosofía, el interés principal de este aserto está en que por él se establece, o se pretende establecer, la no mecanicidad de la lógica formal. Pues si bien es cierto que existen algoritmos que permiten revolver de modo mecánico grandes grupos de problemas de la lógica elemental, según el teorema de Church no existe ni puede existir un algoritmo que los resuelva mecánicamente todos. La operación deductiva de la razón no es totalmente mecanizable.”

[Garrido, Manuel: Lógica simbólica. Madrid: Editorial Tecnos, ²1977, pp. 349-352]