Αλγόριθμοι, δεδομένα και διαδικασίες

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Προηγούμενα θέματα για σκέψη

Συζητήστε πως παρέχονται και υλοποιούνται τα παρακάτω στοιχεία στα λειτουργικά συστήματα MS-DOS, Unix, και Windows 95:
- Χρονοπρογραμματισμός
- Επικοινωνία μεταξύ διεργασιών
- Είσοδος / έξοδος με σταθμοσκόπηση
- Είσοδος / έξοδος με διακοπές
- Είσοδος / έξοδος ανεξάρτητα από τη συσκευή
- Προστασία μεταξύ διεργασιών
- Διαχείριση μνήμης με ανταλλαγή
- Διαχείριση μνήμης με σελιδοποίηση
- Αρχεία
- Κατάλογοι και ιεραρχική δομή
- Διαχείριση χώρου στα αποθηκευτικά μέσα
- Ασφάλεια

Ορισμός

Αλγόριθμος (algorithm) είναι μια διαδικασία που επεξεργαζόμενη ορισμένα στοιχεία με πεπερασμένο αριθμό βημάτων παράγει ένα συγκεκριμένο επιθυμητό αποτέλεσμα. Κάθε βήμα της διαδικασίας αποτελείται από μονοσήμαντα εκτελέσιμες πράξεις.

Εύρεση ν!

Παραγοντικό του Ν στο Χ

Πριν: Ν: φυσικός αριθμός
Μετά: Χ = Ν!

Είσοδος:
   Ν : Φυσικός αριθμός

Εξοδος:
   Χ : Φυσικός αριθμός

Κ : Φυσικός αριθμός

Χ <- 1
Κ <- Ν
Οσο Κ > 0
    Χ <- Χ * Κ
    Κ <- Κ - 1
Τέλος (όσο)

Ψευδοκώδικας

Ο ψευδοκώδικας (pseudocode) επιτρέπει την περιγραφή των αλγορίθμων.

Στοιχεία εισόδου, εξόδου και μεταβλητές

Είσοδος:
πλευρά_α, πλευρά_β, πλευρά_γ : Φυσικός αριθμός

Εξοδος:
εμβαδό : Φυσικός αριθμός

αριθμός_πλακών : Φυσικός αριθμός
συνολικό_βάρος : Πραγματικός αριθμός
είναι_ισοσκελές : Λογική τιμή

Προϋποθέσεις και μετά-συνθήκες

Πριν: Ν Φυσικός αριθμός
Μετά: Χ = Ν!

Εκχωρήσεις

ύψος <- συν(κλίση) * πλευρά
μέσο <- ύψος / 2

Βρόχοι

Οσο υπόλοιπο_χρημάτων > 0
   δώσε_χαρτονόμισμα
Τέλος (όσο)

Επανάλαβε
  μείωσε_αέρα
Οσο στροφές_κινητήρα < 900

Για πάντα
  έλεγξε_παραμέτρους_λειτουργίας_εργοστασίου
Τέλος (για πάντα)

Αποφάσεις

Αν ζωές_παίκτη > 0 Τότε
  ξεκίνα_νέο_παιγνίδι
Αλλιώς
  εμφάνισε "Game Over"
Τέλος (Αν)

Αν στροφές > 8700 Τότε
  διάκοψε_την_τροφοδοσία
Τέλος (Αν)

Αν ομάδα ΠΑΟ Τότε
  χρώμα <- πράσινο
Αλλιώς Αν ομάδα Ολυμπιακός Τότε
  χρώμα <- κόκκινο
Αλλιώς Αν ομάδα ΑΕΚ Τότε
  χρώμα <- κίτρινο
Τέλος (Αν)

Γλώσσες προγραμματισμού

Επιβάλλουν την έκφραση ενός αλγορίθμου με τυπική μορφή.
Χρησιμοποιούνται άμεσα ή έμμεσα από τον υπολογιστή.
Διαφορετικές γλώσσες διαθέτουν διαφορετικά επίπεδα και μέσα έκφρασης.

Γλώσσα μηχανής

Συμβολική γλώσσα

; Παραγοντικό του BX στο AX
	MOV  CX, BX
        MOV  AX, 1
LOOP:	CMP  CX, 0
	JZ   DONE
	MUL  CX
        DEC  CX
        JMP  LOOP
DONE:

C

/* Παραγοντικό */
int
factorial(int n)
{
	int result;
	int count;

	count = n;
	result = 1;
	while (count > 0) {
		result = result * count;
		count = count - 1;
	}
	return (result);
}

int
factorial(int n)
{
	int result = 1;

	for (; n; n--)
		result *= n;
	return (result);
}

Prolog

factorial(0, 1).

factorial(N, N_Factorial) :-
	N > 0,
	M is N - 1,
	factorial(M, M_Factorial),
	N_Factorial is M_Factorial * N.

Lisp

(define (factorial n)
  (if (= n 1)
    1
    (* n (factorial (- n 1)))))

Visual Basic

' Παραγοντικό του Ν
FUNCTION Factorial(N AS INTEGER) AS INTEGER
	DIM Count AS INTEGER
	DIM Result AS INTEGER

	Count = N
	Result = 1
	WHILE Count > 0
		Result = Result * Count
		Count = Count - 1
	WEND

END FUNCTION

Pascal

(* Παραγοντικό του Ν *)
function factorial(N : Integer) : Integer;
var
  Count, Result : Integer;
begin
     Count := N;
     Result := 1;
     While Count > 0 Do
     begin
           Result := Result * Count;
           Count := Count - 1
     end;
     Factorial := Result
end (* Factorial *);

Java

public int παραγοντικό(int ν) {
	int αποτέλεσμα;
	int μετρητής;

	μετρητής = ν;
	αποτέλεσμα = 1;
	while (μετρητής > 0) {
		αποτέλεσμα = αποτέλεσμα * μετρητής;
		μετρητής = μετρητής - 1;
	}
	return (αποτέλεσμα);
}

Πίνακες

Οι πίνακες (arrays) επιτρέπουν τη χρήση πολλών ομοίου τύπου στοιχείων.
Συνήθως το στοιχείο i ενός πίνακα A προσδιορίζεται ως A[i] ή A(i).
Μπορούν να οριστούν και πίνακες πολλαπλών διαστάσεων με στοιχεία αντίστοιχα προσδιορισμένα ως A[i,j] κ.λπ.
Συνήθως υλοποιούνται με τη διαδοχική φύλαξη των στοιχείων τους στη μνήμη.

Παράδειγμα

(* Άθροισμα στοιχείων του πίνακα n στοιχείων a *)
var
   a : array [1..10] of integer;
   n, i, sum : integer;

begin
     sum := 0;
     for i := 1 to 10 do
     begin
          sum := sum + a[i];
     end;
end.

Εγγραφές

Οι εγγραφές (records) επιτρέπουν τον ομαδικό χειρισμό διαφορετικού τύπου στοιχείων.
Συνήθως το στοιχείο i μιας εγγραφής A προσδιορίζεται ως A.i
Μπορούν να οριστούν και πίνακες που περιέχουν εγγραφές ή εγγραφές που περιέχουν πίνακες.
Συνήθως υλοποιούνται με τη διαδοχική φύλαξη των στοιχείων τους στη μνήμη.

Παράδειγμα

var point :
  record
     x : integer;			(* Συντεταγμένη x *)
     y : integer;			(* Συντεταγμένη y *)
  end;

var customer :
  record
    name : array [1..50] of char;	(* Όνομα πελάτη *)
    balance : integer;			(* Υπόλοιπο λογαριασμού *)
  end;

begin
     point.x := 1;
     point.y := 4;
end.

Δομές με δείκτη

Οι δείκτες (pointers) επιτρέπουν τον εύκολο ορισμό και χειρισμό σύνθετων δομών. Τέτοιες δομές μπορεί να είναι
Συνήθως τα περιεχόμενα ενός δείκτη p εκφράζονται ως *p (C) ή p^ (Pascal).
Οι δείκτες υλοποιούνται ως έμμεσες διευθύνσεις μνήμης.

Παράδειγμα

type
  link = ^integer_list;

  integer_list =
    record
      value : integer;
      next  : link;
    end;

Διαδικασίες, συναρτήσεις και τάξεις

Οι διαδικασίες (procedures) επιτρέπουν την οργάνωση των εντολών ενός προγράμματος που εκτελούν μια συγκεκριμένη λειτουργία σε μια ενότητα.
Οι συναρτήσεις (functions) επιτρέπουν την οργάνωση των εντολών ενός προγράμματος που υπολογίζουν ένα συγκεκριμένο αποτέλεσμα σε μια ενότητα.
Οι τάξεις (classes) επιτρέπουν την οργάνωση των στοιχείων και των εντολών που σχετίζονται με ένα αντικείμενο σε μια ενότητα.

Παράδειγμα συνάρτησης και διαδικασίας σε Pascal

program fun;

(* Παραγοντικό του Ν *)
function factorial(N : Integer) : Integer;
var
  Count, Result : Integer;
begin
     Count := N;
     Result := 1;
     While Count > 0 Do
     begin
           Result := Result * Count;
           Count := Count - 1
     end;
     Factorial := Result
end (* Factorial *);

procedure clear_screen;
const number_of_lines = 24;
var i : integer;

begin
  for i := 0 to number_of_lines do
      writeln('');
end (*clear_screen*);

begin
  clear_screen;
  writeln(factorial(5));
end.

Παράδειγμα τάξης σε Java

class Point extends Object {
   private int x;
   private int y;

   public void MoveTo(int x, int y) {
     this.x = x;
     this.y = y;
  }

  public int GetX() {
    return (x);
  }
}

Αναδρομικές τεχνικές

Διαδικασίες, συναρτήσεις και δομές που ορίζονται αναδρομικά (recursively) μπορούν εύκολα να ανιμετωπιστούν με τη χρήση αναδρομικών τεχνικών προγραμματισμού.

Παράδειγμα

program recursive;

(* Αναδρομικός ορισμός δεδομένων *)
type
  link = ^integer_list;

  integer_list =
    record
      value : integer;
      next  : link;
    end;

(* Αναδρομική διαδικασία *)
procedure russian_doll(size : integer);
var i : integer;

begin
   write('[');
   for i := 1 to size do
      write('-');
   writeln(']');
   if size > 1 then
     russian_doll(size - 1);
end (* russina_doll *) ;


(* Αναδρομική συνάρτηση *)
function factorial(n : integer) : integer;
begin
     if n = 0 then
        factorial := 1
     else
         factorial := n * factorial(n - 1)
end (* factorial *);

begin
  writeln(factorial(5));
  russian_doll(10);
end.

Αποτελέσματα

120
[----------]
[---------]
[--------]
[-------]
[------]
[-----]
[----]
[---]
[--]
[-]

Βιβλιογραφία

Peter Rechenberg. Εισαγωγή στην Πληροφορική. σ. 112-133 Κλειδάριθμος, 1992.

David Harel. Algorithmics: the Spirit of Computing. Addison-Wesley, 1987.
Ravi Sethi. Programming Languages: Convepts and Constructs. Addison-Wesley, 1989.

Ασκήσεις

Εκφράστε με ψευδοκώδικα τη διαδικασία μιας πρόσφατης συναλλαγής σας με το Δημόσιο.
Εκφράστε με ψευδοκώδικα τον τρόπο με τον οποίο δίνονται ρέστα στα καταστήματα.
Βελτιώστε τον κώδικα φυλάσσοντας σε πίνακες τις αξίες και ποσότητες των νομισμάτων που υπάρχουν στο ταμείο.
Εκφράστε με ψευδοκώδικα τη διαδικασία πολλαπλασιασμού δύο αριθμών Μ, Ν σε λογ2(MAX(N,M)) βρόχους. Μπορείτε να χρησιμοποιήσετε πρόσθεση, σύζευξη και ολίσθηση.

Περιεχόμενα