Datenstrukturen in Apl2: Mit Anwendungen Aus Der Künstlichen Intelligenz

ISBN-13: 9783540557470 / Niemiecki / Miękka / 1992 / 342 str.

Hanspeter Bieri; Felix Grimm

Opis

Mit dem Erscheinen von PC-Versionen (seit 1988) hat die leistungsfahige Programmiersprache APL2 deutlich an Attraktivitat und Verbreitung gewonnen. Als Entwicklungssystem fur komplexe Anwendungen, die eine schnelle, interaktive Analyse grosser Datenmengen erfordern, hat APL sich einen festen Platz in der Praxis erobert, z.B. bei Banken und Versicherungen. Das vorliegende Buch ist eine hohere Einfuhrung in APL2. Programmierer mit geringen Vorkenntnissen in APL oder APL2 werden anhand sorgfaltig ausgewahlter Beispiele Schritt fur Schritt mit den Moglichkeiten der Sprache vertraut gemacht. Sie werden angeleitet, gut strukturierte Anwendungen zu entwerfen und die zugehorigen - oft recht anspruchsvollen - Algorithmen in elegante, effiziente und trotzdem verstandliche Programme umzusetzen. Dabei werden praxisgerechte Anwendungen bevorzugt, und nicht solche, die sich fur APL2 besonders gut eignen. Ein weiteres, wichtiges Ziel des Buches ist es, auch Pascal- oder Fortran-Programmierer in APL2 einzufuhren. Ihnen wird gezeigt, wie vertraute Techniken auch in APL2 verwendet werden konnen und wie sich bekannte Datenstrukturen, wie Listen, Baume und Graphen, auf einfache Weise realisieren lassen. Ein besonderes Merkmal des Buches ist seine Ausrichtung auf Anwendungen aus der Kunstlichen Intelligenz: Einfache, aber typische Beispiele aus den Teilbereichen Heuristisches Suchen, Bildverarbeitung und Expertensysteme bieten nicht nur eine Gelegenheit, die erworbenen APL2-Kenntnisse sinnvoll einzusetzen und zu vertiefen, sondern fuhren zugleich auch anschaulich in eines der aktuellsten und faszinierendsten Gebiete der heutigen Informatik ein."

Spis treści

A. Grundlagen.- 1. Einleitung.- 2. Datentypen und Datenstrukturen.- 3. Kurzeinführung in APL2.- 3.1 Grundinformationen über APL2.- 3.2 Arrays.- 3.2.1 Standarddatentypen.- 3.2.2 Einfache Skalare.- 3.2.3 Einfache Vektoren.- 3.2.4 Beliebige einfache Arrays.- 3.2.5 Verschachtelte Arrays.- 3.3 Programmieren.- 3.3.1 Ein erstes APL2-Programm.- 3.3.2 Die äussere Form eines Programms.- 3.3.3 Sprünge.- 3.3.4 Rekursion.- 3.3.5 Die primitiven Funktionen Execute und Format.- 3.3.6 Definierte Operatoren.- 3.4 Zur Systemumgebung.- 3.4.1 Allgemeines.- 3.4.2 Umgang mit Workspaces und Bibliotheken.- 3.4.3 Hilfen für das Testen von Programmen.- 3.5 Programmbeispiele.- 3.5.1 Entfernen von Duplikaten aus einem Vektor.- 3.5.2 Selektive Spezifikation mittels Pick.- 3.5.3 Suchpfad eines Arrayelementes bestimmen.- 3.5.4 Ein Zerlegungsproblem.- 4. Abstrakte Datentypen und ihre Implementierung.- 4.1 Abstrakte Datentypen.- 4.2 Drei Implementierungsmethoden.- 4.2.1 APL2-gerechte Implementierung.- 4.2.2 Nachbilden des List Processing in APL2.- 4.2.3 Matrix-Implementierung.- 4.2.4 Pseudopointer-Implementierung.- B. Lineare Datenstrukturen.- 5. Lineare Listen.- 5.1 Der abstrakte Datentyp Lineare Liste.- 5.2 APL2-gerechte Implementierung von linearen Listen.- 5.3 Matrix-Implementierung von linearen Listen.- 5.4 Pseudopointer-Implementierung von linearen Listen.- 5.5 Vergleich der drei Implementierungsmethoden.- 6. Stack und Queue.- 6.1 Stack.- 6.1.1 Der abstrakte Datentyp Stack.- 6.1.2 Implementierung des ADT Stack.- 6.1.3 Eine Anwendung des ADT Stack.- 6.2 Queue.- 6.2.1 Der abstrakte Datentyp Queue.- 6.2.2 Implementierung des ADT Queue.- 6.2.3 Eine Anwendung des ADT Queue.- 7. Klassische Algorithmen und ihre Eignung für APL2.- 7.1 Vorbemerkungen.- 7.2 Der Algorithmus von Horner.- 7.3 Binäres Suchen.- 7.4 Der Merge-Algorithmus.- 7.5 Schlussfolgerungen.- C. Nichtlineare Datenstrukturen.- 8. Mengen und Abbildungen.- 8.1 Der abstrakte Datentyp Menge.- 8.2 Implementierung durch Aufzählen der Elemente.- 8.3 Bitvektor-Implementierung.- 8.4 Abbildungen.- 8.4.1 Der ADT Abbildung.- 8.4.2 Implementierung des ADT Abbildung.- 8.4.3 Eine Anwendung des ADT Abbildung.- 8.5 Priority Queues.- 8.5.1 Der abstrakte Datentyp Priority Queue.- 8.5.2 Implementierung des ADT Priority Queue.- 8.5.3 Eine Anwendung des ADT Priority Queue.- 8.6 Anwendung auf relationale Datenbanken.- 9. Bäume.- 9.1 Der abstrakte Datentyp Binärer Baum.- 9.2 Implementierung des ADT Binärer Baum.- 9.3 Huffman-Code.- 9.3.1 Konstruktion des Huffman-Baumes.- 9.3.2 Codieren von Nachrichten nach Huffman.- 9.3.3 Decodieren von Binärzeichenfolgen nach Huffman.- 9.4 Der abstrakte Datentyp Allgemeiner Baum.- 9.5 Implementierung des ADT Allgemeiner Baum.- 9.6 Tries.- 10. Graphen.- 10.1 Der abstrakte Datentyp Graph.- 10.2 Implementierung von gerichteten Graphen.- 10.2.1 Implementierung als Mengenpaar.- 10.2.2 Implementierung mittels Adjazenzmatrix.- 10.2.3 Implementierung mittels Adjazenzliste.- 10.2.4 Konversion der drei Implementierungsarten.- 10.3 Exhaustive Graphsuche.- 10.4 Transitive Hülle von Graphen.- 10.5 Zusammenhangskomponenten.- 10.6 Ergänzende Bemerkungen.- D. Anwendungen aus der Künstlichen Intelligenz.- 11. Heuristische Graphsuche.- 11.1 Suchverfahren in der Künstlichen Intelligenz.- 11.2 Markierte Graphen.- 11.3 Heuristische Graphsuche.- 12. Bildverarbeitung und Bildanalyse.- 12.1 Einleitung.- 12.2 Bildvorverarbeitung.- 12.2.1 Verbesserung des Kontrastes.- 12.2.2 Eliminieren von gewissen Grauwerten.- 12.2.3 Binärisieren von Bildern.- 12.3 Konturlinien-orientierte Bildsegmentierung.- 12.3.1 Konturliniendetektion nach Sobel.- 12.3.2 Konturlinienverbesserung mittels Schwellwertoperationen.- 12.3.3 Bestimmen der Koordinaten von Konturlinienpunkten.- 12.4 Regionen-orientierte Bildsegmentierung.- 12.4.1 Zusammenhängende Bildkomponenten mittels Graph bestimmen.- 12.4.2 Zusammenhängende Bildkomponenten direkt im Bild bestimmen.- 12.5 Bildsequenzen.- 12.5.1 Differenzbilder.- 12.5.2 Differenz von Konturlinienbildern.- 12.6 Zusammenfassung.- 13. Wissensverarbeitung und Expertensysteme.- 13.1 Einleitung.- 13.2 Regelbasierte Wissensdarstellung und -nutzung.- 13.2.1 Wissensdarstellung mittels Regeln.- 13.2.2 Wissensnutzung mittels Regeln.- 13.3 Ein regelbasiertes Expertensystem.- 13.4 Eine Erklärungskomponente für regelbasierte Expertensysteme.- 13.5 Frame-basierte Wissensdarstellung und -nutzung.- 13.5.1 Wissensdarstellung mittels Frames.- 13.5.2 Wissensnutzung mittels Vererbung.- 13.5.3 Wissensnutzung mittels Matching.- 13.6 Ergänzende Bemerkungen über Expertensysteme.- 14. Künstliche Intelligenz und APL2.- 14.1 Künstliche Intelligenz.- 14.2 APL2 als KI-Sprache.- A. Weitere Programme.- A.1 Die Funktion PATHALL.- A.2 Die Funktion LOCATEV.- A.3 Die Funktion INSERTDB.- A.4 Die Funktion CONSULT.- B. Die verwendeten APL2-Symbole.- Literatur.- Sachwortverzeichnis.