Vergleich zwischen OOP und prozedualer Programmier

1 Software life Cycle (Wasserfallmodell)


Phase Produkt der Phase
Analyse (Probleme finden, Was soll das System tun?)
Spezifikation
Design (Wie soll das System das tun?)
Programmiervorlage
Programmierung, Realisierung
Programm
Test
Testberichte, Mängel ⇒ besseres Programm
Wartung

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

Planningphase
unternehmensweites Betrachten des Problems

Vergleich:
Information Engineering Städteplaner
Software Engineering Architekt
Programmierer Maurer

2 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

3 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, muss für den Prozeß ein eigens DFD erstellt werden.
Die Aufteilung der Diagramme muss konsistent sein, d.h. die Funktion im Unterdiagramm muss genau so viele Zu - und Abflüsse haben, wie das übergeordnete Diagramm.

3.1 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.

4 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

5 Objektorientierte Programmierung

5.1 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





















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 )




















5.1.1 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.

6 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 muss 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, dass 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


7 PROGRAMMING IN THE SMALL

1. - 4. Jahrgang (Pascal, C++ Programme)

8 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








9 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, dass 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?)

10 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!)

11 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.

12 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)

13 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])


13.1 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, dass 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.

14 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.



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.

15 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 )

16 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:

16.1 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!)

16.2 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

!17 Softwarequalitätssicherung

17.1 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

17.2 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.

18 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 (muss 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
}


19 Information Engineering


19.1 Strategien der Systementwicklung




19.1.1 Software Engineering







Probleme: In großen Unternehmen hat jede Abteilung ihre eigene Datenbank - - > selben Daten werden mehrmals genutzt.

19.1.2 Objektorientierte Systementwicklung






19.1.3 Information Engineering






James Martin (Software - Entwickler):

PLANUNG (Unternehmen analysieren)
ANALYSE (Problem verstehen) - - >WAS soll das System tun?
ENTWURF (Lösungen suchen) - - >WIE soll es das tun?

PROGRAMMIERUNG


19.2 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)

19.3 Planning (Planung)

Diese Phase sollte maximal 6 Monate dauern und nicht mehr als 4 Mitarbeiter in Anspruch nehmen.

19.3.1 grobes ERD

z.B.: Firma Shell



19.3.2 Grobe Funktionsdekomposition

19.3.3 Organigramm

Stellen (Organisational Unit)

19.3.4 Unternehmensziele - CFS

19.3.4.1 CSF (Critical Sucess Faktor)

Gemessene kritische Faktoren, die für die Unternehmensziehle gebraucht werden.

19.3.5 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.

20 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.




21 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.

22 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)



23 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, dass eine Lösung öfters gebraucht wird sollte man Unterprogramme schreiben.

24 Strukturdiagramm (Structure Chart)


is_rwgs UP



is_rw is_gs

( muss 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

25 KOHÄSION (Cohesion)

25.1 Funktional Kohäsiv

jedes Unterprogramm sollte mit einem deutschen Satz (ohne UND) beschrieben werden können
z.B.: Diese Unterprogramm erkennt RW - Dreiecke. (++++)

25.2 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.) ( - )

25.3 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. ( - )

25.4 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. ( - )

25.5 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. ( - )

25.6 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.) ( - - )

25.7 Zufallskohäsion

Jobs zu einen UP verbinden, die überhaupt nicht miteinander zu tun haben
z.B.: Inventarnummer vergeben + Schüler löschen ( - - - )

26 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

26.1 Globale Kopplung = Global Coupling


!! ist sehr schlecht = unbedingt vermeiden !!

Es ist schwer zu debuggen, da man nicht weiß, wer wo was hinschreibt. Außerdem muss 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.

26.2 Inhaltskopplung = Content Coupling

Man spricht von Inhaltskopplung, wenn ein UP den Code eines anderen UP´s ändert.

27 Gestaltung von Benutzeroberflächen


Oberste Regel: Der Benutzer ist dümmer als man denkt. Er macht alles falsch, was er nur falsch machen kann!!!

27.1 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.

27.2 Layout

    Wenn von Papier auf EDV umgestellt wird, darauf achten, dass 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 muss 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

28 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, dass es beim Endtermin zB.: 3 - 4 Jahre später kein böses Erwachen gibt. es handelt sich um einen Teil der Spezifikation

29 Projektplanung (Softwareprojektplanung)


vor der Spezifikationsphase
es muss 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, dass 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, dass 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.


30 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, dass man selbst die Sprache bestimmen kann.
l Benutzersprache
Spezifikation soll so formuliert werden, dass der Kunde auch versteht worum es geht.

31 Testen


    Die besten Programmierer sollten Testen Teste nie dein eigenes Programm

31.1 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.

31.2 Testarten

31.2.1 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

31.2.2 Whitebox

Der Tester betrachtet den Programmcode.
Test wird so aufgebaut, dass möglichst viele Programmteile getestet werden.
Bsp.:
A ê B ê C ê





ê Rechteck

31.2.3 Strategie (keine ähnlichen Testfälle sind zu verwenden !)



è Äquivalenzkritärien



31.2.4 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

31.2.5 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.




32 Konstruktor/Destruktor



32.1 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)






33 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ässt.

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 ?

34 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


35 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)

36 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.

37 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, muss 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

Wir unterscheiden Arrays (sortiert, unsortiert) und Bäume.

38 Das Suchen in Arrays

38.1 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).







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

38.2 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.















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).

38.2.1 Indexreorganisation

Beim Binären Suchen ist das Einfügen teurer als bei der Sequentiellen Sortierung, da die Reihenfolge erhalten werden muss.
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.

39 Bäume












39.1 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

39.2 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.

39.3 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 - G



















39.4 Baum

Beim 2 - 3 - 4 Baum hat man nmax 3 Zahlen, die daraus folgend in maximal 4 Einteilungen unterteilt werden können.












39.5 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.






























40 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 muss so aufgebaut sein, das die Verteilung gleichmäßig erfolgt. Der ASCII - Zeichensatz ist dabei ein erster Ansatz. Das Wort 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).








Linear Probing
Bei der Methode des Linear Probing verwenden wir pro Bucket einen Datensatz.















Was geschieht aber, wenn durch das Linear Probing ein Österreicher in ein Feld geschoben werden mussm dass 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, dass es mehr Buckets als Datensätze geben muss.
Indirektes Suchen (Indirect Search)
(vgl. Buchindex am Ende eines Buches = Sortierte Datenstruktur mit einem Pointer auf Seiten)

























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.


41 Sortieralgorithmen

41.1 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.

41.2 Insertion Sort

Eine unsortierte bestehende Liste wird systematisch vom Anfang weg sortiert, indem die nächstkleinere Zahl links, die nächstgrößere Zahl rechts eingeordnet wird.
Der Insertion Sort ist sehr langsam, da nur benachbarte Elemente ausgetauscht werden.









41.3 Selection Sort

= Sortieren durch direktes Auswählen.

Der Selection Sort sucht aus einem Feld das kleinste Element und tauscht es gegen das an erster Stelle stehende Element. Dann wird das zweitkleinste Element gesucht und gegen das an zweiter Stelle stehende Element getauscht, u.sw. bis das gesamte Feld sortiert ist.

1. Durchgang
³
5
9
7
¬
6
3
2. Durchgang
1
°
9
7
8
6
®
3. Durchgang
1
3
´
7
8
6
°
4. Durchgang
1
3
5
²
8
±
9
5. Durchgang
1
3
5
6
³
²
9
6. Durchgang
1
3
5
6
7
8
9

41.4 Bubble Sort

=Sortieren durch direktes Austauschen

Beim durchlaufen der Datei werden jeweils 2 Elemente paarweise verglichen. Wenn dabei das linke Element kleiner ist als das rechte, wird es vertauscht, wenn nicht, wird weitergegangen, bis das rechte Ende des Feldes erreicht ist.

41.5 Indirect Sort

Beim Insertion Sort sortiert man einen Index auf die Tabelle.


41.6 Shell Sort

Der Shell Sort stellt das schnellste Sortierverfahren dar, wobei niemand weiß wieso. Es ist auch das einzige Sortierverfahren, das sich Mathematisch nicht erklären lässt und in keine Formel packen lässt.

Der Insertion Sort ist sehr langsam, weil nur benachbarte Elemente ausgetauscht werden. Wenn sich zum Beispiel das kleinste Element zufällig am Ende des Feldes befindet, so werden n Schritte benötigt, um es dorthin zu bekommen, wo es hingehört. Shellsort ist einfach eine Erweiterung von Insertion Sort, bei dem eine Erhöhung der Geschwindigkeit dadurch erzielt wird, dass ein Vertauschen von Elementen ermöglicht wird, die weit voneinander entfernt sind.

Es wird eine Schrittreihenfolge gewählt (z.B. 13 - h). Vom Ersten Element ausgehend wird jedes h - te Element herausgenommen und in die richtige Reihenfolge gebracht. Dieser Vorgang wird mit jedem Element durchgeführt bis man am Ende angelangt ist. Dann wird eine neue Schrittreihenfolge gewählt (kleiner als die erste z.B.: 5 - h) und der Prozeß beginnt von vorne.

Aus Versuchsreihen hat es sich herausgestellt, dass die Distanzen 1,4,13,40,121,... (3n+1) das schnellste Sortierverfahren darstellen. Es ist allerdings möglich, den Shellsort mit anderen Folgen von Distanzen noch effizienter zu machen. Doch es ist für relativ große n schwer, das Programm um mehr als 20% schneller zu machen.

41.7 Quick Sort

=rennt rekursiv durch
















41.7.1













Beim Quick Sort werden die 2 Teilfelder getrennt durchgegangen. Der linke Teil von links nach rechts, der rechte Teil von rechts nach links. Es wird immer dann unterbrochen, wenn ein Element kleiner ist als das Partitionselement ist. Wenn die beiden im Diagramm kleinen, nach oben zeigenden Pfeile stehengeblieben sind, werden die zwei Elemente vertauscht.

Der Nachteil des Quick Sort besteht darin, dass er rekursiv und störanfällig ist und dass er im Worst Case n² Operationen benötigt.

41.8 Distribution Counting

Eine sehr spezielle Situation, für die ein einfacher Sortieralgorithmus existiert, wenn eine Datei mit n Datensätzen viele verschiedene Zahlenschlüssel hat. Die Idee besteht darin, die Anzahl der Schlüssel mit jedem Wert zu ermitteln und dann die Ergebnisse der Zählung zu verwenden, um bei einem zweiten Durchlauf durch die Datei die Datensätze in die richtige Postition zu bringen.



5875 Worte in "deutsch"  als "hilfreich"  bewertet