Theoretical Computer Science; Algorithms and Data Structures

Diomidis Spinellis
 Department of Management Science and Technology
Athens University of Economics and Business
Athens, Greece
dds@aueb.gr

Επαλήθευση αλγορίθμων

Παράδειγμα

Είσοδος:
  Α(1..Ν): πίνακας ακεραίων
  N : ακέραιος
Έξοδος:
  Β(1..Ν): πίνακας ακεραίων

Προϋποθέσεις:
  Ν >= 1
Μετασυνθήκες:
  Β(1..Ν) περιέχει τις τιμές του Α(1..Ν)

Μεταβλητές
  Ι : Ακέραιος

I := 1
Όσο Ι <= Ν
  Β(Ι) := Α(Ι)
  Αναλοίωτη συνθήκη: Β(1..Ι) := Α(1..Ι)
  Συνθήκη σύγκλισης: Ν - Ι
  Ι := Ι + 1
Τέλος

Αποδοτικότητα των αλγορίθμων

Πολυπλοκότητα

Μη υπολογισιμότητα

Το πρόβλημα του τερματισμού (halting problem)

Τερματίζει(Πρόγραμμα, Δεδομένα)
Είσοδος: Πρόγραμμα, Δεδομένα
Έξοδος: Αληθές αν το πρόγραμμα τερματίζει με τα δεδομένα,
αλλιώς ψευδές.

Δοκιμή(Πρόγραμμα, Δεδομένα)
Αν Τερματίζει(Πρόγραμμα, Δεδομένα) Τότε
  Όσο αληθές
  Τέλος (Όσο)
Αλλιώς
  Δοκιμή := ψευδές
Τέλος (Αν)

Δοκιμή(Δοκιμή ..., Δοκιμή ...)

Αλγοριθμική οικουμενικότητα

Πεπερασμένα αυτόματα (Finite automata)

Πεντάδα Α = (Ι, Ο, S, λ, δ)
  1. Ι : Τιμές εισόδου
  2. Ο : Τιμές εξόδου
  3. S : Πεπερασμένο σύνολο εσωτερικών καταστάσεων
  4. λ : S X I -> S Συνάρτηση επόμενης κατάστασης
  5. δ : S X I -> O Συνάρτηση επόμενης τιμής εξόδου

Η μηχανή του Turing

  1. Πεπερασμένο αλφάβητο: Α
  2. Πεπερασμένο σύνολο καταστάσεων: Μ
  3. Άπειρη ταινία
  4. Κεφαλή γραφής και ανάγνωσης
  5. Διάγραμμα μετάπτωσης: (Α Χ Μ) -> (Α X {Δ, Α, Σ}) Χ Μ

Παραδείγματα

Η θέση των Church/Turing

Πιθανοτικοί αλγόριθμοι

Δειπνούντες φιλόσοφοι

Για πάντα
   Πέτα νόμισμα και περίμενε το ανάλογο πηρούνι
   Αν υπάρχει και το άλλο πηρούνι Τότε
      πάρε το άλλο πηρούνι
      φάε
   Αλλιώς
      Άσε τα πηρούνια
   Τέλος
Τέλος

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

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

89 D9 
B8 01 00 
83 F9 00 
74 05 
F7 E1 
49 
EB F6

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

; Παραγοντικό του BX στο AX
        MOV  CX, BX             ; Μετρητής στο CX
        MOV  AX, 1              ; Αρχική τιμή 1
LOOP:   CMP  CX, 0              ; Τέλος;
        JZ   DONE               ; Ναι, έξοδος
        MUL  CX                 ; Όχι, πολλαπλασίασε ΑΧ με CX
        DEC  CX                 ; Επόμενη τιμή του CX
        JMP  LOOP               ; Πίσω στο βρόχο
DONE:

Fortran 77

C Return factorial of N
C
      FUNCTION IFACTORIAL(N)
      INTEGER N
      INTEGER IFACTORIAL
      INTEGER IRESULT, I

      IRESULT = 1
      DO I = 1, N
        IRESULT = IRESULT * I
      END DO
      IFACTORIAL = IRESULT

      END

Fortran 95

! Return factorial of n
function factorial(n) result (nfac)
        integer, intent(in) :: n
        integer :: factorial
        integer :: i

        nfac = 1
        do i = 1, n
                nfac = nfac * i
        end do
end function factorial

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

% To N_Factorial είναι ισοδύναμο με Ν!
factorial(N, N_Factorial) :-
        N > 0,
        M is N - 1,
        factorial(M, M_Factorial),
        N_Factorial is M_Factorial * N.

Lisp

;; Επιστρέφει το παραγοντικό του n
(define (factorial n)
  (if (= n 1)
    1
    (* n (factorial (- n 1)))))

Basic

500 REM Return factorial of N in variable FACT
510 FACT = 1
520 FOR I = 1 TO N
530 FACT = FACT * I
540 NEXT I
550 RETURN

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 (αποτέλεσμα);
}

Πίνακες

Παράδειγμα

class Sum {
        static int sum(int a[]) {
                int i, sum = 0;

                for (i = 0; i < a.length; i++)
                        sum += a[i];
                return sum;
        }

        static int testdata[] = {1, 2, 3, 4, 5};

        public static void main(String args[]) {
                System.out.println(sum(testdata));
        }
}

Εγγραφές

Παράδειγμα

struct point {
        double x;       /* X coordinate */
        double y;       /* Y coordinate */
};

struct customer {
        char name[50];  /* Customer name */
        int balance;    /* Account balance */
};

struct customer customer_list[100];

main()
{
        struct point a, b;

        a.x = 5;
        a.y = 9;
        b.x = 12;
        b.y = 19;
}

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

Παράδειγμα (C)

struct s_int_list {
	int val;
	struct s_int_list *next;
};

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

Παράδειγμα συνάρτησης και διαδικασίας σε 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);
  }
}

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

Παράδειγμα

class Recurse {
        static void russian_doll(int size) {
                int i;

                System.out.print("[");
                for (i = 0; i < size; i++)
                        System.out.print("-");
                System.out.println("]");
                if (size > 1)
                        russian_doll(size - 1);
        }

        static int factorial(int n) {
                if (n == 0)
                        return (1);
                else
                        return (n * factorial(n - 1));
        }

        public static void main(String args[]) {
                System.out.println(factorial(5));
                russian_doll(10);
        }
}

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

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

Οι πύργοι του Ανόι

import java.util.*;

public class Hanoi {
        static Stack A, B, C;

        /** Display the contents of a collection with a given name */
        static void showCollection(String name, Collection c) {
                Iterator i;

                System.out.print(name + ": ");
                for (i = c.iterator(); i.hasNext(); )
                        System.out.print(i.next() + " ");
                System.out.println();
        }

        /** Display the hanoi towers */
        static void showConfiguration() {
                showCollection("A", A);
                showCollection("B", B);
                showCollection("C", C);
                System.out.println();
        }

        /** Move n blocks from to using tmp */
        static void move(int n, Stack from, Stack to, Stack tmp) {
                if (n == 1) {
                        to.push(from.pop());
                        showConfiguration();
                } else {
                        move(n - 1, from, tmp, to);
                        to.push(from.pop());
                        showConfiguration();
                        move(n - 1, tmp, to, from);
                }
        }

        public static void main(String args[]) {
                final int N = 4;
                A = new Stack();
                B = new Stack();
                C = new Stack();

                for (int i = N; i > 0; i--)
                        A.push(new Integer(i));
                showConfiguration();
                move(N, A, C, B);
        }
}

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

Creative Commons License  Last change: Wednesday, December 15, 2004 3:09 pm
 Unless otherwise expressly stated, all original material on this page created by Diomidis Spinellis is licensed under a Creative Commons Attribution-Share Alike 3.0 Greece License.