Diskussion:Algorithmus

Müsste es nicht heissen "Ein Algorithmus ist eine wohldefinierte endliche Methode oder Prozedur, um ein Problem zu lösen."

Markus: Ich finde das sprachlich ungeschickt. Das "um" stört mich. Besser wäre: "Ein Algorithmus ist eine wohldefinierte endliche Methode oder Prozedur zur Lösung eines Problems."

Markus: Habe dies in den Text integriert --66.171.5.203 17:38, 28. Feb 2004 (CET)

Ich tendiere dazu, diesen Artikel vollständig zu überarbeiten (und von der jetzigen Version nicht viel übrig zulassen) und zwar aus folgenden Gründen:

Es gibt insgesamt 4 Beschreibungen/Definitionen eines Algorithmus (Einleitung, Algorithmus, Grundprinzip, Definition)
Schlechte Gliederung
Teilweise (nach meinem Verständnis von Algo.) Falschaussagen (schon in der Definition) wie " Der Ablauf des Verfahrens ist zu jedem Zeitpunkt eindeutig definiert" (Gegenbsp. nicht-deterministischer Algorithmus) oder " Das Verfahren muss in endlich vielen Schritten zum Ende gelangen." (Gegenbsp. nicht terminierender Algorithmus) - sollte ich da falsch liegen, ist der von mir angelegte Artikel Determinismus (Algorithmus) auch falsch.
Unvollständig
...

Mein Vorschlag der Gliederung:

Einleitung (ohne Überschrift)
Definition
Eigenschaften (Finitheit, Komplexität, Terminierung, Determiniertheit, Determinismus, Effizienz, ...?)
Implementierung - da können dann Sätze wie "Algorithmen werden meistens als Computerprogramm implementiert." rein
Beispiele
Geschichte

Ich finden den Artikel ziemlich wichtig, weil Algorithmus ein Basisthema für die Informatik ist (somit auch für Wikipedia:WikiProjekt Wirtschaftsinformatik). Sollte es kein Feedback geben, lass ichs, weil alleine ist mir das Thema zu umfangreich/komplex (alleine zur Definition hab ich im Internet schon umfangreichste Diskussionen gefunden - Bsp. google-groups) --brunft 16:02, 13. Mär 2004 (CET)

Ich stimme dir voll und ganz zu. Die jetzige Form des Artikels ist ziemlich unübersichtlich. Ich hab mir deshalb erlaubt den Artikel neu zu gliedern. Dabei habe ich einiges ergänzt. Das Problem mit den Definitionen besteht glaube ich immer noch, allerdings abgeschwächt: Im ersten Satz sollte eine einfache Definition vorkommen. Der Geschichtsteil beinhaltet auch eine Definition, jedoch im historischen Kontext ;). Unter dem Gliederungspunkt Definition findet sich eine sehr knappe Definition(wie sie beispielsweise im Informatikschulunterricht gegegeben wird). Unter Implementierung könnten vielleicht noch Beispielimplementationen des Beipiels: In einer Programmiersprache, als schriftliche Rechnung etc. Aber ich wollte erstmal abwarten ob eine Neustrukturierung überhaupt erwünscht ist.-- Ich hab hunga 18:36, 3. Mai 2004 (CEST)Beantworten

Habe die Endlichkeit aus dem Artikel rausgenommen und auf das Halteproblem verwiesen. Der Artikel hat sich bislang selbst widersprochen: Erst heißt es, Algos seien endlich, dann am Ende heißt es, ob sie terminieren, lernt man in der Berechenbarkeitstheorie. Naja.

--Thorwald C. Franke 03:00, 9. Apr 2004 (CEST)

Also ich glaube, daß Du das verschlimmbessert hast: Algorithmen sind immer endlich. Berechenbarkeitstheorie sagt aus, ob es einen Algorithmus gibt (der endlich ist), der das gegebene Problem loest.

Sprich: der Satz, "ob sie terminieren" ist falsch. Ein Algorithmus der nie terminiert ist halt kein Algorithmus. --DaTroll 11:51, 9. Apr 2004 (CEST)

Hm, das ist zunächst eine definitorische Frage.

Diese löst man am besten, indem man in Fachliteratur nachschlägt.

Schüler-Duden Informatik:

Hier sind Algorithmen auch nciht endlich. Turingmaschinen werden als

eine Realisierung angesehen. Also auch nicht-endliche.

Zitat: "Für die Praxis sind meist nur solche Algorithmen von Bedeutung,

die für jede Eingabe nach endlich vielen Schritten ein Resultat liefern

und anhalten."

Goldschlager/Lister, "Informatik" (ein Klassiker):

S. 25: Prozesse/Algorithmen können unendlich sein (z.B. Alarmanlagen steuern),

S. 79: Kapitelüberschrift: "Theorie der Algorithmen",

darunter dann Berechenbarkeitstheorie etc. => Algos können auch nciht-endlich sein.

Lexikon der Informatik und Datenverarbeitung:

Auch hier gibt es die Möglichkeit, dass die Berechnung nciht abbricht.

Fazit:

Algorithmen sind auch nciht-endlich.

--Thorwald C. Franke 20:05, 9. Apr 2004 (CEST)

Könnte es sein, daß da gerade zwei Sachen durcheinander gehen?

Sind Algorithmen endliche Beschreibungen? (Ja)
Ist die Ausführung eines Algorithmus ein endlicher Prozeß? (Nein, Beispiel: Der Algorithmus, mit dem man alle natürlichen Zahlen erzeugen kann.)

--Skriptor 20:32, 9. Apr 2004 (CEST)

Nein, ich glaube nicht, dass ich DaTroll falsch interpretiert habe. Das Wort "terminieren" macht deutlich, worum es ihm geht. Er meint, dass z.B. eine Endlosschleife kein Algorithmus mehr wäre. Ist es aber doch. Endlosschleifen werden sogar praktisch eingesetzt.

Hier geht es bei Endlichkeit klar um das Halteproblem.

--Thorwald C. Franke 00:50, 10. Apr 2004 (CEST)

Thorwald hat mich schon richtig verstanden. Und ich glaube dann einfach mal, dass er Recht hat. Viele Gruesse, DaTroll 15:35, 13. Apr 2004 (CEST)

Ein Computer ist ein Werkzeug, welches bei der Lösung bestimmter Probleme hilft.

Was soll der Leser aus diesem Satz lernen? Insbesondere, wenn er sich folgenden Sachverhalt vor Augen führt:

Ein Hammer ist ein Werkzeug, welches bei der Lösung bestimmter Probleme hilft.

Ich habe folgenden Abschnitt rausgeschmissen:

Grundprinzip eines Algorithmus

Ein Algorithmus basiert auf zwei Grundelementen, der (Rechen-)Anweisung und dem bedingten Sprung. Ein bedingter Sprung zeigt an, an welcher Stelle im Algorithmus fortgefahren werden soll, wenn eine bestimmte Bedingung erfüllt ist (z.B. die, dass zwei Werte gleich sein müssen), und an welcher fortgefahren werden soll, wenn diese Bedingung nicht erfüllt ist (wenn im Beispiel also die Werte nicht gleich sind).

Das stimmt so einfach nicht; es gibt ganz verschiedene Methoden, einen Algorithmus zu formulieren, und das Verfahren mit bedingten Sprunganweisungen ist nur eine davon. Eine andere Möglichkeit sind Wenn-Dann-Abfragen in Verbindung mit Schleifen oder Markov-Algorithmen, die auf reinen Zeichenersetzungsregeln beruhen, oder µ-rekursive Funktionen. All diese Verfahren sind äquivalent im Sinne der rechnerischen Mächtigkeit. --Mussklprozz 15:30, 25. Apr 2004 (CEST)

"Typischerweise wird ein Algorithmus durch eine endliche Folge von Anweisungen beschrieben, die nacheinander ausgeführt und oft in festgelegter Weise wiederholt werden."

Die Endlichkeit hat nichts mit dem Begriff des Algorithmus zu tun.
Der Beweis, daß die rationalen Zahlen zwar unendlich sind, aber nicht dicht (im Gegensatz zu den reellen Zahlen) liegen, wird zum Bsp. über die Abzählbarkeit geführt. (Siehe auch Eulers Beweis, der Transzendenz von PI.). Das Abzählen sehe ich als einen nicht endlichen Algorithmus an. Man belehre mich eines Besseren.

In dem Satz "Die Theoretische Informatik beschäftigt sich u.a. mit der Frage, welche Problemstellungen algorithmisch, d.h. mittels genau definierter Handlungsanweisungen, gelöst werden können und wie rechenaufwendig Lösungen gegebener Probleme mindestens sein müssen." liegt dann auch schon der Hund begraben. Basis der Analyse zu diesem Begriff muß natürlichen die Algorithmentheorie sein. Die Formulierung ist nicht nur inhaltlich, sondern auch sprachlich ("Lösungen gegebener Probleme") sehr fragwürdig.

Wer kam eigentlich auf die merkwürdige Idee der "Verballhornung" im Bereich Geschichte? Scheinbar haben diese Bemerkung schon Einige Internetseiten aus wikipedia übernommen...

Wie gesagt, ich lass mich gern überzeugen. --Ping 16:16, 25. Apr 2004 (CEST)

Vielleicht hilft die Umstellung, das Problem deutlicher werden zu lassen, dass hier teils redundante,aber teils auch nicht redundante Erklärungen des Begriffs vorhanden sind. Es wäre wohl gut, alles unter einen Hut zu bringen. -Hati 16:32, 25. Apr 2004 (CEST)

Ich hab versucht, umzustellen, die Definitionen (allgemeine Definition, mathematische Definition) zu ordnen, und auch das Endlichkeitsproblem klar heraus zu stellen. Was meint Ihr? --Mussklprozz 16:39, 25. Apr 2004 (CEST)

Vielleicht habe ich jetzt zu schnell gelesen aber das "Ein Algorithmus ist eine eindeutige Beschreibung eines Verfahrens zur Lösung einer bestimmten Klasse von Problemen." Hat mir eigentlich ganz gut gefallen, vor allem weil es wie im aller ersten Erklärungssatz ohne Prozedur auskommt, die ja im strengen Sinne auch nur ein Algorithmus ist. Vielleicht wird die Materie noch fassbarer, wenn man sie gegen Heuristik abgrenzt? ansonsten: der Fortschritt ist nicht aufzuhalten :-> -Hati 16:51, 25. Apr 2004 (CEST)

Warum Deine Version von 16:25, 25. Apr 2004 von Musklprozz so schnell gelöscht wurde, verstehe ich auch nicht. Die Formulierung "Ein Algorithmus ist eine eindeutige Beschreibung eines Verfahrens zur Lösung einer bestimmten Klasse von Problemen." als Einleitung kann man durchaus stehen lassen. Wenn man auf die Endlichkeit so einen Wert legt, ließe sich das meiner Meinung nach auch durch das Wort "Abbruchbedingung" klar stellen. --Ping 17:32, 25. Apr 2004 (CEST)

Danke für Eure Stellungnahme.

Ich war gleichzeitig mit Hati am Arbeiten; beim Speichern gab es einen Bearbeitungskonflikt. Darauf hin habe ich vor dem Speichern Hatis Version gegen die Vorversion geprüft und gesehen, dass er eine Umstellung im Sinn hatte. Genau das hatte ich unter anderem ja auch vor. Na ja, und als ich das gesehen hatte, habe ich meine bereits fertig vorbereitete neue Version eingesetzt.

Hatis Einleitungssatz habe ich jetzt in die Definition übernommen; ich finde ihn auch besser, weil weniger technisch und somit einladender als die Version mit den Eingabe- und Ausgabegrößen. Vorher war er meinem Aufräumen unter den Definitionen zum Opfer gefallen, wo sich meines Er8ens doch einiges im Kreis herum gedreht und wiederholt hat, siehe die Diskussion weiter oben.

Dass das mit der Endlichkeit ein Problem darstellt, geht aus der Diskussion oben hervor. Daher habe ich versucht, klar abzugrenzen, in welcher Hinsicht ein Algorithmus endlich ist und in welcher Hinsicht nicht.

--Mussklprozz 19:31, 25. Apr 2004 (CEST)