Abspeicherung:_katnr-gegenstand.doc
Software life Cycle (Wasserfallmodell)
Phase Produkt der Phase
Analyse (Probleme finden, Was soll das System tun?)SpezifikationDesign (Wie soll das System das tun?)ProgrammiervorlageProgrammierung, RealisierungProgrammTestTestberichte, Mängel Þ besseres ProgrammWartung
Parallel zu diesen Phasen:
Standardisierung
Review
Dokumentation
Testfälle (schon in Analysephase)
Controlling
Integrationsstrategie
Problem: Mehrere Datenbanken in einem Unternehmen können Mehrfachspeicherung von gleichen Daten und somit Redundanzen zur Folge haben, auch wenn jede Datenbank für sich normalisiert ist Þ
unternehmensweites Datenmodell (UDM) = Information Engineering nach James Martin
Unterschied zwischen Software und Information Engineering:
vor der Analysephase kommt die
Planningphaseunternehmensweites Betrachten des Problems
Vergleich:
Information Engineering Städteplaner
Software Engineering Architekt
Programmierer Maurer
Funktionsdekomposition (Aufgabenzerlegung)
Die Funktionsdekomposition dient zur besseren Verdeutlichung der Spezifikation (welche Funktionen sollen enthalten sein?). Es werden die Funktionen Schritt für Schritt verfeinert (Top down) bis das unterste Level der Detailierung erreicht wird. Ist ein Hilfsmittel für die Sezifikation
Zweck:
Mit dem Kunden ein Bild davon machen, was das Produkt leisten soll.
Vertragsgrundlage
Nachteile:
Manche Funktionen lassen sich nicht eindeutig zuordnen (z.B. Stundenplan für Lehrer ausdrucken, sowohl zur Lehrerverwaltung als auch Reports drucken)
Kann sehr groß und unübersichtlich werden
Verknüpfung zwischen Daten und Funktionen fehlen (Þ DFD)
Wenn man die Funktionsdekomposition mit den Datenflüssen erweitert (Funktionsdekomposition + ERD) erhält man ein
Datenflußdiagramm
Das Datenflußdiagramm zeigt die Prozesse und den Fluß der Daten durch diese Prozesse.
4 Grundkomponenten:
Datenfluß: Pfeil mit Name darüber, zeigt den Datenfluß durch das System (z.B. Suchergebnis)
Prozeß: Abgerundetes Rechteck (Ellipse) mit Namen des Prozesses (sprechender Name!), Keine andere Information über den Prozeß in Datenflußdiagramm (z.B. Termin planen)
Data Store: Name zwischen zwei waagrechten Strichen, repräsentiert ein lokales File in das entweder Daten eingelesen werden, oder von dem Daten gelesen werden (z.B Schüler)
Terminator: Rechteck mit Namen, Gibt die Herkunft (Source) bzw.
den Empfänger (Sink) der Daten an, doch sie werden meistens nicht in die Datenflußdiagramm eingezeichnet (z.B. Benutzer)
Jede Funktion wird auf eine Seite aufgeteilt, es werden alle Datenströme von und zur Funktion eingezeichnet.
DFD für den Prozeß Report:
Ein Datenflußdiagramm zeigt den Datenfluß in einem konkreten Prozeß, der wieder aus mehreren Unterprozessen besteht, die man wieder in eigene Datenflußdiagramm zerlegen kann.
So kann man ein System bis in die tiefsten Ebenen zerlegen. Ein Datenflußdiagramm gibt uns keine Details über die Datenflüsse innerhalb der Unterprozesse, um mehr über diese Datenflüsse zu erfahren, muß für den Prozeß ein eigens DFD erstellt werden.
Die Aufteilung der Diagramme muß konsistent sein, d.h. die Funktion im Unterdiagramm muß genau so viele Zu- und Abflüsse haben, wie das übergeordnete Diagramm.
Hyperdiagramm (in IEF: Repository)
großes Diagramm mit allen Informationen (Funktionen, Tabellen, Beziehungen)
Nachteil: Durch die vielen Informationen zu kompliziert und unübersichtlich (wird nicht gezeichnet) Þ Teilung in Teildiagramme (DFD), entweder Funktionen oder Informationen (Tabellen, Beziehungen) weglassen.
IEF (Information Engineering Facility)
CASE - Tool (Computer Aided Software Engineering): EDV unterstütztes Hilfsmittel für die Erstellung von DFD, ERD, FD.
CDUR - Matrix
TABELLEN
PROZESSE /
Schüler
Lehrer
FUNKTIONEN
Schüler suchen
R
Klassenb.
Blatt 1
X
X
.
.
.
C
Reorganisation
D
Versatz
R/U
nach Stärke geordnet
C ...
Create
D ... Delete
U ...
Update
R ... Read
oder höchste Stärke
CDUR Þ DFD nicht ableitbar; z.B.: externe Pfeile
CDUR Þ genauer bezüglich Flüsse
Objektorientierte Programmierung
Unterprogramme und Stacks
Der Stack (=Stapel) dient zur Variablen- oder Wertübergabe von einem Programm zu seinem Unterprogramm.
Der Stack ermöglicht die Kommunikation zwischen Hauptprogramm und Unterprogramm. Der Stack funktioniert nach dem Prinzip First In Last Out.
PUSH ... ein Wert wird in den Stack geschrieben
PUSH x Þ x wird auf den Stapel gelegt, Stapel wird erhöht
POP .
.. ein Wert wird aus dem Stack geholt
POP x Þ x wird vom Stapel genommen, der nächste Wert liegt nun oben
y=1;
for (i=1; i<=5; i++) y=y*a; Þ y=a5 Þ y=pot(a,5);
.
.
.
k=1;
for (u=1; u<=7; u++) k=k*z; Þ k=z7
.
.
.
p=1;
for (m=1; m<=4; m++) p=p*s; Þ p=s4
Sobald eine Aktion in einem Programm mehrmals vorkommt, ist es besser stattdessen ein Unterprogramm zu benützen.
long pot (int basis, int exp)
{
int x;
long y=1;
for (x=1; x<=exp; x++) y=y*basis;
return y;
}
Übergabe von Werten:
a
12
1078
Call by Value
Call by Reference
( Call by Name )
IMMEDIATE ADDRESSING (unmittelbar) : PUSH 7 (=Call by Value)
DIRECT ADDRESSING (direkt) : PUSH M[1000] (=Call by Reference)
INDIRECT ADDRESSING (indirekt) : PUSH M[M[2000]]
M ...
Memory (Speicherstelle)
Beispiel:
int a; a Û 1078 Compiler vergibt die Plätze
int k;
e=pot (a, k); pot Û 50000
<HP>
PUSH M[1090]
1004
k wird auf den Stack gelegt
PUSH M[1078]
1005
a wird auf den Stack gelegt
e = pot(a,k)
PUSH 1008
1006
Rücksprungadresse auf Stack
JMP 50000
1007
Sprung zum UP (eigentlicher UP-Aufruf)
POP M[1094]
1008
Ergebnis (y) wird nach e geschrieben
.
.
a
12
1078
Direct Addressing
...
Immediate Addressing
k
2
1090
.
..
e
144
1094
.
.
Stack (P1)
2 / - / 144 / -
10000
Stackbeginn
(P2)
12 / -
(P3)
1008 / -
.
.
return address
1008
29999
x
30000
y
144
30002
basis
12
30004
exp
2
30006
.
.
POP M[29999]
50000
Rücksprungaddresse von Stack
POP M[30004]
50001
a (12) vom Stack nach basis
POP M[30006]
50002
k (2) vom Stack nach exp
UP pot
...
Schleife
.
..
PUSH M[30002]
50070
Ergebnis y (144) auf Stack
JMP[M[M29999]
50071
Rücksprung ins HP ( Indirect Addressing )
Static Binding ( Statisches Binden )
= Die Adressen der Unterprogramme werden beim Compilieren festgelegt
Parameter werden in den Stack geschrieben
JMP 10020
Unterprogrammaufruf
7061
Rücksprungaddresse wird in den Stack geschrieben
.
.
JMP 10020
8205
.
.
10020
UP Anfang
CALLING OVERHEAD: Das Schreiben in den Stack - benötigt viel Zeit
deshalb wird bei kleineren UP die INLINE DEFINITION (=MAKRO EXPANSION) verwendet.
Das UP wird in die Stellen geschrieben, wo eigentlich der Unterprogrammaufruf stehen sollte. Dadurch entfällt das Stacken und das Springen Þ Das Programm wird schneller, braucht aber mehr Speicher. Diese Methode wird auch für Makros verwendet.
STRUCTURES
Eine Struktur entspricht im Prinzip einer Tabelle.
Andere Namen für structure: records (in Pascal), Klassen (OOP)
Eine Structure entspricht im Prinzip einer Tabellendefinition.
Der Syntax der folgenden Code-Zeilen hält sich nicht genau an eine bestimmte Sprache.
notwendige Variablen für Schülerverwaltung: Huber_Alter
Huber_Groesse
Mayer_Alter ,...
Hier würden sehr viele Variablen benötigt werden. Außerdem leidet die Übersichtlichkeit
Gute Programmierer verwenden Structures:
typedef schueler { int a,b;
int alter; schueler huber,maier;
float groesse; huber.
alter = 17;
int edvnote; huber.edvnote = 3;
string name; } huber.name = „Huber“;
Soll eine neue Klasse für Schüler der kaufmännischen Abteilung erstellt werden, so muß nicht jede einzelne Stukturvariable oder -methode (mehr zu Methode später) der Klasse neu definiert werden. Man wendet die Vererbung (=Inheritance) an.
Structure kaschüler { schueler +
int alter; int stenonote;
float groesse;
int edvnote; Hierbei handelt es sich jedoch nur um eine
string name; Kurzschrift, um die Arbeit zu erleichtern.
int stenonote; } {In Java statt + --> „extends“)
Mehrfachvererbung (Multiple Inheritance --> Es werden die Definitionsinhalte mehrerer Klassen weiterverwendet) gibt es in keiner wichtigen Programmiersprache, außer C++.
Selective Inheritance: hierbei wird nicht alles aus der Vaterklasse weiterverwendet.
Diese Art von Vererbung existiert ebenfalls in keiner wichtigen Programmiersprache.
schueler -
float groesse;
Es ist auch möglich, den Datentyp einer oder mehrerer Strukturvariablen flexibel zu gestalten (=Generizität).
structure schueler (T) { structure schueler (T,R) {
int alter; R alter;
...
.. ....
.
T EDVNote;} T EDVNote; }
Hierbei handelt es sich ebenfalls nur um eine Kurzschrift, die dem Programmierer die Arbeit erleichtern soll. Am Maschinencode ändert sich nichts.
Jene Unterprogramme, die sich einen Schueler oder mehr erwarten, packen wir in die Structure-Definition.
z.B.
boolean ist_neg (schueler s) { schueler der_Groessere (Schueler a,Schueler b)
if (s.edvnote = 5) return (TRUE) {if (a.groesse > b.groesse) return (a)
else return (FALSE);} else return (b);}
---> In Structuredefinition packen:
structure schueler {
int alter;
...
..
ist_negativ() boolean {
if (this.edvnote = 5) return (TRUE)
else return (FALSE);}
der_Groessere schueler;}
Der Compiler würde es ohne „this“ auch verstehen. Verwendung von“this“ bewahrt Übersicht.
Steht das Unterprogramm (Werkzeug oder Methode) in der Definition, so bedeutet das, daß das erste Argument dieser bestimmte Schueler ist.
Diesen Schueler spricht man mit this an.
If this.edvnote = 5 ...
Folgende Aufrufe sind ident:
schueler y; schueler y;
if y.
ist_negativ ..... if ist_negativ (y) .
....
Vorteil der linken Lösung:
Man kann die UP-Aufrufe in der Structure-Definition durch normale Attribute ersetzen (z.B.
ist_negativ plötzlich Attribut mit Datentyp boolean). Der Compiler
würde diese Lösung trotzdem verstehen. Bei der rechten Lösung würde er den Code bei gleicher Änderung nicht mehr akzeptieren.
Unterschied zwischen OOP und prozeduraler Programmierung
OOP
class = Structure mit UP (= Methode;
in Smalltalk --> Message)
prozedurale Programmierung
class schueler {
...
boolean ist_negativ() {
if (this.edvnote = 5) return (TRUE)
else return (FALSE);}
schueler der_Groessere(schuelerb) {
if (this.groesse > b.groesse) ...
..;}
}
schueler y;
if y.ist_negativ ...
.
schueler z,x;
x = y.der_Groessere(z)
r = a.f(b,c)
h = u.p(z)
struct schueler {
..
...}
boolean ist_negativ (schueler s) {
if s.edvnote = 5 ..
. }
schueler der_Groessere (schueler a,
schueler b) {
If (a.groesse > b.groesse) ...
;}
schueler y;
if ist_negativ(y).....
schueler z,x;
x = der_Groessere(y,z)
r = f(a,b,c)
h = p(u,z)
class schueler {
int alter;
float groesse;
boolean ist_riese() {
if this.
groesse > 2.00 return(TRUE)
else return(FALSE);}
boolean ist_negativ() {
if this.edvnote = 5 ...;}
Methoden können bei der Vererbung folgendermaßen verändert werden:
class kaschueler extends schueler {
int stenonote;
redefines ist_negativ() {
if this.
edvnote = 5 or this.stenonote = 5 ....}
class schueler {
name:string;
pnote:integer;
groesse:float;
ist_riese():boolean {
if this.
groesse > 2.2 then return(TRUE)
else return(FALSE);}
istnegativ():boolean; --> wie ist_riese, nur --> if this.pnote = 5 ....
..
}
schueler stz;
stz.name = „Stanzl“;
stz.groesse = 1.81;
stz.
pnote = 2;
if (stz.ist_negativ = TRUE) .....
schueler s;
kaschueler k;
......
s:=k; --> funktioniert (k hat alles was s hat) --> Regel 1 von Strongly Typed: links darf kein
Kind von rechts stehen.
....
k:=s; --> funktioniert nicht (s hat nicht alles, was k hat)
if (k.
ist_stenogenie)... ---> war s ein technischer Schueler, gibt es hier keine stenonote
(ist_stenogenie vergleicht stenonote mit 1 und liefert true or false)
Compiler mit diesem Verhalten nennt man STRONGLY TYPED.
Regel 1 von Strongly Typed: links darf kein Kind von rechts stehen.
Regel 2 von Strongly Typed: ob Methodenanwendung zulässig ist oder nicht,
entscheidet der Compiler nach dem statischen Typ.
Den dynamischen Typ kann der Compiler nicht wissen
(arbeitet ja vor Programmablauf).
Strongly Typed-Compiler verlassen sich nur auf die statischen Typen.
STATIC TYPE: Typ mit dem Variable deklariert wurde
DYNAMIC TYPE: Typ, den Variable zur Laufzeit hat.
Bei der OOP ist der dynamische Typ das „Auge des Hurricane“.
Compiler ohne dieses Verhalten nennt man WEAKLY TYPED (z.B.
: Smalltalk)
WEAKLY TYPED:
schueler s,s2; k = kaschueler und s = schueler
kaschueler k; Dynamischer Typ
s s2 k
s s k
s:=k;
k s k
k:=s2;
k s s
s2:=s;
k k s
PROGRAMMING IN THE SMALL
1. - 4. Jahrgang (Pascal, C++ Programme)
PROGRAMMING IN THE LARGE
Wesentliche Unterschiede zu „Programming in the small“:
Rollen
Methoden
Phasen
- mehrere Mitarbeiter
- emotionale Ebene
(Sympathie)
Psychologe
- Koordination
Manager
- mehrere Funktionen
Funktions-dekomposition,
DFD,
CDUR-Matrix
- Funktionen anfangs unklar
Analytiker
Spezifikation
(Analyse)
- relationale Datenbank
Datenmodellierer
ERD,
Normalisierung
- hohe Fehlerzahl
(Fehleranz. steigt mit dem Quadrat der Codelänge)
Tester
Testphase
- wirkliche User
Dokumentation
Einschulung
- Schnittstellen
- zu anderen Systemen
Integrations-experte
Integrations-phase
- Datenmigration
(neues Prog. soll Daten vom alten Prog. übernehmen)
Migrations-experte
- graphische Oberflächen (Standards)
Maskendesigner
- Qualitätssicherung
Qualitäts-sicherung
ISO 9000
Review
IMMER
- Entwurf
Designer
Struktogramm
Design
- teuer
Finanzplaner
Controller
( Þ Qualitäts-sicherung)
- Langlebigkeit
Wartungs-experte
Kommentar
Dokumentation
Wartung
Entity View Analysis
Bsp:
int pot (int b, int e) Þ Inputparameter
{
int zwischenergebnis Þ lokale Parameter
int ergebnis
database datenbank Þ Entity Action Parameter
(auf welche Tabellen wird zugriffen)
.
..
...
return ergebnis Þ Outputparameter
}
PARAMETER
Bei der Entity View Analysis schaut man sich einen Prozeß an und betrachtet die Entities (Daten) die einwirken, d.
h. man betrachtet die Daten mit denen der Prozeß zu tun hat. (=Kontrollinstrument)Prozeß ->> Entities
Eingabe in IEF:
In IEF werden Parameter View genannt.
Bsp: CD-ROM anlegen
input view:
CDROM Inventarnummer CD1
grid list: CDROM Inventarnummer CD2
output view
...
lokale view
...
entity action view:
CDROM_Inventarnummer
CDROM_Speed
Die input views können nur Datenbankobjekte enthalten. Das Schlüsselwort gird bedeutet, daß eine Liste übergeben wird (und kein einzelner Datensatz). CD1 und CD2 sind Rollen um auf die jeweilige Inventarnummer zugreifen zu können.
Bei den entity action views kann man hinzufügen wie der Prozeß wirkt (C,D,U,R?)
Prozeßlogikdiagramme
Das Prozeßlogikdiagramm ist ein ERD mit folgenden Zusatzinformationen:
- Kennzeichung von Beziehungen:
A ... Associate (Beziehung knüpfen)
D ...
Disassioate (Beziehung löschen)
- Art, wie auf die Tabelle zugegriffen wird (C, D, U, R)
Nebenbei:
Ein C(reate) hat meistens eine A(ssociation) und ein D(eletion) ein D(isassiotion)!
Bsp: Bestellannahme
input view:
grid (Kund\Kundennummer,
Produkt\Prodkutnummer,
Bestellzeile\Menge)
??? (weitere)
output view:
Bestellnummer,
Lieferdatum,
??? (weitere)
entity action view:
Kunde
Bestellung
BZeile
Produkt
(Prozeßlogikdiagramme wurden nicht in IEF realisiert!)
Datennavigationsdiagramm
Aus dem Prozeßlogikdiagramm ist z.B. nicht ersichtlich, in welcher Reihenfolge gelesen, geschrieben, ... wird.
Das Datennavigationsdiagramm besteht aus einem (vereinfachten) ERD und einem Flowchart (Flußdiagramm).
Bsp: Bestellannahme (siehe auch vorige Seite)
(Doppelpfeil bedeutet mehrere, zB mehrere Datensätze lesen)
Das DND (Datennavigationsdiagramm) wurde in IEF nicht realisiert. Weiters zählt James Martin das DND zur Analyse (unserer Meinung nach eher zum Design, da man sich in der Analyse mit der Fragestellung „was“ und nicht mit „wie“ beschäftigt!)
Mit dem DND kann man die Datenflüsse sehr einfach darstellen.
Der Stapel (Stack)
Der Stack dient zur Variablenübergabe von einem Programm zu seinem Unterprogramm.
PUSH ..
. auf den Stapel legen ( PUSH ax ® ax auf Stapel, Stapel wird erhöht )
POP ... vom Stapel holen ( POP ax ® vom Stapel nach ax, nächster Wert oben )
y=1;
for (i=1; i<=5; i++) y=y*a; ® y=a5 ® y=pot(a, 5);
.
.
.
k=1;
for (u=1; u<=7; u++) k=k*z; ® k=z7
.
.
.
p=1;
for (m=1; m<=4; m++) p=p*s; ® p=s4
besser
long pot (int basis, int exp)
{
int x;
long y=1;
for (x=1; x<=exp; x++) y=y*basis;
return y;
}
PUSH 7 UNMITTELBAR (IMMEDIATE) addressing
PUSH M[1000] DIREKT (DIRECT)
PUSH M[M[2000]] INDIREKT (INDIRECT) M ..
. Memory (Speicherstelle)
stark vereinfachtes Beispiel:
int a; a « 1078 Compiler vergibt die Plätze
int k;
e=pot (a, k);
PUSH M[1090]
1003
k wird auf den Stack gelegt
PUSH M[1078]
1004
a wird auf den Stack gelegt
PUSH 1007
1005
Rücksprungaddresse auf Stack
JMP 50000
1006
Sprung zum UP (besser: CALL pot)
POP M[1094]
1007
y (144) vom Stack nach e
.
.
a
12
1078
...
k
2
1090
...
e
144
1094
.
.
Stack (P1)
2 / - / 144 / -
10000
Stapelbeginn
(P2)
12 / -
10001
(P3)
1007 / -
10002
.
.
return address
1007
29999
x
???
30000
y
144
30002
basis
12
30006
exp
2
30008
.
.
pot:
POP M[29999]
50000
Rücksprungaddresse von Stack
POP M[30006]
50001
a (12) vom Stack nach basis
POP M[30008]
50002
k (2) vom Stack nach exp
! Schleife
...
PUSH M[30002]
50070
y (144) auf Stack
JMP M[M[29999]]
50071
Rücksprung ins Hauptprogramm
(besser: RET ... gilt für CALL)
Beispiel Kartenspiel
Objekt: STAPEL ® WAS soll das Objekt können?
-LEGE (KARTE) DEFERRED
-NIMM (KARTE) DEFERRED
-TOP (KARTE) [oberste Karte anschauen]
-LEER (JA/NEIN) DEFERRED [ist Stapel leer?]
TOP { x = THIS.NIMM
THIS.LEGE(x)
RETURN(x) }
Eine massiv aufgeschobene Klasse heißt auch ABSTRACT DATA TYPE.
Diese werden verwendet um AXIOME zu definieren. Axiome sind Sachverhalte die zeigen wie die Methoden zusammenhängen.
Stapel , LEGE (K), NIMM, S (Stapel bleibt nach dieser Aktion gleich)
S, x = NIMM, LEGE (x), S (Stapel bleibt nach dieser Aktion gleich [entspricht TOP])
Implementierung
Class stapel_arr { extends STAPEL
PRIVATE
int a[52]
int anz
PUBLIC
redefines LEGE (KARTE)
{ a[anz] = Karte
anz = anz +1 }
redefines NIMM
{ anz = anz -1
RETURN a[anz] }
redifines LEER
{ if anz = 0 ....
}
}
Es ist nötig zu verbieten, daß man in den Stapel hineinschreibt - dies sollte nur durch das verwenden der Methoden geschehen. Darum gibt es die einschränkungen PUBLIC, PRIVATEund PROTECTED.
Bei Private dürfen alle Methoden Attribute verändern, bei Protected nur Methoden der Vater- und Kinderklassen.
Im Prinzip legt man eine Kapsel an, die kleine Löcher hat (die Methoden), durch die man auf die Daten zugreifen kann.
Diese Taktik wird DATA ENCAPSULATION (DATENKAPSELUNG) genannt.
Radikale Taktik: Jedes Attribut wird PRIVATE, auch solche die verändert werden dürfen.
So ist man gezwungen für jede Variable eine SET und eine GET Routine zu schreiben. So ist es aber einfacher die eingaben zu kontrollieren.
Klassenfindung
Es gibt keine optimalen Klassenbäume.
Ansatz zur Klassenfindung: Was man angreifen kann ist ein Objekt.
Alles auf das man Methoden anwenden kann ist ein Objekt.
Weiters ist es möglich MIXIN-Klassen zu definieren, die nur erschaffen werden weil sich andere Klassen gut davon ableiten lassen, die selber in der Realität nicht vorkommen.
Als Hilfsmittel um zu ermitteln welche Klassen man von welchen Ableitet dient das Attributsdiagramm.
KÜ
Steno
Rollstuhl
TA_BEH
X
X
TA
X
KA_BEH
X
X
KA
X
Bsp.:
Klassa A: X X X X X X
Klasse B: X X X X
Hier ist es ratsam Klasse B von Klasse A abzuleiten.
Methodenfindung
1. Nicht direkt auf Attribute zugreifen. (Get & Set Methoden)
2.
Nicht lesen & schreiben in einer Methode ( man weiß sonst nicht was das UP im Hintergrund macht )
Aufwandschätzung
® A.Albrecht (IBM) ® Function Point Methode
(= Verfahren zur Schätzung derbenötigte Arbeitszeit)
PROBLEM:
es fehlen viele Daten
Erfahrung
Anforderungscheckliste (Anforderungen, die immer wieder auftreten!)
Funktionsdekomposition
Jede Funktion wird mittels Punktesystem (0,2,3,6 Punkte) bewertet. Je komplizierter desto mehr Punkte.
3 Arten von Funktionen: INPUT, OUTPUT, DB-ABFRAGEN
Die Qwerte werden addiert, Endwert wird mit Faktor (meist 0,7) multipliziert, dann wird die Systemcheckliste zu Rate gezogen:
Anforderungscheckliste (0...
5 Punkte)
Schnittstelle zu anderen Systemen
Performanceanforderung z.B:. schnell, Echzeitsysteme
! gibt Altdaten, die verwendet werden müssen
mehrere User (Verteiltheit)
einfache oder komplizierte Benutzerführung
schwierige Prozeßlogik (Algorithmen)
! Wiederverwendbarkeit von Modulen
Þ gewichtete Teilnahme von den Funktionskomposition und Anforderungscheckliste = Function Points ® Tabelle ® entspricht Mannmonatszahl
doppelt so langes Programm 4x
solange Zeit (exponentiell!)
Problem
Softwareentwicklung fortgeschritten
Algorithmen werden nicht einbezogen
gewichtete Summe problematisch
(0,1 * Systembewertung ® ?)
Qualifiziertheit wird nicht einbezogen
viele Tätigkeiten vergessen :
Qualitätssicherung
Projektmanagement
Dokumentation
- Case Tools ® unterstützen dies nicht!
Softwarequalitätssicherung
Kriterien für gute Software
Zuverlässigkeit (Reliability)
Performance
Benutzerfreundlich (User Friendliness)
Korrektheit (Correctiness) bezüglich der Analyse / Spezifikation
Robustheit (Robustness) ® ist es außerhalb der Spezifikation stabil ?
Erweiterbarkeit / Wertbarkeit (Maintainability)
Portabilität (Portability)
Kompatibilität (Compatibility) (z.B:. Schnittstellen)
Job: (!) Hält sich das Unternehmen an die selbstauferlegten Standards ?
formale Regeln !
z.B:.
IVAN ® wird der Logic-Standard eingehalten, nicht ob die CDROM richtig verwaltet wird.
® keine Spezialisten (gesunder Hausverstand) ® Taktgefühl, menschliches Gespür
z.B:. keine Korrekturen in der Schrift (z.B:. grün)
Standards beim IVAN (geregeltes Vorgehen):
Programmierrichtlinien
Datenbankrechtlinie
Arbeitszeiterfassung
Mängelverwaltung
Logic-Standard
Darstellungsdomänen
Zusatzfragen
Codeinspektion (Code Inspection) ® Code wird auf Folie ausgedruckt ® Präsentation (beim Präsentieren werden Fehler gefunden) Þ Korrektlast.
Review (Audit: Überprüfung ob Standards eingehalten werden).
Walkthrough Þ Rollenspiel mit Sourcecode ® Durchspielen des Programmcodes mit verteilte Rollen (z.B:. UP) Þ Korrektheit.
Peer Rating
® Stilnote (gute Dokumentation, leicht lesbar, effizient, ..
.)
® jeder erhält Ausdruck eines Programmcodes ® Bewertung durch andere ® Æ Note.
JAVA
(Weiterentwicklung von C++ ; C --> C++ --> JAVA)
- keine Mehrfachvererbung
- keine friends
- kein virtual (denn alles ist virtual)
- garbage collection (automatisch; destructoren haben kleinere Rolle)
- Klasse:
- Attribute
- Methoden
- Fehler (exception) --> catch (muß beim Aufruf sein) --> sonst kompilierbar
class auto extends fahrzeug
{
private float speed;
private boolean motor;
public void beschl
{
speed=speed+10.0
}
public auto
{
speed=0.0
}
Information Engineering
Strategien der Systementwicklung
Software Engineering
Probleme: In großen Unternehmen hat jede Abteilung ihre eigene Datenbank --> selben Daten werden mehrmals genutzt.
Objektorientierte Systementwicklung
Information Engineering
James Martin (Software-Entwickler):
IEF
PLANUNG (Unternehmen analysieren)
ANALYSE (Problem verstehen) -->WAS soll das System tun?
ENTWURF (Lösungen suchen) -->WIE soll es das tun?
PROGRAMMIERUNG
IEF - CASE TOOL (Computer Aided Software Engineering)
IEF ist ein Information Engineering Tool.
Nach dem Entwurf kann das Programm generiert werden.
Entwicklung der Programmiersprachen:
ASSEMBLER
FORTRAN (Hochsprache)
CASE TOOL (graphisch)
Planning (Planung)
Diese Phase sollte maximal 6 Monate dauern und nicht mehr als 4 Mitarbeiter in Anspruch nehmen.
grobes ERD
z.B.: Firma Shell
Grobe Funktionsdekomposition
Organigramm
Stellen (Organisational Unit)
Unternehmensziele -CFS
CSF (Critical Sucess Faktor)
Gemessene kritische Faktoren, die für die Unternehmensziehle gebraucht werden.
Information Needs
Welche Informationen werden wirklich gebraucht?
Man kann fast alle Faktoren in Beziehung setzen um Inkonsistenzen aufzudecken.
Stelle
R
A
Ziele
A
X
X
E
N
R .... Responsibility
A ..
.. Authority
E ....
Expertise
W .... Work
Wenn weder S2 oder S3 mit Z2 ode Z3 in Beziehung steht ist nicht klar, warum S1 mit Z1 in Beziehung steht.
Papierflüsse sollen nicht in Datenflüsse umgewandelt werden.
Die Unternehmensstruktur hat sich nach dem Programm zu richten und nicht umgekehrt.
Entwurf (Design)
Information Engineering - Programme (z.B. IEF) können noch keine Masken erstellen. Die Masken müssen daher vom Entwickler erstellt werden. Formulare, die Eventhandler enthalten, nennt man „Procedure Step“ oder Dialog.
Man kann mehrere Prozesse in einem Dialog zusammenfassen (Anlegen, Löschen, Ändern). Es können aber auch Prozesse auf mehrere Masken aufgeteilt werden, z.B. aus Platzgründen am Bildschirm.
Action Diagramm
= eine Art Strukogramm, nur anders aufgezeichnet.
Struktogramm
Action Diagram
Beschreibung
Anweisungen
Schleife
Verzweigung (If - Klausel)
Verzweigung (CASE - Anweisung)
nächster Schleifendurchlauf Schleife verlassen
gleichzeitige Anweisungen
(für Parallelrechner)
Bsp: Bestellungen
Der Vorteil eines Quer-Checks beim Case-Tool ist, dass überprüft wird, dass das Programm zur DB und zum DFD paßt.
Dialogflußdiagramm
Hier werden die möglichen Pfade durch die Dialoge festgelegt. Dazu verwendet IEF zwei Arten von Verbindungen:
Link Flow (Wechsel in beide Richtungen möglich: "flows on" / "returns on")
Transfer Flow (Wechsel nur in eine Richtung möglich: "flows on"-Event)
Modularisierung
P1: 3 Zahlen (Input)
Dreieck ist rechtwinkelig (3,4,5) (Output)
Dreieck ist gleichschenkelig (3,5,5) (Output)
Dreieck ist allgemein (3,5,6) (Output)
P2: 3 Zahlen (Input) -> wie P1
Dreieck rechtwinkelig und/oder gleichschenkelig (Output)
P3: -> wie P1, aber Input 3 Eckpunkte
P4: -> wie P3, aber im Raum ( 3 Koordinaten)
Nicht 4 einzelne Programme schreiben, sondern Unterprogramme (UP) machen
Falsch : Eingabeschleife für xyz _
if x²+y²=z² then output („rechtwinkelig“) \
elseif x =y then output („gleichschenkelig“) =====à Unterprogramm UP1 machen
else output („allgemein“) _/
.
.
Richtig: is_rw (abc) -> true/false UP2
is_gs (abc) -> true/false UP3
is_rwgs (abc) {
if ((is_rw (abc)) and (is_gs(abc))) return (true) }
UP5: float dist (x1,y1,x2,y2) { ß gleich eine dritte Koordinate hinzufügen für P4
return (sqrt (x1-x2) (x1-x2) + (y1-y2) (y1-y2))
->Lösung durch UP- Aufruf
-> ausrechnen der Distanzen -> Aufruf von UP1 -> UP1 ruft wiederum UP2/UP3/UP4 auf -> Lösung
Immer wenn man merkt, daß eine Lösung öfters gebraucht wird sollte man Unterprogramme schreiben.
Strukturdiagramm (Structure Chart)
is_rwgs UP 3 Seiten
3 Seiten
T/F
is_rw is_gs
( muß kein Baum sein, da sich UP gegenseitig aufrufen können)
· à Echtdaten werden übergeben
° à Steuerdaten werden übergeben
Echtdaten : Daten, die etwas aus dem wirklichen Leben übergeben (Größe,Gewicht)
Steuerdaten : Daten, die ein (meist Prüfungs)ergebnis darstellen TRUE / FALSE oder eine Aktion auslösen sollen (Read/Write).
Funktionsdiagramm : Zerlegung des Problems
Strukturdiagramm : Zerlegung des Programms
Wann ist ein Unterprogramm sinnvoll: - Wiederverwendbarkeit
- Übersichtlichkeit
- wenig Datenaustausch
KOHÄSION (Cohesion)
Funktional Kohäsiv
jedes Unterprogramm sollte mit einem deutschen Satz (ohne UND) beschrieben werden können
z.
B.: Diese Unterprogramm erkennt RW-Dreiecke. (++++)
Sequentiell Kohäsiv
ein Unterprogramm erledigt 2 Jobs -> werden in ein UP gepackt weil sie unmittelbar hintereinander durchgeführt werden sollen ( -> UND !) (z.B. dieses Programm zerlegt einen Text in einzelne Worte und überprüft anschließend, welches am häufigsten vorkommt. Besser wären zwei Unterprogramme gewesen: Eines zum Zerlegen von Texten und eines, das aus einer Wortliste das häufigste ermittelt.
) ( -)
Zeitlich Kohäsiv
2 Jobs werden in ein P gesteckt , weil sie zeitlich gleichzeitig ausgeführt werden müssen
z.B.: Files öffnen & Menu anzeigen. (-)
Logisch Kohäsiv
Das UP bekommt echte Daten + Steuerflag, was zu tun ist -> besser der Aufrufer entscheidet was zu tun ist. Beispiel: Unterprogramm das eine Datensatznummer erwartet und anhand eines ebenfalls übergebenen Flags entscheidet, ob es ihn anzeigen oder löschen soll. (-)
Kommunikativ Kohäsiv
wenn 2 UP die selben Inputwerte übergebenbekommen, aber der Output verschieden ist.
Beispiel: Ein Unterprogramm zum Überprüfen, ob jemand innerhalb Wiens wohnt und ein Unterprogramm zum Versenden von Emails sollten nicht in eines gepackt werden, nur weil sie beide eine Adresse als Inputparameter erwarten. (-)
Prozeduale Kohäsion
2 Jobs die nichts miteinander zu tun haben, werden weil sie die gleiche strukturelle Abfolgen haben in ein UP gesteckt. z.B.: beidesmal von 1 bis 100 zählen. (Beispiel: ein Unterprogramm, das ein Array von 100 Namen auf syntaktische Korrektheit testet und ein zweites, das 100 Zahlen in eine Hashtabelle schreibt sollten nicht in eines verpackt werden, nur weil sie beide eine 100-er Schleife benützen.
) (--)
Zufallskohäsion
Jobs zu einen UP verbinden, die überhaupt nicht miteinander zu tun haben
z.B.: Inventarnummer vergeben + Schüler löschen (---)
Kopplung = Coupling
Es geht um die Daten die zwischen den Unterprogrammen fließen.
Datenkopplung (Data Coupling) geht nur dann gut, wenn wenig Daten übergeben werden.
Pointer + es wird „wenig“ übergeben, da ein Pointer nur ein String ist
- es wird damit aber zB.: das ganze Recordset übergeben
- geht nicht wenn UP auf verschiedenen Rechnern laufen
Wenn Daten übergeben werden, sollte nach Möglichkeit ein Pointer übergeben werden.
zur Erinnerung: call by value => Echtdaten werden übergeben
call by reference => Pointer wird übergeben
Globale Kopplung = Global Coupling
!! ist sehr schlecht = unbedingt vermeiden !!
Es ist schwer zu debuggen, da man nicht weiß, wer wo was hinschreibt. Außerdem muß man, wenn man die Struktur einer Variablen ändert, 15 Programmierer verständigen.
Bei IVAN ist die größte Variable die Datenbank selbst, da jeder darauf zugreifen und sie löschen und speichern kann.
Inhaltskopplung = Content Coupling
Man spricht von Inhaltskopplung, wenn ein UP den Code eines anderen UP´s ändert.
Gestaltung von Benutzeroberflächen
Oberste Regel: Der Benutzer ist dümmer als man denkt. Er macht alles falsch, was er nur falsch machen kann!!!
Farben
augenfreundlich
pro Seite nicht mehr als zwei Farben
große Flächen in dezenten Farben => kleine können grell sein, aber nicht mehr als zwei verschieden Farben verwenden.
Layout
Wenn von Papier auf EDV umgestellt wird, darauf achten, daß die Eingabemaske dem Papiervorgänger ähnlich sieht, da die EDV dann eher angenommen wird.
Formulare sollten einander ähnlich im Aufbau sein (Style Guide).
Entfernung des Benutzers vom Bildschirm muß beachtet werden => dementsprechende Schriftgröße (Benutzer rennt hin und her => große Schrift => wenig auf einer Maske)
Zusammengehöriges zusammen (Vor- und Nachname)
am Kulturkreis des Benutzers orientieren (Arabien => schreiben von rechts nach links)
zwischen Lesefeldern, Lese-Kann-Schreibfeldern, Lese-Muß-Schreibfeldern unterscheiden. Wenn dies von der Anwendung abhängig ist, zur Laufzeit ändern.
Die richtigen Steuerelemente wählen:
neue Einträge neue Einträge neue Einträge
möglich müssen prog. müssen programmiert werden
mittlere Lösung ist am Besten (wenn aber zB.
: steuerpflichtig dazukommt, ist die letzte Lösung am Besten, da mann alles extra ankreuzen kann)
Beim Verlassen keine Datenbankabfragen (Datenbankaktionen) mehr starten; zB.: Datumsüberprüfung auf OK-Button verlegen und nicht beim Schließen
Felder mit links-rechts-Auslegung nicht untereinander
Felder nicht eingegeben werden können, inaktiv setzen.
Statuszeilentext ist wünschenswert (Suchmodus, Lesemodus, Änderungsmodus, ...)
selbstsprechende Fehlermeldungen (nicht: Falsche Eingabe, sondern Warum)
bei riskanten Sachen: Rückfragen (zB.
: Löschen)
Hot-Keys von Vorteil, da Profis kaum die Maus benützen
Eingabe am Benutzer orientieren
Die älteren Herrschaften können oft keine Mäuse benutzen
Kinder können mit der Maus besser als mit der Tastatur umgehen
bei Behinderten: wie können diese Eingeben
bei Börsenmaklern: keine piepsende Stimme
gleiches gleich benennen: Nach- + Zuname = falsch
Schriften wie Farben
Rapid Prototyping
Als erstes einen Prototyp - bei dem noch nichts funktioniert - an den Kunden, damit dieser die Oberfläche sehen kann, und sich mit ihr anfreundet. Dies sollte ein paar Tage nach der Erstellung des Pflichtenheftes geschehen.
Kunde kann dann bevor die Programmierung beginnt, sagen ob er mehr oder weniger Steuerelemente, andere Farben, ... haben will.
Der Vorteil darin ist, daß es beim Endtermin zB.: 3-4 Jahre später kein böses Erwachen gibt.
es handelt sich um einen Teil der Spezifikation
Projektplanung (Softwareprojektplanung)
vor der Spezifikationsphase
es muß entschieden ewrden, ob: Case Tool, ö
Prototyping, ý ja/nein
Objektorientiert, ø
welche Phasen wie lange,
...
Als erstes müssen die ZIELE festgelegt werden => daraus ergeben sich dann die Aufgaben, die wiederum in Teilgebiete unterteilt werden müssen.
Für den Projektleiter ist wichtig: WIEVIEL wird es kosten,
WIELANGE wird es dauern,
WER macht WAS?
Es gibt verschieden Methoden, die Kosten eines Projektes abzuschätzen. Die Funktion-Point-Methode dient nur der Abschätzung der Programmierkosten.
Um alle Aufwände, und vor allem die Dauer, zu ermitteln, dient die BREITBAND DELPHI METHODE:
Verschieden Experten setzen sich zusammen und reden über das Projekt, dann tragen sie geheim (jeder für sich) auf einer Linie die von ihnen geschätzten Mann-Monate ein.
Wenn alle Zettel abgegeben worden sind, werden alle Ergebnisse auf einem Diagramm zusammengefaßt, die Experten wissen jetzt was die anderen meinen, aber nicht von wem welche Abschätzung stammt.
20 30 50 55
Das ganze beginnt jetzt von vorne nochmals, bis man zu einem gemeinsamen Ergebnis kommt.
Der Vorteil dieser Methode liegt darin, daß nicht ein Mittelwert, sondern ein Wert der allgemeinen Zustimmung genommen wird, und meist sehr gute Ergebnisse erzielt werden.
Kleine Fehler können aber zu großen Verzögerungen führen.
Hierzu ist noch zu sagen, daß die Arbeitsumgebung wesentlichen Einfluß auf das Projekt hat. Kleinere Räume mit viel Tageslicht und Pflanzen erhöhen den Eifer. Personen die nicht „miteinander können“, nie in einen Raum setzten, da sie nie zu einem gegenseitigen „Mutmachen“, sondern eher zum Miesmachen neigen.
Die Spezifikation
Funktionen (beschreiben)
Einschränkungen (meist zeitlich) - Performance
Enviroment (Umgebung)
nicht sollte drinnen stehen:
l Platitüde (Leersatz- Sätze, die nichts aussagen)
z.B: System sollte benutzerfreundlich sein;
z.
B: System sollte schnell sein.
l Mehrdeutigkeiten (Ambiguity)
z.B: „Ausgeben“ - Drucker oder am Bildschirm angezeigt.
z.B: „Meistens“, „oft“, „im Normalfall“, „in Ausnahmefällen“
l Auslastungen (Omission)
Wichtige Fälle, die eintreten können, müssen auch behandelt werden.
z.
B: Reaktion auf Fehlereingaben &- eingabeformat.
l Implemention Directive
Welche Programmiersprache verwendet wird, sollte so ausverhandelt werden, daß man selbst die Sprache bestimmen kann.
l Benutzersprache
Spezifikation soll so formuliert werden, daß der Kunde auch versteht worum es geht.
Testen
Die besten Programmierer sollten Testen
Teste nie dein eigenes Programm
Typische Fehler
l OFF- ONE ERROR
Schleife die 30x durchlaufen werden soll, aber nur 29x durchlaufen wird
l DANGLING POINTER
int *p; // p enthält also die Adresse eines Integerobjektes
*p = 34; // In diese Adresse wird die Zahl 34 hineingeschrieben. Da aber nie angegeben wurde, um welche Adresse es sich eigentlich handelt, wird irgendetwas im Speicher mit 34 überschrieben.
l DIVISION DURCH 0
l FALSCHER UP- AUFRUF
Parameter werden falsch übergeben.
Beispiel: int potenzieren(int basis, int exponent)
Programmierer will 3 hoch 4 ausrechnen, ruft aber potenzieren(4,3) auf.
l WERTEBEREICHSVERLETZUNG
Beispiel: int x;
x=3.142;
3.142 ist kein Integer (keine ganze Zahl)
l IN FILES SCHREIBEN, DIE GAR NICHT GEÖFFNET WERDEN.
Testarten
Blackboxtests
Der Tester betrachtet das Programm als Blackbox ( -> Code ist uninteressant). Es wird überprüft, ob Spezifikation erfüllt wird.
Bsp.:
A ê B ê C ê
ê Rechteck
ê Allgemein
ê Gleichseitig
Whitebox
Der Tester betrachtet den Programmcode.
Test wird so aufgebaut, daß möglichst viele Programmteile getestet werden.
Bsp.:
A ê B ê C ê if (a<0)
if (b>5)
..
.
ê Rechteck
Strategie (keine ähnlichen Testfälle sind zu verwenden !)
3, 6, 7
3, 7, 8
è Äquivalenzkritärien
Seeding
Es werden z.B: 200 Fehler bewußt eingebaut
è Dann wird getestet.
è Es werden z.B: 100 Fehler gefunden die in den bewußt eingebauten sind
è dadurch kann man auf die verbleibenden Fehler schließen
Zwei Tester
Zwei Tester testen ein und dasselbe Programm. Je mehr sich die Fehler, die gefunden werden überschneiden, desto weniger Fehler sind noch vorhanden, wenn die nicht überschneidenden Fehler einen geringeren Anteil ausmachen.
Konstruktor/Destruktor
Dynamische Speicherverwaltung
= Platzreservierung, wenn das Programm läuft
in C: malloc (memory allocation / Speicher-Zuteilung)
x = malloc (2) während der Laufzeit werden 2 Byte an Speicher reserviert
*x = 50 ;
class knoten {
int z; while ( ... )
knoten *next; {
constructor knoten ® wird bei new ausgeführt .
{ .
this.
next=NULL .
this.zahl=-1 p=new knoten
} p.zahl=z
} ...
delete p
Kurzsymbol für destructor knoten ® ~ knoten
Wenn eine Methode genauso wie die Klasse heißt, so ist sie ein Konstruktor
® constructor kann weggelassen werden (C++, JAVA)
best fit (beste):
sucht nach dem optimalsten Speicherplatz, es können jedoch kleine Speicherreste übrigbleiben, die unbenutzt bleiben (z.B. bei 30 Byte wird ein 32 Byte-Block benutzt)
worst fit (schlechteste):
Zugriff auf den größten Speicherblock, nimmt dadurch anderen Programmen, die den Speicher benötigen, den Platz weg (z.B. bei 30 Byte werden 1000 Byte angeschnitten)
first fit (erste):
greift auf den 1. freien Speicher zu, egal wie groß der Block ist, sofern er größer als der geforderte Platzbedarf ist (z.
B. bei 30 Byte 60 o. 100 Byte)
Analyse
G R O B E R D
G
Kunde
Produktion
Abteil
R
Einkauf
X
O
Verkauf
X
X
B
Produktion
X
-
Marketing
X
F
D
Welche Funktion benützt welche Entity Type ?
· Kanonische Synthese (Verfahren um Datenmodell zu erhalten)
· Fein-Funktionsdekomposition
· Prozeßabhängigkeitsdiagramm (Process Dependency Diagramm):
=> erweitertes Funktionsdiagramm
Prozeß: hat einen definierten Anfang und Ende (z.B.: Schüler anlegen)
Funktion: z.B.
: Schülerverwaltung
Elementarprozeß: Prozeß, der sich nicht mehr weiter zerlegen läßt.
P1 P2 P2 darf erst ablaufen, wenn P1 fertig ist
P1
P2
· CDUR
· DFD (Prozeßdatenseite)
· Entity Cycle Analysis: welches Entity begegnet welchen Funktionen?
· Entity View Analysis: welcher Prozeß begegnet welchen Daten ?
Kanonische Synthese
1.) Datenelemente suchen. (alles, was man speichern will) =>Attribute
z.B.: CD-Rom Typ InvNr.
Floppybez.
Blase
Ist dies fertig, so erhält man ein Bubble-Chart.
Man erkennt, was legt was fest.
InvNr . CD-Rom
Land Feiertage
Lieferant
intersection data0 (assoziative Beziehung)
L + P Preis
Produkt
transitive Abhängigkeit ist überflüssig
Patient
Spital
Bett
Bsp.: X Tab.
: Z X Y
Z
Y
X Y Tab.: X Y
Z Tab.: X Y
X Y Y Z
Entity Life Cycle Analysis
Bsp.: Mängelverwaltung
Prozesse
P3 auszubessern
offen
P2 P1 testen behoben
unberechtigt
Andere Beispiele sind z.B.: Betriebssytem, Büchereibibliothek
Man betrachtet ein Objekt an und schaut welche Prozesse eine Zustandsänderung hervorrufen (Kontrolle, ob wirklich alle Prozesse realisiert werden)
Affinität
a(E) = Anzahl der Funktionen, die das Entity Type benützen
z.
B.: a(Produkt) = 3
a(Kunde) = 1
a(Abteilung) = 2
a(E1/E2) = Anzahl der Ergebnisse, die beide benutzen
z.B.: a(Kunde,Produkt)=0
a(Produkt,Abteilung)=2
Regel: 2 Elemente,die eine große Affinität zueinander haben => in ein Projekt
a(E1 nach E2) = a(E1,E2)/a(E1) Bereich ist von 0-1
Jede Funktion, die E1 braucht, benötigt auch E2. Dies ist ein Maß ab 2 Entities ,die in ein Projekt gehören.
z.
B.: 0,7: 70% überdecken sich; 30 überdecken sich nicht.
IEF => alle Affinitäten: E1 nach E4 0,92 E1 & E2 verschmolzen zu E14 = neues Objekt
E2 nach E4 0,89
E4 nach E2 0,81
Die Affinitätsanalyse ist ein Schritt von der Planung zur Analysephase.
Suchen (Searching)
Das Suchen verkörpert die meistbenutzte Operation neben dem Anlegen. Sogar das Löschen ist eine Erweiterung des Suchens, denn bevor etwas gelöscht werden kann, muß es erst einmal gefunden werden. Zur Erklärung der Punkte Sequentielles und Binäres Suchen sei als Beispiel die Sozielversicherungsnummer angeführt.
Sie hat insgesamt 12 Stellen. Die ersten 4 sind ein Code, die nachfolgenden 6 das Geburtsdatum im Format <TT:MM:JJ>
Wir unterscheiden Arrays (sortiert, unsortiert) und Bäume.
Das Suchen in Arrays
Das Sequentielle Suchen
Bei diesem Suchverfahren wird jedes Feld des Arrays nacheinander durchgelaufen, bis das entsprechende Feld gefunden ist. Im Durchschnitt benötigt man dafür N/2 Operationen.
Best Case: das Erste Feld entspricht der gesuchten Sozialversicherungsnummer.
Worst Case: Das n-te Feld entspricht der gesuchten Sozialversicherungsnummer.
Eine neues Feld wird am Ende des Arrays angefügt (n+1).
3502 120456
n Felder
7113 031291
Für den hohen Durchschnitt der benötigten Operationen, die man bis zum Finden der gesuchten Sozialversicherungsnummer braucht (8 Mio Felder), ist das Sequentielles Suchen nicht gerade zweckführend. Eine andere Möglichkeit des Suchens ist
Das Binäre Suchen
Bei unserem zweiten Versuch ist ein sortiertes Array vorliegend, d.h. die Felder sind aufsteigend sortiert. Man nennt das auch ein sortiertes Array.
Neue Felder werden am Ende der Liste angefügt, unabhängig davon, ob es sich um eine Neugeburt oder um einen Zuwanderer handelt. Siehe auch Kapitel Indexreorganisation.
Funktion: Beim Binären Suchen wird die Anzahl der Felder immer weiter halbiert. Dadurch gelangt man viel schneller zum gesuchten Feld gegenüber dem Sequentiellen Suchen, da sich die Menge der zu suchenen Felder systematisch verkleinert. Bei 8 Mio. Felder entspricht das 23 Suchschritten.
3502 120456
7113 031291
4 Mio
immer weiter halbieren
n-1 -tes Feld
n-tes Feld
Frage: Wie oft kann man n Felder halbieren? -> ld n
2^x = 8 Mio
x = ld 8 Mio
x » 23
Average Case entspricht ungefähr dem Worst Case beim Binären Suchen (=2^x).
Indexreorganisation
Beim Binären Suchen ist das Einfügen teurer als bei der Sequentiellen Sortierung, da die Reihenfolge erhalten werden muß.
Angenommen im Laufe eines Tages werden zu den 8 Mio. Feldern 30 neue hinzugefügt, so dauert die Suche der zuletzt angefügten Felder am Längsten. Das kommt daher, da zwar die ersten 8 Mio. Felder binär in 23 Schritten durchlaufen, die neu angefügten 30 Felder aber sequentiell im Worst Case bis zu 30 Mal zusätzlich abgeklappert werden.
Indexreorganisation wird meistens über Nacht oder zu Zeiten geringer Abfragen durchgeführt.
Gestaltung einer Baumstruktur aufgrund einer Reihenfolge
Bäume
(15,8,12,21,30,14,16)
15
8
21
12
30
14
Knoten und Tiefen
Knoten
1
3
7
Tiefe
0
1
2
Baum
b.B.
b.B.
balancierter Baum
Anmerkung:
balancierter Baum: kurzes Suchen
unbalancierter Baum: langes Suchen
(bei vorsortierten Daten)
2^(T+1) = K+1
T-1 = ld (K+1) -1
T= ld (K+1)-1
AVL Baum
Erfunden von drei russischen Mathematikern (AVL steht für die drei Anfangsbuchstaben der Nachnamen der Mathematiker).
Ein AVL Baum ist ein Baum, bei dem jeder einzelne Knoten eine Tiefendifferenz von ±1 hat.
Degenerierter Baum
Bei einem Degenerierten Baum ist die Struktur vollig unbalanciert. Jeder Knoten hat nur rechte bzw. linke Nachfoger.
Beispiel: das Wort W-U-R-M-L-I-E-D ist degeneriert.
Aber auch: S-O-N-N-I-GW
S
U
O
R
N
M
N
L
I
I
G
E
D
Baum
Beim 2-3-4 Baum hat man nmax 3 Zahlen, die daraus folgend in maximal 4 Einteilungen unterteilt werden können.
8 13 70
>= 70
<= 8
14-70
9-13
Lazy Deletion
Ausgehend von der Grundlage, kleinere Kinder eines Knotens werden linke, größere jeweils rechts angeornet, ergibt sich folgendes Verfahren zum füllen der Lücke, an der ein Knoten gelöscht wurde. An Stelle des gelöschten Knotens können nur die Schwarz markierten Knoten stehen.
DELETE
HASHING
Operatoren beim Suchen:
-MINMAX
-MERGE (verschmelzen)
Beim Hashing gibt es nicht eine große, sondern viele kleine Suchstrukturen. Ein Beispiel wäre 26 (26 Buchstaben im Alphabet) Schülertabellen anzulegen.
Allgemein: Bevor man eine Strukur entwickelt entschließt man sich für eine der folgenden Operationsgruppen:
nur Hinzufügen & Löschen
oder MINMAX & Löschen
andere Ansätze:
h1 erster Buchstabe
h2 letzter Buchstabe
h3 länge des Namens
Ziel des Hashings ist es, gleichmäßige Hashfunktionen zu finden.
Einzelstruktur = Bucket (engl.
Kübel)
Hashfunktion h(Pk... Primary key)
Mittels eines Algorithmuses wird bestimmt, wo das Objekt eingeordnet wird. Der Algorithmus muß so aufgebaut sein, das die Verteilung gleichmäßig erfolgt. Der ASCII- Zeichensatz ist dabei ein erster Ansatz.
Das Wort <R-O-T> besteht aus den drei unterschiedlichen Zeichencodes 200, 170 und 150. Man summiert die drei Codes, dividiert durch die Anzahl der Buchstaben im Alphabet (26!) und erhält einen Rest (modulo).
Das Verfahren ist aber nur dann optimal, wenn es mit 10 Datensätzen pro Bucket gefahren wird. Die Suche innerhalb des Buckets ist ein Array oder einfach eine verkettet Liste (Separate Chaining).
Verkettete Liste
Linear Probing
Bei der Methode des Linear Probing verwenden wir pro Bucket einen Datensatz..
.
.
h1 (Österreicher 3)
14730
h1 (Österreicher 1)
.
.
.
Was geschieht aber, wenn durch das Linear Probing ein Österreicher in ein Feld geschoben werden mußm daß schon besetzt ist? Die Lösung sind verschiedene Schrittweiten z.
B. 2 Funktionen, auch genannt Double Hashing (gleichmäßigere Vererbung). Die Vorraussetzung für dieses Verfahren ist, daß es mehr Buckets als Datensätze geben muß.
Indirektes Suchen (Indirect Search)
(vgl. Buchindex am Ende eines Buches = Sortierte Datenstruktur mit einem Pointer auf Seiten)INDEX
PAUER 2020
SCHELLNER 2060
PAUER
5602
Adr ..
.
2020
3080
4205
SCHELLNER
5602
Adr ...
2060
3113
5602
3060
3040
XXX
..
.
...
2814
INDEX= Für jedes Suchkriterium ein eigener Hilfsbaum (für schnelle Rückantwort)
für langsame Rückantwort Þ sequentiell
Statt dem Baum kann man auch eine geordnete Liste erstellen.
Sortieralgorithmen
Parameter der Leistungsfähigkeit
Laufzeit: ist die Zeit, die ein Algorithmus dazu benötigt eine Anzahl von n Elementen zu sortieren.
Stabilität: Ein Sortierverfahren wird stabil genannt, wenn es die Reihenfolge gleicher Schlüssel in der Datei beibehält, z.B. eine Menge von Schülern wird nach Noten (Schlüssel) sortiert. Bei einer stabilen Methode sind die Schüler noch immer in alphabetischer Reihenfolge in der Liste angeführt; bei einer instabilen ist von einer alphabetischen Reihenfolge keine Rede mehr.
Insertion Sort
Eine unsortierte bestehende Liste wird systematisch vom Anfang weg sortiert, indem die nächstkleinere Zahl links, die nächstgrößere Zahl re
| Anmerkungen: |
| impressum | datenschutz
© Copyright Artikelpedia.com
