Γλώσσες προγραμματισμού και δομές δεδομένων

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

Εισαγωγή - Πίνακες

Καλώς ήρθατε

Γλώσσες προγραμματισμού και δομές δεδομένων

Τι περιλαμβάνει το μάθημα

  1. Εισαγωγή - Πίνακες
  2. Στοίβες
  3. Ουρές και δείκτες
  4. Συνδεδεμένες λίστες
  5. Δένδρα
  6. Γράφοι
  7. Αναζήτηση
  8. Ταξινόμηση
  9. Κατακερματισμός
  10. Τεχνικές αρχείων
  11. Αντικείμενα στη C++
  12. Κληρονομικότητα
  13. Αντικειμενοστρεφής σχεδιασμός με UML
  14. Η βιβλιοθήκη STL
  15. Λίστες στη Lisp
  16. Κατηγορήματα στην Prolog
  17. Παραλληλία στα Windows NT
  18. Οπτικός προγραμματισμός σε Automation Basic
  19. Ανασκόπηση - επανάληψη

Οι σημειώσεις

Αφηρημένοι τύποι δεδομένων

Παράδειγμα

Το παρακάτω παράδειγμα ορίζει έναν ΑΤΔ για σημεία σε δύο διαστάσεις. Ο τελεστής -> στη χρήση structure_pointer->member είναι συντομογραφία του (*structure_pointer).member.
Δηλώσεις: point.h
/*
 * Abstract Data Type Definition file point.h
 */

typedef struct s_point *point;

point new_point(void);
int get_x_point(point p);
int get_y_point(point p);
void set_point(point p, int x, int y);
void delete_point(point p);
Ορισμοί: point.c
/*
 * Abstract Data Type Implementation file point.c
 */

#include <stdlib.h>
#include "point.h"

struct s_point {
	int x, y;		/* Point coordinates */
};

point
new_point(void)
{
	return (point)malloc(sizeof(struct s_point));
}

int
get_x_point(point p)
{
	return (p->x);
}

int
get_y_point(point p);
{
	return (p->y);
}

void
set_point(point p, int x, int y)
{
	p->x = x;
	p->y = y;
}

void
delete_point(point p)
{
	free(p);
}

Σημείωση: στη γλώσσα C++ οι μέθοδοι new και delete παρέχονται από τη γλώσσα, ενώ στις υπόλοιπες συναρτήσεις ο δείκτης p μεταφέρεται αυτόματα

Πίνακες

Υλοποίηση πινάκων

Το παρακάτω παράδειγμα ορίζει έναν ΑΤΔ για πίνακα ακεραίων δύο διαστάσεων με δυναμικά οριζόμενες διαστάσεις. Ο υπολογισμός της θέσης ενός στοιχείου γίνεται με τη απεικόνιση των δύο διαστάσεων του πίνακα στη μία διάσταση της δυναμικής μνήμης.

Δηλώσεις: array2d.h
/*
 * Abstract Data Type Definition file array2d.h
 */

typedef struct s_array2d *array2d;

array2d new_array2d(int rows, int cols);
void array2d_set_value(array2d a, int row, int col, int val);
int array2d_get_value(array2d a, int row, int col);
void array2d_delete(array2d a);
Ορισμοί: array2d.c
/*
 * Abstract Data Type Implementation file array2d.c
 * 2D -> 1D mapping implementation
 */

#include <stdlib.h>
#include <assert.h>
#include "array2d.h"

struct s_array2d {
	int *values;		/* Value storage */
	int rows, cols;		/* Dimensions */
};

array2d
new_array2d(int rows, int cols)
{
	array2d a;

	a = (array2d)malloc(sizeof(struct s_array2d));
	assert(a != NULL);

	a->values = (int *)malloc(rows * cols * sizeof(int));
	assert(a->values != NULL);

	a->rows = rows;
	a->cols = cols;
}

void
array2d_set_value(array2d a, int row, int col, int val)
{
	assert(row > 0 && row < a->rows);
	assert(col > 0 && col < a->cols);
	a->values[row * a->cols + col] = val;
}

int
array2d_get_value(array2d a, int row, int col)
{
	assert(row > 0 && row < a->rows);
	assert(col > 0 && col < a->cols);
	return (a->values[row * a->cols + col]);
}

void
array2d_delete(array2d a)
{
	free(a->values);
	free(a);
}

Εναλλακτικά, μπορούμε να υλοποιήσουμε τον πίνακα δύο διαστάσεων με βάση έναν πίνακα από δείκτες σε πίνακες μιας διάστασης. Η τεχνική αυτή υλοποίησης μπορεί να είναι αποδοτικότερη σε αρχιτεκτονικές όπου ο πολλαπλασιασμός διαρκεί μεγαλύτερο χρόνο από την πρόσβαση στη μνήμη ή σε περιπτώσεις όπου οι διαστάσεις των γραμμών του πίνακα δεν είναι όλες ίσες.

Οι δηλώσεις του ΑΤΔ παραμένουν φυσικά οι ίδιες.

Ορισμοί: array2d.c
/*
 * Abstract Data Type Implementation file array2d.c
 * Array of pointer implementation
 */

#include <stdlib.h>
#include <assert.h>
#include "array2d.h"

struct s_array2d {
	int **values;		/* Value storage */
	int rows, cols;		/* Dimensions */
};

array2d
new_array2d(int rows, int cols)
{
	array2d a;
	int i;

	a = (array2d)malloc(sizeof(struct s_array2d));
	assert(a != NULL);

	a->values = (int **)malloc(rows * sizeof(int *));
	assert(a->values != NULL);

	for (i = 0; i < rows; i++) {
		a->values[i] = (int *)malloc(cols * sizeof(int));
		assert(a->values[i] != NULL);
	}

	a->rows = rows;
	a->cols = cols;
}

void
array2d_set_value(array2d a, int row, int col, int val)
{
	assert(row > 0 && row < a->rows);
	assert(col > 0 && col < a->cols);
	a->values[row][col] = val;
}

int
array2d_get_value(array2d a, int row, int col)
{
	assert(row > 0 && row < a->rows);
	assert(col > 0 && col < a->cols);
	return (a->values[row][col]);
}

void
array2d_delete(array2d a)
{
	int i;

	for (i = 0; i < a->rows; i++)
		free(a->values[i]);
	free(a->values);
	free(a);
}

Ειδικές μορφές πινάκων

Οι παραπάνω μορφές πινάκων μπορούν να υλοποιηθούν πολύ κομψά με τη χρήση ΑΤΔ. Οι παρακάτω ορισμοί υλοποιούν συμμετρικό πίνακα ακεραίων που ορίζεται με πίνακα δεικτών. Οι δηλώσεις του ΑΤΔ παραμένουν φυσικά οι ίδιες με αυτές στο προηγούμενο παράδειγμα.
Ορισμοί: array2d.c
/*
 * Abstract Data Type Implementation file array2d.c
 * Array of pointer implementation
 * Special case for symmetric arrays
 */

#include <stdlib.h>
#include <assert.h>
#include "sym.h"

struct s_array2d {
	int **values;		/* Value storage */
	int rows, cols;		/* Dimensions */
};

/*
 * Given a pointer to a symmetric array and the coordinates of an
 * an element return a pointer to its location.  Elements on the left
 * and below the diagonal are mapped using the diagonal as the axis of 
 * symmetry
 */
static int *
value_position(array2d a, int row, int col)
{
	assert(row >= 0 && row < a->rows);
	assert(col >= 0 && col < a->cols);
	if (row > col)
		return (&(a->values[col][row]));
	else
		return (&(a->values[row][col]));
}

array2d
new_array2d(int rows, int cols)
{
	array2d a;
	int i;

	assert(rows == cols);		/* Must be symmetric */
	a = (array2d)malloc(sizeof(struct s_array2d));
	assert(a != NULL);

	a->values = (int **)malloc(rows * sizeof(int *));
	assert(a->values != NULL);

	for (i = 0; i < rows; i++) {
		a->values[i] = (int *)malloc((i + 1) * sizeof(int));
		assert(a->values[i] != NULL);
	}

	a->rows = rows;
	a->cols = cols;
	return (a);
}

void
set_val_array2d(array2d a, int row, int col, int val)
{
	*value_position(a, row, col) = val;
}

int
get_val_array2d(array2d a, int row, int col)
{
	return (*value_position(a, row, col));
}

void
delete_array2d(array2d a)
{
	int i;

	for (i = 0; i < a->rows; i++)
		free(a->values[i]);
	free(a->values);
	free(a);
}

Συσχετιστικοί πίνακες

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

Γενική βιβλιογραφία

Ασκήσεις

Άσκηση 1 (προαιρετική)

  1. Να ορίσετε τον ΑΤΔ για ένα τριδιαγώνιο πίνακα αριθμών κινητής υποδιαστολής.
  2. Υλοποιήστε ένα πρόγραμμα ελέγχου του ΑΤΔ.

Στοίβες

Ορισμός

Υλοποίηση στη μνήμη

Υλοποίηση σε C

Αφηρημένος τύπος

O παρακάτω ΑΤΔ ορίζει τις βασικές συναρτήσεις για τη χρήση μιας στοίβας ακεραίων.
Επιστρέφεται μια νέα κενή στοίβα
int_stack new_int_stack(void);
Το στοιχείο i εισάγεται στην κορυφή της στοίβας s
void push_int_stack(int_stack s, int i);
Το στοιχείο από την κορυφή της στοίβας s αφαιρείται και επιστρέφεται
int pop_int_stack(int_stack s);
Επιστρέφεται αληθές αν η στοίβα s είναι κενή
int isempty_int_stack(int_stack s);
Απαλείφεται η στοίβα
void delete_int_stack(int_stack s);

Εφαρμογές

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

Ασκήσεις

Άσκηση 2

  1. Να υλοποιηθεί σε C ο ΑΤΔ στοίβας ακεραίων.
  2. Με βάση τον ΑΤΔ να υλοποιηθεί πρόγραμμα το οποίο να διαβάζει ακεραίους μέχρι να διαβάσει 0 και να τους τυπώνει με αντίστροφη σειρά.

Συνδεδεμένες λίστες

Ορισμός

Υλοποίηση στη μνήμη

Υλοποίηση με πίνακα

Υλοποίηση σε C

Παράδειγμα (διαβάζει ακέραιους σε λίστα και τους τυπώνει με την ανάποδη σειρά): 
#include <stdlib.h>
#include <stdio.h>

/* List of integers */
struct s_list {
	int val;		/* Integer value */
	struct s_list *next;
};

main()
{
	struct s_list *head, *p;
	int n;

	head = NULL;
	/* Read list elements */
	while (scanf("%d", &n) == 1) {
		p = (struct s_list *)malloc(sizeof(struct s_list));
		p->val = n;
		p->next = head;
		head = p;
	}

	printf("\nStarting output:\n");
	/* Print list elements */
	for (p = head; p; p = p->next)
		printf("%d\n", p->val);
}

Αφηρημένος τύπος

Ορισμός του τύπου της συνδεδεμένης λίστας ακεραίων
typedef struct s_int_list *int_list;
Επιστρέφεται μια άδεια συνδεδεμένη λίστα
int_list list_new(void);
Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο i στην αρχή της
int_list int_list_add(int_list l, int i);
Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο i διαγραμμένο
int_list int_list_del(int_list l, int i);
Επιστρέφει αληθές αν κάποιο στοιχείο της λίστας έχει την τιμή i, αλλιώς ψευδές.
int int_list_search(int_list l, int i);
Καλεί τη συνάρτηση process για κάθε στοιχείο της λίστας
void int_list_traverse(int_list l, void (*process)(int i));
Επιστρέφεται αληθές αν η λίστα είναι κενή
int int_list_isempty(int_list l);
Διαγράφει όλα τα στοιχεία της λίστας l
void int_list_delete(int_list l);

Ειδικές μορφές λιστών

Διακρίνουμε τις παρακάτω ειδικές μορφές συνδεδεμένων λιστών:
διπλά συνδεδεμένη λίστα (doubly linked list)
Κάθε στοιχείο της λίστας έχει δείκτες στο προηγούμενο και το επόμενο. Αυτή μπορεί να οριστεί με την παρακάτω δομή της C: 
struct s_int_dlist {
	int	val;			/* Integer value */
	struct s_int_dlist *prev;	/* Previous element */
	struct s_int_dlist *next;	/* Next element */
};
Η εισαγωγή ενός στοιχείου np πριν από το στοιχείο της λίστας p γίνεται με τις παρακάτω εντολές: 
	p->prev->next = np;
	np->next = p;
	np->prev = p->prev;
	p->prev = np;
κυκλικά συνδεδεμένη λίστα
Το τελευταίο στοιχείο της λίστας δείχνει ξανά το πρώτο. Η δομή αυτή ονομάζεται και δακτύλιος (ring). Η διάσχιση της δομής αυτής πρέπει να γίνει με προσοχή για να μην καταλήξει σε ατέρμoνο βρόχο: 
	struct s_dlist *start, *p;

	p = start;
	if (p)
		do {
			/* Process list element */
			...
			p = p->next;
		} while (p != start);
κυκλικά διπλά συνδεδεμένη λίστα
Σύνθεση των παραπάνω.

Εφαρμογές

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

Ασκήσεις

Άσκηση 3

  1. Να υλοποιηθεί σε C ο αφηρημένος τύπος της συνδεδεμένης λίστας χαρακτήρων σύμφωνα με τις παρακάτω συναρτήσεις:
    Ορισμός του τύπου της συνδεδεμένης λίστας χαρακτήρων
    Επιστρέφεται μια άδεια συνδεδεμένη λίστα
    char_list char_list_new(void);
    Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο c στην αρχή της
    char_list char_list_add(char_list l, char c);
    Καλεί τη συνάρτηση process για κάθε στοιχείο της λίστας
    void char_list_traverse(char_list l, void (*process)(char c));
    Επιστρέφεται αληθές αν η λίστα είναι κενή
    int char_list_isempty(char_list l);
    Διαγράφει όλα τα στοιχεία της λίστας l
    void char_list_delete(char_list l);
  2. Με βάση τον αφηρημένο αυτό τύπο να υλοποιηθεί πρόγραμμα το οποίο να διαβάζει μια σειρά χαρακτήρων μέχρι να συναντήσει μια τελεία και στη συνέχεια να τυπώνει τους χαρακτήρες αυτούς με την αντίστροφη σειρά.
      Παράδειγμα: 
      L
I
V
E
.
E
V
I
L

    Ουρές

    Ορισμός

    Υλοποίηση στη μνήμη

    Υλοποίηση σε C

    Υλοποίηση με πίνακα

    Παράδειγμα 1
    struct s_int_queue {
	int values[20];			/* Array of values */
	int head;			/* Head of queue (values[head]) */
	int tail;			/* Tail of queue (values[tail]) */
};
    Παράδειγμα 2
    struct s_int_queue {
	int *values;			/* Allocated array of values */
	int values_size;		/* Number of values allocated */
	int head;			/* Head of queue (values[head]) */
	int tail;			/* Tail of queue (values[tail]) */
};
    Παράδειγμα 3
    struct s_int_queue {
	int *values_start;		/* Start of allocated array of values */
	int *values_end;		/* End of allocated array of values */
	int *head;			/* Head of queue  */
	int *tail;			/* Tail of queue  */
};

    Υλοποίηση με συνδεδεμένη λίστα

    Παράδειγμα
    struct s_int_list {
	int val;
	struct s_int_list *next;
};

struct s_int_queue {
	struct s_int_list *head;
	struct s_int_list *tail;
};

/* Add an element to the queue */
void
int_queue_put(struct s_int_queue *q, int v)
{
	struct s_int_list *p;

	p = (struct s_int_list *)malloc(sizeof(struct s_int_list));
	p->next = NULL;
	p->val = v;
	if (q->tail != NULL)
		q->tail->next = p;	/* Add element to queue tail */
	else
		q->head = p;		/* Special case for empty queue */
	q->tail = p;
}

/* Remove and return an element from a non-empty queue */
int
int_queue_get(struct s_int_queue *q)
{
	int v;
	struct s_int_list *tmp;

	assert(q->head != NULL);

	v = q->head->val;
	if (q->head->next == NULL)
		q->tail = NULL;		/* Special case for empty queue */
	tmp = q->head->next;
	free(q->head);
	q->head = tmp;
	return (v);
}

    Αφηρημένος τύπος

    Ορισμός του τύπου της ουράς λίστας ακεραίων
    typedef struct s_int_queue *int_queue;
    Επιστρέφει μια άδεια ουρά
    int_queue new_int_queue(void);
    Το στοιχείο i εισάγεται στο τέλος της ουράς
    void put_int_queue(int_queue q, int i);
    Το στοιχείο από την αρχή της μη κενής ουράς αφαιρείται και επιστρέφεται
    int get_int_queue(int_queue q);
    Επιστρέφεται αληθές αν η ουρά είναι κενή
    int isempty_int_queue(int_queue q);
    Διαγράφει την ουρά
    void delete_int_queue(int_queue q);

    Εφαρμογές

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

    Ασκήσεις

    Άσκηση 4

    1. Να υλοποιηθεί σε C ο αφηρημένος τύπος της ουράς ακεραίων σύμφωνα με τις παρακάτω συναρτήσεις:
      Επιστρέφει μια άδεια ουρά
      int_queue new_int_queue(void);
      Το στοιχείο i εισάγεται στο τέλος της ουράς
      void put_int_queue(int_queue q, int i);
      Το στοιχείο από την αρχή της μη κενής ουράς αφαιρείται και επιστρέφεται
      int get_int_queue(int_queue q);
      Επιστρέφεται αληθές αν η ουρά είναι κενή
      int isempty_int_queue(int_queue q);
    2. Με βάση τον αφηρημένο αυτό τύπο και μονοτονικά αυξανόμενη μεταβλητή να υλοποιηθεί πρόγραμμα το οποίο να υλοποιεί ουρά εξυπηρέτησης πελατών ως εξής:
      1. Όταν εισάγεται ο χαρακτήρας I (In) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του νέου πελάτη.
      2. Όταν εισάγεται ο χαρακτήρας O (Out) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του επόμενου πελάτη που θα εξυπηρετηθεί.
      Παράδειγμα: 
      I
1
I
2
I
3
O
1
I
4
O
2
...

    Δένδρα

    Ορισμοί

    Ιδιότητες

    Υλοποίηση σε C

    Παράδειγμα: 
    #include <stdlib.h>

/*
 * Declare a binary tree of integers
 */
struct s_tree {
	int val;
	struct s_tree *left, *right;
};

main()
{
	struct s_tree *tree, *node;

	node = (struct s_tree *)malloc(sizeof(struct s_tree));
	node->val = 5;
	node->left = node->right = NULL;
	tree = node;

	node = (struct s_tree *)malloc(sizeof(struct s_tree));
	node->val = 12;
	node->left = node->right = NULL;
	tree->right = node;
}

    Δένδρα αναζήτησης

    Παράδειγμα αναζήτησης

    /*
 * Search for the integer i in the ordered binary tree t
 * If found return its node; otherwise return NULL
 */
struct s_tree
search(struct s_tree *t, int i)
{
	if (t == NULL)
		return (NULL);
	else if (t->val == i)
		return (t);
	else if (i < t->val)
		return (search(t->left, i));
	else
		return (search(t->right, i));
}

    Διάσχιση δένδρων

    Η διάσχιση ενός δένδρου μπορεί να γίνει με τους παρακάτω τρόπους ανάλογα με τη σειρά επίσκεψης των κόμβων:
    Προδιαταγμένη διάσχιση (preorder traversal)
    1. επίσκεψη της ρίζας
    2. επίσκεψη του αριστερού υποδένδρου
    3. επίσκεψη του δεξιού υποδένδρου
    Μεταδιαταγμένη διάσχιση (postorder traversal)
    1. επίσκεψη του αριστερού υποδένδρου
    2. επίσκεψη του δεξιού υποδένδρου
    3. επίσκεψη της ρίζας
    Ενδοδιαταγμένη διάσχιση (inorder traversal)
    1. επίσκεψη του αριστερού υποδένδρου
    2. επίσκεψη της ρίζας
    3. επίσκεψη του δεξιού υποδένδρου
    Επιπεδοδιαταγμένη διάσχιση (level order traversal)
    1. επίσκεψη των κόμβων από πάνω προς τα κάτω

    Οι αντίστοιχες διασχίσεις διάσχισης υλοποιούνται αναδρομικά ως εξής:

    Προδιαταγμένη διάσχιση 
    void
visit(struct s_tree *t, void(*process)(int val))
{
	if (t == NULL)
		return;
	process(t->val);
	visit(t->left);
	visit(t->right);
}
    Μεταδιαταγμένη διάσχιση 
    void
visit(struct s_tree *t, void(*process)(int val))
{
	if (t == NULL)
		return;
	visit(t->left);
	visit(t->right);
	process(t->val);
}
    Ενδοδιαταγμένη διάσχιση 
    void
visit(struct s_tree *t, void(*process)(int val))
{
	if (t == NULL)
		return;
	visit(t->left);
	process(t->val);
	visit(t->right);
}
    Επιπεδοδιαταγμένη διάσχιση 
    /*
 * Process all nodes at taget level given a tree t and its current depth level
 * Return the number of nodes processed
 * (Used by the visit function)
 */
static int
visit_level(struct s_tree *t, int current_level, int target_level, void(*process)(int val))
{
	if (t == NULL || current_level > target_level)
		return (0);
	else if (current_level == target_level) {
		process(t->val);
		return (1);
	} else
		return (
		    visit_level(t->left, current_level + 1, target_level, process) +
		    visit_level(t->left, current_level + 1, target_level, process));
}

void
visit(struct s_tree *t, void(*process)(int val))
{
	int i = 0;
	int nodes_processed;

	do {
		nodes_processed = visit_level(t, 0, i, process);
		i++;
	} while (nodes_processed > 0);
}

    Εφαρμογές

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

    Ασκήσεις

    Άσκηση 5

    1. Να υλοποιηθεί σε C πρόγραμμα το οποίο με τη χρήση διατεταγμένου δυαδικού δένδρου διαβάζει από το χρήστη μια σειρά από ονόματα μέχρι να τελειώσει το αρχείο που διαβάζει (π.χ. ο χρήστης πληκτρολογήσει CTRL-Z) και τα εκτυπώνει με αλφαβητική σειρά. Παράδειγμα: 
      Verdi
Strauss
Mozart
Wagner
Adams
Gounod
Bellini
Gauss
Bizet
Donizetti
Mascagni
Puccini
Rossini
^Z
Adams
Bellini
Bizet
Donizetti
Gauss
Gounod
Mascagni
Mozart
Puccini
Rossini
Strauss
Verdi
Wagner
      Σημείωση 1: Η συνάρτηση strcmp συγκρίνει αλφαβητικά δύο συμβολοσειρές (α, β), και επιστρέφει ανάλογα -1 (α < β), 0 (α = β), ή 1 (α > β). Ορίζεται στην string.h.

      Σημείωση 2: Ανάγνωση των συμβολοσειρών μέχρι το τέλος του αρχείου, αντιγραφή τους σε χώρο που έχει επιστραφεί από τη malloc, και αποθήκευσή του δείκτη σε μεταβλητή p τύπου char * μπορεί να γίνει ως εξής: 

      	char buff[80];

	while (fgets(buff, sizeof(buff), stdin)) {
		p = strdup(buff);
		...
	}
      Η δήλωση της strdup βρίσκεται στην επικεφαλίδα string.h.

      Σημείωση 3: Ο ορισμός των παρακάτω δύο συναρτήσεων μπορεί να σας βοηθήσει στη δομή του προγράμματος: 

      static void add_tree(struct s_btree **t, char *name);
static void print_tree(struct s_btree *t);

    Γράφοι

    Ορισμοί

    Παράσταση

    Ένας γράφος μπορεί εύκολα να παρασταθεί με δύο διαφορετικούς τρόπους:
    1. πίνακα γειτνίασης (adjacency matrix).
    2. λίστα γειτνίασης (adjacency list).
    Και οι δύο τρόποι προϋποθέτουν ένα μονοσήμαντο σύστημα αρίθμησης των κόμβων.

    Πίνακας γειτνίασης

    Σε έναν γράφο με ν κόμβους ο πίνακας ν*ν γειτνίασης περιέχει 1 στις θέσεις (κ,λ) όπου υπάρχει ακμή από τον κόμβο κ στον κόμβο λ.

    Παράδειγμα για γράφο 100 κόμβων: 

    /*
 * Adjacency matrix for a graph of 100 nodes
 */
static int adjmatrix[100][100];

main()
{
	int a, b;

	/* Read edges and connect them */
	while (scanf(%d %d", &a, &b) == 2)
		adjmatrix[a][b] = adjmatrix[b][a] = 1;
}

    Λίστα γειτνίασης

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

    Παράδειγμα για γράφο 10 κόμβων: 

    #include <stdlib.h>
#include <stdio.h>

/*
 * Adjacency list for a graph of 10 nodes
 */
struct s_adjlist {
	int node;
	struct s_adjlist *next;
};

static struct s_adjlist *adj[10];

main()
{
	int a, b;
	struct s_adjlist *p;
	int i;

	/* Read edges and connect them */
	while (scanf("%d %d", &a, &b) == 2) {
		p = (struct s_adjlist *)malloc(sizeof(struct s_adjlist));
		p->node = b;
		p->next = adj[a];
		adj[a] = p;
		p = (struct s_adjlist *)malloc(sizeof(struct s_adjlist));
		p->node = a;
		p->next = adj[b];
		adj[b] = p;
	}
}

    Πρόσθετοι ορισμοί

    Προτάσεις σε συνεκτικούς μη κυκλικούς γράφους

    Οι παρακάτω προτάσεις είναι ισοδύναμες για πεπερασμένους γράφους με ν > 0 κόμβους:
    1. Ο γράφος Γ είναι συνεκτικός και μη κυκλικός.
    2. Αν διαγραφεί οποιαδήποτε ακμή ο γράφος θα πάψει να είναι συνεκτικός.
    3. Δύο διαφορετικοί κόμβοι συνδέονται από μια και μόνο μια απλή διαδρομή.
    4. Ο γράφος είναι μη κυκλικός και περιέχει ν - 1 ακμές.
    5. Ο γράφος είναι συνεκτικός και περιέχει ν - 1 ακμές.

    Ψάξιμο κατά βάθος

    Για να επισκευθούμε όλους τους κόμβους ενός γράφου με ν κόμβους χρειαζόμαστε έναν πίνακα λογικών μεταβλητών μιας διάστασης και μήκους ν ο οποίος περιέχει την τιμή "αληθές" για τους κόμβους τους οποίους έχουμε επισκευθεί. Η συστηματική επίσκεψη όλων των κόμβων γίνεται σύμφωνα με τα παρακάτω βήματα:
    1. Φυλάμε την τιμή "ψευδές" στον πίνακα επισκέψεων.
    2. Επισκεπτόμαστε όλους τους κόμβους που δεν έχουμε επισκευτεί.

    Η επίσκεψη ενός κόμβου γίνεται σύμφωνα με τα παρακάτω βήματα:
    1. Σημειώνουμε στον πίνακα ότι έχουμε επισκευθεί τον κόμβο.
    2. Επισκεπτόμαστε όλους τους συνδεδεμένους κόμβους που δεν έχουμε επισκευθεί.
    Το παρακάτω παράδειγμα περιέχει υλοποίηση για λίστα γειτνίασης: 
    #include <stdlib.h>
#include <stdio.h>

/*
 * Adjacency list for a graph of 10 nodes
 */
struct s_adjlist {
	int node;
	struct s_adjlist *next;
};

static struct s_adjlist *adj[10];
static int visited[10];

/*
 * Visit the nodes starting from node printing their value using
 * depth first search 
 */
static void
visit(int node)
{
	struct s_adjlist *p;

	visited[node] = 1;
	printf("%d\n", node);
	for (p = adj[node]; p != NULL; p = p->next)
		if (!visited[p->node])
			visit(p->node);
}

main()
{
	int a, b;
	struct s_adjlist *p;
	int i;

	/* Read edges and connect them */
	while (scanf("%d %d", &a, &b) == 2) {
		p = (struct s_adjlist *)malloc(sizeof(struct s_adjlist));
		p->node = b;
		p->next = adj[a];
		adj[a] = p;
		p = (struct s_adjlist *)malloc(sizeof(struct s_adjlist));
		p->node = a;
		p->next = adj[b];
		adj[b] = p;
	}
	/* Depth first search/print of the graph */
	for (i = 0; i < 10; i++)
		visited[i] = 0;
	for (i = 0; i < 10; i++)
		if (!visited[i])
			visit(i);
}
    Αν το πρόγραμμα διαβάσει το γράφο: 
    2 3
3 8
8 6
4 9
    θα τυπώσει την παρακάτω σειρά επίσκεψης: 
    0
1
2
3
8
6
4
9
5
7

    Εφαρμογές

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

    Αναζήτηση και ταξινόμηση

    Ταξινόμηση

    Ταξινόμηση με παρεμβολή

    Ταξινόμηση με επιλογή

    Ταξινόμηση με αντιμετάθεση

    Ταξινόμηση με διαμερισμό και αντιμετάθεση

    Παράδειγμα

    Το παρακάτω παράδειγμα ταξινομεί το πίνακα ακεραίων ivals και τυπώνει το αποτέλεσμα: 
    #include <stdlib.h>
#include <stdio.h>

/*
 * Integer compare function (passed to qsort)
 */
static int
icmp(const void *arg1, const void *arg2)
{
	return (*(int *)arg1 - *(int *)arg2);
}

main()
{
	int ivals[] = {100, 5, 6, 2, 8, 3, 45, 23};
	int i;

	qsort((void *)ivals, sizeof(ivals) / sizeof(int), sizeof(int), icmp);
	for (i = 0; i < sizeof(ivals) / sizeof(int); i++)
		printf("%d\n", ivals[i]);
}

    Αναζήτηση

    Σειριακή αναζήτηση

    Δυαδική αναζήτηση

    Παράδειγμα

    Το παρακάτω παράδειγμα διαβάζει μια γραμμή και την τυπώνει σύμφωνα με το διεθνές φωνητικό αλφάβητο (π.χ. για τη γραμμή HELLO WORLD θα τυπώσει: 
    Hotel
Echo
Lima
Lima
Oscar
Whiskey
Oscar
Romeo
Lima
Delta

    /*
 * Read a line from the standard input and print it according to the
 * international phonetic alphabet.
 *
 * Diomidis Spinellis.  March 1999.
 *
 * $Id$
 *
 */

#include <stdlib.h>
#include <stdio.h>

/*
 * The international phonetic alphabet (sorted)
 */
char *names[] = {
	"Alpha",
	"Bravo",
	"Charlie",
	"Delta",
	"Echo",
	"Foxtrot",
	"Golf",
	"Hotel",
	"India",
	"Juliet",
	"Kilo",
	"Lima",
	"Mike",
	"November",
	"Oscar",
	"Papa",
	"Quebec",
	"Romeo",
	"Sierra",
	"Tango",
	"Uniform",
	"Victor",
	"Whiskey",
	"X-Ray",
	"Yankee",
	"Zulu",
};

/*
 * Bsearch compare function
 */
static int
namecmp(char **a, char **b)
{
	return (**a - **b);
}

main()
{
	char buff[80], *p, **name;

	fgets(buff, sizeof(buff), stdin);
	for (p = buff; *p; p++)
		if (name = (char **)bsearch(&p, names, 26, sizeof(char *), namecmp))
			printf("%s\n", *name, *name);
}

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

    Ασκήσεις

    Άσκηση 6

    1. Να υλοποιηθεί σε C πρόγραμμα το οποίο διαβάζει ονόματα και τηλέφωνα μέχρι να συναντήσει το όνομα "ΤΕΛΟΣ". Στη συνέχεια, για κάθε επόμενο όνομα που διαβάζει, τυπώνει το αντίστοιχο τηλέφωνο, ή τη λέξη ΑΓΝΩΣΤΟΣ αν δεν υπάρχει. Το πρόγραμμα να υλοποιηθεί με τη χρήση των qsort και bsearch.

      Παράδειγμα: 

      Γιάννης
031343454
Φανή
027354566
Θανάσης
014645678
Αλέξανδρος
56789
Γεωργία
034556789
ΤΕΛΟΣ
Σωτήρης
ΑΓΝΩΣΤΟΣ
Φανή
027354566

      Σημείωση: Η σύγκριση για τη λέξη "ΤΕΛΟΣ" μπορεί να γίνει ως εξής: 
      if (strcmp(buff, "END\n") == 0) ...

    Κατακερματισμός

    Εισαγωγή

    Ορισμοί

    Σε ένα σύστημα κατακερματισμού μπορούμε να ορίσουμε τα παρακάτω:

    Συναρτήσεις κατακερματισμού

    Η συνάρτηση κατακερματισμού πρέπει να εκτελείται γρήγορα και να είναι κατά το δυνατό ομοιόμορφη. Οι παρακάτω είναι μερικές ενδεικτικές μέθοδοι υλοποίησης: Οι παραπάνω μέθοδοι μπορούν να χρησιμοποιηθούν και σε συνδυασμό.

    Διαχείριση συγκρούσεων

    Σε περίπτωση που σημειωθεί μια σύγκρουση υπάρχουν οι παρακάτω επιλογές:

    Υλοποίηση σε C

    Ο ορισμός της γλώσσας προγραμματισμού C εγγυάται ότι οι αριθμητικές και λογικές πράξεις μη προσημασμένων ακεραίων (π.χ. unsigned int) γίνονται πάντα με υπερχείλιση modulo ν όπου ν ο αριθμός των bits που χρησιμοποιείται για τη φύλλαξη των αριθμών.

    Ο παρακάτω πίκανας απεικονίζει τους αντίστοιχους αριθμούς ν στην αρχιτεκτονική Intel Pentium:
    Τύποςν (bits)
    unsigned char8
    unsigned short16
    unsigned int32
    unsigned long32

    Έτσι για παράδειγμα σε πρόσθεση δύο τιμών τύπου unsigned char 250 + 10 το αποτέλεσμα θα είναι 4 μια και 260 mod 2 8 = 4. Η ιδιότητα αυτή σε συνδυασμό με τις πράξεις πάνω σε bits που ορίζει η C μας επιτρέπει να ορίζουμε εύκολα συναρτήσεις κατακερματισμού.

    Οι τελεστές για πράξεις πάνω σε bits ακεραίων αριθμών είναι οι παρακάτω:
    ΤελεστήςΠράξη
    |σύζευξη (or)
    &διάζευξη (and)
    ^αποκλειστική διάζευξη (exclusive or)
    ~άρνηση (negation)
    Μια συνάρτηση κατακερματισμού συμβολοσειράς σε τιμή 0-127 με βάση την αποκλειστική διάζευξη μπορεί να υλοποιηθεί ως εξής: 

    unsigned int
hash(unsigned char string)
{
	char *s;
	unsigned char sum = 0;

	for (*s = string; *s; s++)
		sum ^= *s;
	return (sum & 127);
}

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

    Ασκήσεις

    Άσκηση (προαιρετική)

    1. Να υλοποιηθεί σε C πρόγραμμα το οποίο διαβάζει 5 ακεραίους και τους αποθηκεύει με κατακερματισμό σε πίνακα 50 θέσεων. Στην συνέχεια ζητάει κατ' εξακολούθηση από το χρήστη να δώσει έναν ακέραιο αριθμό και τυπώνει στην οθόνη αν ο αριθμός αυτός ήταν ανάμεσα στους 5 ή όχι. Το ενδεχόμενο της υπερχείλισης να μην εξεταστεί.

      Παράδειγμα: 

      454
3466
456
23
199
Give number: 123
Not known
Give number: 456
Known

    Τεχνικές αρχείων

    Βοηθητική μνήμη

    Αρχεία

    Επεξεργασία σειριακών αρχείων

    Αρχεία τυχαίας προσπέλασης

    Επεξεργασία αρχείων στη C

    Η επεξεργασία αρχείων στη C γίνεται με βάση συναρτήσεις του αφηρημένου τύπου δεδομένων FILE * που ορίζονται στην επικεφαλίδα stdio.h. Για να αποκτήσει το πρόγραμμα πρόσβαση σε ένα αρχείο πρέπει να καλέσει τη συνάρτηση:
    fopen(μονοπάτι αρχείου, τύπος πρόσβασης)

    Η συνάρτηση επιστρέφει μια τιμή τύπου FILE * την οποία το πρόγραμμα χρησιμοποιεί για πρόσβαση στο αρχείο. Αν η πρόσβαση στο αρχείο δεν είναι δυνατή (π.χ. το αρχείο στο οποίο ζητήθηκε ανάγνωση δεν υπάρχει, ένας κατάλογος από το μονοπάτι δεν υπάρχει, το αρχείο το οποίο ζητήθηκε εγγραφή δεν το επιτρέπει) τότε η συνάρτηση fopen επιστρέφει την τιμή NULL.

    Ο τύπος πρόσβασης μπορεί να είναι ένας από τους παρακάτω:
    Τύπος πρόσβασηςΠρόσβαση
    "r"Ανάγνωση (read)
    "w"Εγγραφή (write)
    "a"Προσθήκη (append)
    "r+w"Ανάγνωση και εγγραφή

    Στο τέλος της επεξεργασίας του αρχείου πρέπει να καλέσουμε τη συνάρτηση fclose(f) (όπου f η τιμή που επέστρεψε η fopen) για να δηλώσουμε στη βιβλιοθήκη και το λειτουργικό σύστημα να απελευθερώσουν τους πόρους που είχαν δεσμευτεί για την επεξεργασία του αρχείου.

    Σειριακή επεξεργασία αρχείων ASCII στη C

    Η σειριακή επεξεργασία αρχείων που περιέχουν χαρακτήρες ASCII στη μορφή που τους διαβάζουν και γράφουν οι άνθρωποι γίνεται με βάση τις παρακάτω συναρτήσεις:
    fprintf(FILE *stream, char *format, ...)
    Τυπώνει φορμαρισμένα σε αρχείο.
    fscanf(FILE *stream, char *format, ...)
    Διαβάζει φορμαρισμένα από αρχείο.
    fgetc(FILE *stream)
    Διαβάζει έναν χαρακτήρα από αρχείο.
    fputc(char c, FILE *stream)
    Γράφει έναν χαρακτήρα σε αρχείο.
    feof(FILE *stream)
    Επιστρέφει αληθές αν έχει ανιχνευτεί το τέλος του αρχείου.
    Οι παραπάνω συναρτήσεις είναι αντίστοιχες με τις printf, scanf, getchar, putchar, μόνο που αντί για την είσοδο και έξοδο του προγράμματος δουλεύουν σε αρχεία.

    Το παρακάτω πρόγραμμα γράφει στο αρχείο codes.txt τους χαρακτήρες ASCII που διαβάζονται και τους αντίστοιχους κωδικούς τους: 

    #include <stdio.h>

main()
{
	FILE *f;
	int i;

	f = fopen("codes.txt", "w");
	for (i = ' '; i < '~'; i++)
		fprintf(f, "Character: %c  code:%d\n", i, i);
	fclose(f);
}

    Σημείωση: οι συναρτήσεις getc και putc είναι γρήγορες εκδόσεις των gfetc και fputc.

    Σειριακή επεξεργασία κωδικοποιημένων αρχείων στη C

    Για λόγους απόδοσης συχνά τα αρχεία δεν περιέχουν παράσταση των τιμών των δεδομένων με τη μορφή που τα εισάγουν και τα διαβάζουν οι άνθρωποι (αρχεία ASCII (ASCII files)), αλλά με τη μορφή που φυλάσσονται στη μνήμη του υπολογιστή (δυαδικά αρχεία (binary files)). Ο τρόπος αυτός φύλλαξης έχει τις παρακάτω επιπτώσεις: Μεταφορά στοιχείων μεταξύ της κεντρικής μνήμης και αρχείων γίνεται με τις συναρτήσεις:
    fread(void *ptr, size_t size, size_t nitems, FILE *stream)
    Μεταφέρει nitems στοιχεία μεγέθους size από το αρχείο f στη θέση μνήμης ptr.
    fwrite(void *ptr, size_t size, size_t nitems, FILE *stream)
    Μεταφέρει nitems στοιχεία μεγέθους size από τη θέση μνήμης ptr στο αρχείο f.
    Το παρακάτω παράδειγμα γράφει τον πίνακα tbl στο αρχείο f: 
    	int tbl[100];

	fwrite(tbl, sizeof(int), 100, f);

    Επεξεργασία αρχείων τυχαίως προσπέλασης στη C

    Η βιβλιοθήκη της C μας δίνει τη δυνατότητα μετακίνησης και σε τυχαία σημεία του αρχείου με βάση τις συναρτήσεις fseek και ftell:
    int fseek(FILE * f, long pos, int whence);
    Ορίζει ως επόμενη θέση για ανάγνωση ή εγγραφή στο αρχείο f τη θέση pos. Η θέση ορίζεται ανάλογα με τη σταθερά που θα οριστεί στη whence:
    SEEK_CUR
    από την τρέχουσα θέση στο αρχείο,
    SEEK_END
    από το τέλος του αρχείου,
    SEEK_SET
    από την αρχή του αρχείου.
    Η fseek επιστρέφει -1 αν η θέση που δώθηκε δεν είναι σωστή, αλλιώς επιστρέφει 0. Το παρακάτω παράδειγμα μεταφέρει τη θέση ανάγνωσης στον 10ο ακέραιο του αρχείου f: 
    	fseek(f, 10 * sizeof(int), SEEK_SET);
    long ftell(FILE *f)
    Επιστρέφει την τρέχουσα θέση ανάγνωσης/εγγραφής στο αρχείο f.

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

    Ασκήσεις

    Άσκηση 7

    1. Να υλοποιηθεί σε C το πρόγραμμα addphone το οποίο ζητά από το χρήστη ένα όνομα και ένα τηλέφωνο και τα προσθέτει σε αρχείο καθώς και το πρόγραμμα getphone το οποίο ζητά από το χρήστη ένα όνομα και αν αυτό βρίσκεται στο αρχείο τυπώνει το τηλεφωνό του.
      Παράδειγμα: 
      C>addphone
Name:EKAB
Phone:166

C>getphone
Name:EKAB
Phone=166

    Αντικείμενα στη C++

    Εισαγωγή

    Το πρώτο πρόγραμμα σε C++

    Το πρώτο πρόγραμμα σε C++ θα τυπώσει, όπως θα περίμενε κανείς, τις λέξεις hello, world: 
    #include <iostream.h>

main()
{
	cout << "hello, world\n";
}

    Μεταγλώττιση

    Στο περιβάλλον του εργαστηρίου (Windows NT, Visual C++) το πρόγραμμα πρέπει να έχει επίθεμα .cpp αντί για .c για να το αναγνωρίσει ο μεταγλωττιστής ως πρόγραμμα C++. Ο μεταγλωττιστής παραμένει ο ίδιος (cl).

    Σε εγκαταστάσεις Linux το πρόγραμμα πρέπει να έχει επίθεμα .C. Για να μεταγλωττιστεί χρησιμοποιούμε την εντολή g++.

    C++ ως καλύτερη C

    Η C++ προσφέρει πρόσθετες δυνατότητες σε προγράμματα C:

    Ορισμός κλάσεων

    Καθοριζόμενοι τελεστές

    Είσοδος και έξοδος

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

    Πηγές στο Internet

    Άσκηση

    Άσκηση 8

    1. Να υλοποιηθεί σε C++ η κλάση της ουράς ακεραίων int_queue σύμφωνα με τις παρακάτω συναρτήσεις:
      Δημιουργεί μια άδεια ουρά size στοιχείων
      int_queue(int size);
      Το στοιχείο i εισάγεται στο τέλος της ουράς
      void put_int_queue(int i);
      Το στοιχείο από την αρχή της μη κενής ουράς αφαιρείται και επιστρέφεται
      int get_int_queue();
      Επιστρέφεται αληθές αν η ουρά είναι κενή
      int isempty_int_queue();
    2. Με βάση τον αφηρημένο αυτό τύπο και μονοτονικά αυξανόμενη μεταβλητή να υλοποιηθεί πρόγραμμα το οποίο να υλοποιεί ουρά εξυπηρέτησης πελατών ως εξής:
      1. Όταν εισάγεται ο χαρακτήρας I (In) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του νέου πελάτη.
      2. Όταν εισάγεται ο χαρακτήρας O (Out) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του επόμενου πελάτη που θα εξυπηρετηθεί.
      Παράδειγμα: 
      I
1
I
2
I
3
O
1
I
4
O
2
...
      Παρατήρηση: Το πρόγραμμα μπορεί να δομηθεί γύρω από τον παρακάτω κώδικα εισόδου: 
      #include <iostream.h>

main()
{
	char c;
	// Initializations here

	for (;;) {
		cin >> c;
		switch (c) {
		case 'I':
			// Process input here
			break;
		case 'O':
			// Process output here
			break;
		}
	}
}

    Κληρονομικότητα

    Εισαγωγή

    Κληρονομικότητα σε κλάσεις

    Ιδεατές συναρτήσεις

    Παράδειγμα

    Το παρακάτω παράδειγμα ορίζει τη βασική κλάση shape και τις υποκλάσεις της circle και rectangle. Η μέθοδος area ορίζεται ως virtual με αποτέλεσμα να μπορεί να οριστεί για τις υποκλάσεις και κατά την εκτέλεση του προγράμματος να εκτελεστεί η σωστή έκδοσή της. Η συνάρτηση printarea της shape εκμεταλλεύεται τη δυνατότητα αυτή και μπορεί να κληθεί (και να δουλέψει σωστά) με όρισμα οποιαδήποτε από τις υποκλάσεις της shape. 
    #include <iostream.h>

class shape {
private:
	double x, y;		// Position
public:
	void setposition(double x, double y);
	void printarea();
	virtual double area();
};

double
shape::area()
{
	return (0);
}

void
shape::printarea()
{
	cout << area() << "\n";
}


void shape::setposition(double x, double y)
{
	shape::x = x;
	shape::y = y;
}

class circle : public shape {
private:
	double radius;
public:
	void setradius(double r);
	virtual double area();
};

void
circle::setradius(double r)
{
	radius = r;
}

double
circle::area()
{
	return (3.1415927 * radius * radius);
}


class rectangle : public shape {
private:
	double height, width;
public:
	void setdimensions(double h, double w);
	virtual double area();
};

void
rectangle::setdimensions(double h, double w)
{
	height = h;
	width = w;
}

double
rectangle::area()
{
	return (height * width);
}

main()
{
	circle c;
	rectangle r;
	shape *sp;

	r.setposition(1, 2);
	c.setposition(3, 4);
	r.setdimensions(10, 10);
	c.setradius(1);
	c.printarea();
	r.printarea();
	sp = &r;
	cout << sp->area();
}

    Αφηρημένες κλάσεις

    Για παράδειγμα, ένας σχεδιασμός του πληροφοριακού συστήματος του Πανεπιστημίου μπορεί να ορίσει την αφηρημένη κλάση person ως βασική κλάση για τις υποκλάσεις student, employee και visitor. Αν και δε θα μπορεί να οριστεί μια μεταβλητή για την αφηρημένη κλάση person, αυτή μπορεί να περιέχει ορισμένα βασικά χαρακτηριστικά όπως birth_date και να επιβάλει την υλοποίηση συγκεκριμένων μεθόδων όπως home_page_URL() ορίζοντάς τις ως θεωρητικές.

    Πρότυπα στη C++ και δείκτες σε μέλη

    Παραμετροποίηση προγραμμάτων με πρότυπα

    Η C++ μας επιτρέπει να δηλώσουμε και να ορίσουμε συναρτήσεις και κλάσεις παραμετροποιημένες ως προς τους τύπους ή τις σταθερές που χρησιμοποιούν. Βάση για τους ορισμούς αυτούς είναι ένα πρότυπο (template). Έχοντας ορίσει μια συνάρτηση ή μια κλάση με μορφή προτύπου μπορούμε στη συνέχεια να τη χρησιμοποιήσουμε για κάποιο συγκεκριμένο τύπο ή σταθερά. Η χρήση αυτή γίνεται αυτόματα μέσα στον πηγαίο κώδικα. Το παρακάτω παράδειγμα ορίζει και χρησιμοποιεί μια συνάρτηση max παραμετροποιημένη ως προς τον τύπο των παραμέτρων και του αποτελέσματός της: 
    #include <iostream.h>

/*
 * Return the maximum of a, b.
 * A, b and the return type of max are of type T.
 */
template <class T>
T
max(T a, T b)
{
	if (a > b)
		return (a);
	else
		return (b);
}

main()
{
	cout << max("Samos", "Zambia") << "\n";
	cout << max(3, 42) << "\n";
	cout << max(3.1415, 1.4142) << "\n";
}
    Χρησιμοποιούμε πρότυπα: Σε αντίθεση με πολυμορφικές συναρτήσεις που ορίζονται με υπερφόρτιση, συναρτήσεις που ορίζονται με πρότυπα απαιτούν έναν μόνο ορισμό για όλους τους πιθανούς τύπους. Ο μεταγλωττιστής αυτόματα υλοποιεί την κάθε συνάρτηση για το συγκεκριμένο τύπο που χρησιμοποιείται. Με τη χρήση των προτύπων αυξάνουμε την ευελιξία του κώδικα που γράφουμε και μειώνουμε το μέγεθος του κώδικα που απαιτείται για μια συγκεκριμένη υλοποίηση.

    Ο ορισμός του προτύπου περιέχει μετά τη δεσμευμένη λέξη template μια σειρά τύπων ή παραμέτρων μέσα σε < > που χρησιμοποιούμε για να ορίσουμε τη συγκεκριμένη συνάρτηση ή κλάση. Οι τύποι και οι παράμετροι χωρίζονται μεταξύ τους με κόμμα. Οι τύπου μπορούν να οριστούν ως class όνομα_κλάσης (π.χ. class T) ή ως typename όνομα_τύπου (π.χ. typename T). Οι παράμετροι ορίζονται όπως και στις συναρτήσεις (π.χ. int stacksize). Μέσα στη δήλωση της συνάρτησης ή της κλάσης καθώς και στον ορισμό του σώματός τους μπορούμε να χρησιμοποιήσουμε τα ονόματα που δηλώθηκαν με βάση το πρότυπο σαν να ήταν πραγματικοί τύποι ή σταθερές. Κατά τη χρήση μια κλάσης ή συνάρτησης οι παράμετροι πρέπει να είναι σταθερές.

    Το παρακάτω παράδειγμα δηλώνει την πρότυπη κλάση tstack ως μια στοίβα της οποίας ο τύπος των στοιχείων και το μέγεθος ορίζονται με βάση το πρότυπό της και το αντικείμενο instack ως μια στοίβα 20 ακεραίων: 

    template <class T, int i> class tstack
{
	T data[i];
	int items;
public:
	tstack(void);
	void push(T item);
	T pop(void);
};

tstack <int, 20> intstack;

    Η υλοποίηση προτύπων που χρησιμοποιούμε (Microsoft Visual C++ 5.0) απαιτεί ο ορισμός του προτύπου να είναι στο ίδιο αρχείο με τη χρήση του. Για το λόγο αυτό οι κλάσεις και οι συναρτήσεις που ορίζονται με βάση τα πρότυπα ορίζονται και δηλώνονται μέσα σε αρχείο επικεφαλίδων.

    Πρότυπα συναρτήσεων

    Πρότυπα κλάσεων

    Δείκτες σε μέλη κλάσεων

    Η βιβλιοθήκη της C++

    Η βιβλιοθήκη της C++

    Η βιβλιοθήκη της C++ μπορεί να χωριστεί στις παρακάτω κατηγορίες:
    1. Γενικές λειτουργίες
    2. Λειτουργίες μετατροπής και αρχείων (iostreams)
    3. Αλγόριθμοι με τη χρήση ενός επαναλήπτη (iterator) πάνω σε έναν περιέχοντα (container). Οι λειτουργίες αυτές αποτελούν τη βιβλιοθήκη με το όνομα Standard Template Library (STL).
    4. Συμβατότητα με τη C
    Οι τρεις πρώτες κατηγορίες της βιβλιοθήκης ορίζονται σε επικεφαλίδες χωρίς το επίθεμα .h. Για να μην υπάρχει πιθανότητα τα ονόματα που ορίζονται στις επικεφαλίδες να ταυτίζονται με ονόματα που ορίζει ο χρήστης, τα ονόματα που ορίζουν οι επικεφαλίδες αυτές βρίσκονται απομονωμένα σε έναν ξεχωριστό χώρο ονομάτων (namespace) με το πρόθεμα "std::". Για να τα χρησιμοποιήσουμε στο πρόγραμμά μας χωρίς το πρόθεμα αυτό μπορούμε μετά τις επικεφαλίδες να δηλώσουμε: 
    using namespace std;
    Στις επόμενες ενότητες περιγράφουμε συνοπτικά μόνο τις γενικές λειτουργίες της βιβλιοθήκης και με περισσότερες λεπτομέρειες τις λειτουργίες της STL.

    Γενικές λειτουργίες

    Η γενικές λειτουργίες της βιβλιοθήκης της C++ είναι οι παρακάτω:
    bitset
    κλάση προτύπων (ως προς το μέγιστο πληθάριθμο του συνόλου) που επεξεργάζεται σύνολο από bit
    complex
    κλάση προτύπων (ως προς τον τύπου των δύο στοιχείων) μιγαδικών αριθμών. Εξειδικεύσεις της κλάσης είναι μιγαδικοί αριθμοί float, double και long double.
    exception
    συναρτήσεις χειρισμού διακοπών
    limits
    ιδιότητες αριθμητικών τιμών
    locale
    προσαρμογή του προγράμματος σε τοπικά χαρακτηριστικά. Περιλαμβάνονται πρότυπες κλάσεις που ορίζουν:
    • τον τρόπο μετατροπής μεταξύ χαρακτήρων
    • τη σειρά ταξινόμησης
    • το χαρακτηρισμό χαρακτήρων
    • τη μετατροπή νομισματικών τιμών
    • τη μετατροπή αριθμητικών τιμών
    • τη μετατροπή τιμών που παριστάνουν χρόνο
    • τη μετατροπή μηνυμάτων προς το χρήστη
    stdexcept
    κλάσεις για αναφορά διακοπών
    string
    πρότυπη κλάση που ορίζει σειρές αντικειμένων μεταβλητού μήκους. Εξειδίκευση της κλάσης αυτής είναι οι συμβολοσειρές.
    valarray
    πρότυπη (ως προς το περιεχόμενο του πίνακα) κλάση που επιτρέπει το μαζικό χειρισμό πινάκων

    Λειτουργίες μετατροπής και αρχείων

    Οι επικεφαλίδες iostreams υποστηρίζουν τη μετατροπή μεταξύ κειμένων και της εσωτερική μορφή παράστασης των τύπων καθώς και είσοδο και έξοδο από και σε εξωτερικά αρχεία. Ορίζονται οι παρακάτω επικεφαλίδες:
    fstream
    πρότυπες κλάσεις iostreams για το χειρισμό εξωτερικών αρχείων
    iomanip
    δήλωση χειριστών iostreams
    ios
    βασική κλάση προτύπων iostreams
    iosfwd
    δήλωση προτύπων κλάσεων iostreams πριν από τον ορισμό τους
    iostream
    δήλωση των βασικών αντικειμένων iostreams
    istream
    πρότυπη κλάση που εξάγει στοιχεία
    ostream
    πρότυπη κλάση που εισάγει στοιχεία
    sstream
    πρότυπες κλάσεις iostreams που αναφέρονται σε συμβολοσειρές
    streambuf
    πρότυπες κλάσεις που προσφέρουν ενταμιευτές σε κλάσεις iostreams
    strstream
    κλάσεις iostreams που λειτουργούν σε στοιχεία που βρίσκονται στη μνήμη

    Περιέχοντες και επαναλήπτες στην STL

    Η STL ορίζει μια σειρά από περιέχοντες (containers) όπως την ουρά, τη στοίβα, την απεικόνιση και τον πίνακα. Πάνω στους περιέχοντες αυτούς επιτρέπει την εκτέλεση αλγορίθμων, όπως την εύρεση ενός στοιχείου, η ένωση δύο περιεχόντων, η ταξινόμηση, κ.λπ.

    Στην STL ορίζονται οι παρακάτω πρότυποι (ως προς τα στοιχεία που περιέχουν) περιέχοντες:

    list
    διπλά συνδεδεμένη λίστα
    queue
    ουρά
    deque
    ουρά με πρόσβαση και στις δύο άκρες
    map
    απεικόνιση (π.χ. από συμβολοσειρές σε ακέραιους)
    set
    απεικόνιση με μοναδικά στοιχεία στο πεδίο τιμών
    stack
    στοίβα
    vector
    πίνακας
    Η πρόσβαση των στοιχείων ενός περιέχοντα από τους αλγορίθμους γίνεται μέσω επαναληπτών (iterators). Οι επαναλήπτες - ανάλογα με τη δομή των δεδομένων του περιέχοντα - μπορούν να επιτρέπουν την παρακάτω ιεραρχία κινήσεων: Επίσης, μπορούν να επιτρέπουν την παρακάτω ιεραρχία πρόσβασης στα δεδομένα που δείχνουν: Η κλάση των επαναληπτών ορίζεται στην επικεφαλίδα iterator. Μερικές μέθοδοι που ορίζονται σε επαναλήπτες είναι οι παρακάτω: Για κάθε περιέχοντα ορίζονται μέθοδοι όπως (στην περίπτωση της διπλής ουράς):
    assign
    ανάθεση τιμής
    at
    αναφορά σε στοιχείο
    back
    το τελευταίο στοιχείο
    begin
    επαναλήπτης που δείχνει στην αρχή της δομής
    clear
    διαγραφή όλων των στοιχείων
    empty
    αληθές αν η δομή είναι άδεια
    end
    επαναλήπτης που δείχνει στο τέλος της δομής
    erase
    διαγραφή σειράς στοιχείων
    front
    το πρώτο στοιχείο
    insert
    προσθήκη στοιχείου
    operator[]
    πρόσβαση σε στοιχείο
    pop_back
    αφαίρεση στοιχείου από το τέλος
    pop_front
    αφαίρεση στοιχείου από την αρχή
    push_back
    προσθήκη στοιχείου στο τέλος
    push_front
    προσθήκη στοιχείου στην αρχή
    rbegin
    ανάστροφος επαναλήπτης που δείχνει στην αρχή της δομής
    rend
    ανάστροφος επαναλήπτης που δείχνει στο τέλος της δομής
    resize
    καθορισμός του αριθμού των στοιχείων
    size
    αριθμός των στοιχείων
    swap
    εναλλαγή δύο στοιχείων μεταξύ τους
    Το παρακάτω παράδειγμα ορίζει μια διπλή ουρά ακεραίων, προσθέτει 5 στοιχεία και τα τυπώνει: 
    #include <iostream>
#include <deque>

using namespace std;


typedef deque <int>  INTDEQUE;

void main()
{

	// Create A and fill it with elements 1,2,3,4 and 5
	// using push_back function
	INTDEQUE  A;

	A.push_back(1);
	A.push_back(2);
	A.push_back(3);
	A.push_back(4);
	A.push_back(5);

	// Print the contents of A using iterator
	// and functions begin() and end()
	INTDEQUE::iterator pi;

	for (pi = A.begin();  pi != A.end(); pi++)
		cout << *pi << " ";
	cout << "\n";
}

    Πρόσθετες λειτουργίες στην STL

    Επικεφαλίδα algorithm

    Στην επικεφαλίδα algorithm ορίζονται μέθοδοι που ενεργούν πάνω σε περιέχοντες:
    adjacent_find
    βρίσκει δύο ίσα στοιχεία σε διπλανές θέσεις
    binary_search
    δυαδική ανίχνευση
    copy
    αντιγραφή περιοχής
    copy_backward
    αντίστροφη αντιγραφή περιοχής
    count
    μέτρημα
    count_if
    μέτρημα υπό συνθήκη
    equal
    σύγκριση περιοχών
    equal_range
    σύγκριση περιοχών με συγκεκριμένη ακρίβεια
    fill
    πλήρωση περιοχής με τιμή
    fill_n
    πλήρωση αριθμού στοιχείων με τιμή
    find
    εύρεση στοιχείου
    find_end
    εύρεση στοιχείου από το τέλος
    find_first_of
    εύρεση στοιχείου ίσου με κάποιο μέλος από σύνολο στοιχείων
    find_if
    εύρεση στοιχείου που να ικανοποιεί συνθήκη
    for_each
    εκτέλεση συνάρτησης για όλα τα στοιχεία σε περιοχή
    generate
    πλήρωση περιοχής με αποτέλεσμα συνάρτησης
    generate_n
    πλήρωση αριθμού στοιχείων με αποτέλεσμα συνάρτησης
    includes
    έλεγχος αν μια περιοχή εμπεριέχει μια άλλη
    inplace_merge
    σύζευξη δεδομένων στον ίδιο περιέχοντα
    iter_swap
    εναλλαγή δύο τιμών
    lexicographical_compare
    σύγκριση δύο περιοχών α, β για α < β
    lower_bound
    εύρεση μιας ελάχιστης τιμής σε περιοχή σε σχέση με μιαν άλλη τιμή
    make_heap
    μετατροπή περιοχής σε σωρό (heap) (δυαδικό δένδρο στο οποίο τα παιδιά έχουν τιμή μικρότερη ή ίση από αυτή των γονέων τους).
    max
    το μέγιστο από δύο στοιχεία
    max_element
    εύρεση του μέγιστου στοιχείου σε περιοχή
    merge
    σύζευξη δύο περιοχών σε τρίτη
    min
    το ελάχιστο από δύο στοιχεία
    min_element
    εύρεση του ελαχίστου στοιχείου σε περιοχή
    mismatch
    εύρεση του πρώτου διαφορετικού στοιχείου ανάμεσα σε δύο περιοχές
    next_permutation
    υπολογισμός της επόμενης μετάθεσης σε μια περιοχή
    nth_element
    θέτει ένα στοιχείο στη θέση που θα έπρεπε να έχει αν η περιοχή ήταν ταξινομημένη
    partial_sort
    ταξινομεί τα πρώτα στοιχεία μιας περιοχής
    partial_sort_copy
    ταξινομεί τα πρώτα στοιχεία μιας περιοχής σε μιαν άλλη
    partition
    χωρίζει μια περιοχή στα δύο με βάση μια συνάρτηση και επιστρέφει το σημείο που είναι ο χωρισμός
    pop_heap
    αφαίρεση στοιχείου από σωρό
    prev_permutation
    υπολογισμός της προηγούμενης μετάθεσης σε μια περιοχή
    push_heap
    προσθήκη στοιχείου από σωρό
    random_shuffle
    ανακατεύει μια περιοχή
    remove
    αφαιρεί στοιχεία ίσα με μια τιμή
    remove_copy
    αφαιρεί στοιχεία ίσα με μια τιμή μεταφέροντας το αποτέλεσμα σε μιαν άλλη περιοχή
    remove_copy_if
    αφαιρεί στοιχεία για τα οποία μια συνάρτηση είναι αληθής μεταφέροντας το αποτέλεσμα σε μιαν άλλη περιοχή
    remove_if
    αφαιρεί στοιχεία για τα οποία μια συνάρτηση είναι αληθής
    replace
    αλλάζει τιμή σε στοιχεία ίσα με μια τιμή
    replace_copy
    αλλάζει τιμή σε στοιχεία ίσα με μια τιμή μεταφέροντας το αποτέλεσμα σε μιαν άλλη περιοχή
    replace_copy_if
    αλλάζει τιμή σε στοιχεία για τα οποία μια συνάρτηση είναι αληθής μεταφέροντας το αποτέλεσμα σε μιαν άλλη περιοχή
    replace_if
    αλλάζει τιμή σε στοιχεία για τα οποία μια συνάρτηση είναι αληθής
    reverse
    αντιστρέφει τη σειρά σε μια περιοχή
    reverse_copy
    αντιστρέφει τη σειρά σε μια περιοχή μεταφέροντάς την σε μιαν άλλη περιοχή
    rotate
    περιστρέφει τη σειρά των στοιχείων σε μια περιοχή
    rotate_copy
    περιστρέφει τη σειρά των στοιχείων σε μια περιοχή μεταφέροντάς την σε μιαν άλλη περιοχή
    search
    εύρεση σειράς στοιχείων σε μια περιοχή ίσης με στοιχεία μιας άλλης
    search_n
    εύρεση σειράς στοιχείων σε μια περιοχή ίσης με αριθμό στοιχείων μιας άλλης
    set_difference
    θέτει μια περιοχή ίση με τη διαφορά των στοιχείων δύο άλλων περιοχών (διαφορά συνόλων)
    set_intersection
    θέτει μια περιοχή ίση με την τομή των στοιχείων δύο άλλων περιοχών (τομή συνόλων)
    set_symmetric_difference
    θέτει μια περιοχή ίση με τα μη κοινά των στοιχείων δύο άλλων περιοχών
    set_union
    θέτει μια περιοχή ίση με την ένωση των στοιχείων δύο άλλων περιοχών (ένωση συνόλων)
    sort
    ταξινομεί μια περιοχή
    sort_heap
    ταξινομεί έναν σωρό
    stable_partition
    χωρίζει μια περιοχή στα δύο με βάση μια συνάρτηση και επιστρέφει το σημείο που είναι ο χωρισμός. Ο χωρισμός γίνεται χωρίς να αλλάξει η σχετική σειρά των στοιχείων.
    stable_sort
    ταξινομεί μια περιοχή. Η ταξινόμηση γίνεται χωρίς να αλλάξει η σχετική σειρά των στοιχείων που είναι μεταξύ τους ίσα.
    swap
    αντιστρέφει μεταξύ τους δύο στοιχεία
    swap_ranges
    αντιστρέφει μεταξύ τους δύο περιοχές
    transform
    εφαρμόζει έναν τελεστή σε μια περιοχή ή μεταξύ δύο περιοχών
    unique
    αφαιρεί τα όμοια στοιχεία από μια περιοχή
    unique_copy
    αφαιρεί τα όμοια στοιχεία από μια περιοχή μεταφέροντάς την σε μιαν άλλη περιοχή
    upper_bound
    εύρεση μιας μέγιστης τιμής σε περιοχή σε σχέση με μια άλλη τιμή

    Επικεφαλίδα numeric

    Στην επικεφαλίδα algorithm ορίζονται αριθμητικές μέθοδοι που ενεργούν πάνω σε περιέχοντες:
    accumulate
    υπολογίζει ένα σύνολο πάνω σε μια περιοχή
    adjacent_difference
    υπολογίζει τις διαφορές τιμών μεταξύ στοιχείων μιας περιοχής
    inner_product
    υπολογίζει ένα εσωτερικό γινόμενο μεταξύ δύο περιοχών
    partial_sum
    υπολογίζει ένα μερικό άθροισμα τιμών μιας περιοχής σε μιαν άλλη

    Άλλες επικεφαλίδες

    Ακόμα στην STL ορίζονται οι παρακάτω επικεφαλίδες:
    utility
    πρότυπη κλάση που ορίζει διάταξη σε ζεύγη τιμών
    functional
    κλάση που επιτρέπει συναρτησιακό προγραμματισμό
    memory
    ορίζει την κλάση allocator η οποία κατανέμει τη μνήμη σε όλους τους περιέχοντες. Ο επανακαθορισμός της επιτρέπει την υλοποίηση άλλων στρατηγικών καταμερισμού και πρόσβασης στη μνήμη.

    Συμβατότητα με τη C

    Ακόμα παρέχονται επικεφαλίδες που παρέχουν υπηρεσίες όμοιες με τις αντίστοιχες της γλώσσας C. Καλό είναι οι επικεφαλίδες αυτές να χρησιμοποιούνται μόνο όταν απαιτείται συμβατότητα με κληρονομημένο (legacy) (παλιό) κώδικα.
    cassert
    απόδειξη ιδιοτήτων κατά την εκτέλεση συναρτήσεων
    cctype
    χαρακτηρισμός χαρακτήρων
    cerrno
    πρόσβαση στα λάθη από την εκτέλεση συναρτήσεων της βιβλιοθήκης
    cfloat
    ιδιότητες αριθμών κινητής υποδιαστολής
    ciso646
    ορισμός λέξεων που επιτρέπουν τον προγραμματισμό σε συστήματα με τις κωδικοσελίδες ISO 646 (δεν αφορά την Ελλάδα)
    climits
    ιδιότητες των ακεραίων
    clocale
    προσαρμογή του προγράμματος σε τοπικά χαρακτηριστικά
    cmath
    μαθηματικές συναρτήσεις
    csetjmp
    αδόμητη μετάβαση ελέγχου μεταξύ συναρτήσεων
    csignal
    έλεγχος διακοπών
    cstdarg
    πρόσβαση σε ορίσματα με μεταβλητό αριθμό παραμέτρων
    cstddef
    ορισμός χρησίμων τύπων
    cstdio
    είσοδος και έξοδος όμοια με τη C
    cstdlib
    πρόσβαση στις αντίστοιχες συναρτήσεις της C
    cstring
    επεξεργασία συμβολοσειρών της C
    ctime
    χρήση ώρας και ημερομηνίας
    cwchar
    επεξεργασία "πλατιών" χαρακτήρων
    cwctype
    χαρακτηρισμός "πλατιών" χαρακτήρων

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

    Ασκήσεις

    Άσκηση 9

    1. Με βάση τον περιέχοντα της STL queue και μονοτονικά αυξανόμενη μεταβλητή να υλοποιηθεί πρόγραμμα το οποίο να υλοποιεί ουρά εξυπηρέτησης πελατών ως εξής:
      1. Όταν εισάγεται ο χαρακτήρας I (In) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του νέου πελάτη.
      2. Όταν εισάγεται ο χαρακτήρας O (Out) το πρόγραμμα τυπώνει τον αριθμό προτεραιότητας του επόμενου πελάτη που θα εξυπηρετηθεί.
      Παράδειγμα: 
      I
1
I
2
I
3
O
1
I
4
O
2
...

    Ολοκληρωμένα περιβάλλοντα ανάπτυξης

    Εισαγωγή

    Ο διορθωτής

    Ο διορθωτής σε ένα ολοκληρωμένο περιβάλλον ανάπτυξης περιλαμβάνει ισχυρές δυνατότητες εισαγωγής του κώδικα καθώς και δυνατότητες που σχετίζονται με τη γλώσσα προγραμματισμού όπως: Σε περιβάλλοντα που στοχεύουν στην ανάπτυξη προγραμμάτων με γραφικό σύστημα διεπαφής με το χρήστη συχνά υπάρχει και διορθωτής ο οποίος επιτρέπει το σχεδιασμό του συστήματος διεπαφής. Ο διορθωτής αυτό επιτρέπει την εισαγωγή στοιχείων του γραφικού περιβάλλοντος. Μερικά στοιχεία που απαντώνται συχνά είναι: Το παρακάτω σχήμα δείχνει ένα πλαίσιο διαλόγου σχεδιασμένο μέσα στο περιβάλλον του διορθωτή.

    Το σύστημα βοήθειας

    Το σύστημα βοήθειας περιλαμβάνει συχνά σε ψηφιακή μορφή τεκμηρίωση για: Το σύστημα βοήθειας είναι τις περισσότερες φορές παρουσιασμένο σε μορφή υπερκειμένου με πίνακες περιεχομένων και συνδέσεις ανάμεσα σε τμήματα, όπως φαίνεται στο παρακάτω σχήμα:

    Μερικές φορές το σύστημα βοηθείας συμπληρώνεται από οδηγούς (wizards) που επιτρέπουν με διαλογικό τρόπο τη βήμα με βήμα ανάπτυξη μιας εφαρμογής. Τα παρακάτω σχήμα παριστάνει ένα στάδιο από την εκτέλεση ενός οδηγού:

    Συχνά υπάρχει άμεση σύνδεση του διορθωτή με το σύστημα βοήθειας έτσι ώστε την ώρα που π.χ. πληκτρολογούμε την κλήση σε μια συνάρτηση της βιβλιοθήκης να μπορούμε να δούμε τον ορισμό της.

    Η διαδικασία μεταγλώττισης

    Η διαδικασία της μεταγλώττισης περιλαμβάνει αρκετές ευκολίες σε ένα ολοκληρωμένο περιβάλλον.

    Αποσφαλμάτωση

    Ο αποσφαλματωτής επιτρέπει τον πλήρη έλεγχο της ροής εκτέλεσης και των δεδομένων του προγράμματος που εκτελείται. Περιλαμβάνει δυνατότητες όπως: To παρακάτω σχήμα εμφανίζει ένα πρόγραμμα που εκτελείται σε περιβάλλον αποσφαλματωτή.

    Φυλλομέτρηση πηγαίου κώδικα και κλάσεων

    Συνδεδεμένο με το διορθωτή είναι συχνά ένα εργαλείο που επιτρέπει τη φυλλομέτρηση και την εμφάνιση της δομής του κώδικα και των κλάσεων που τον απαρτίζουν. Δυνατότητες του φυλλομετρητή μπορεί να είναι οι παρακάτω:

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

    Αντικειμενοστρεφής σχεδιασμός με UML

    Εισαγωγή

    Η ενοποιημένη γλώσσα σχεδιασμού (unified modeling language) (UML) είναι μια γραφική γλώσσα για την οπτική παράσταση, τη διαμόρφωση προδιαγραφών και την τεκμηρίωση συστημάτων που βασίζονται σε λογισμικό. Η UML στοχεύει στο σχεδιασμό αντικειμενοστρεφών συστημάτων. Το σχέδιο είναι μια απλοποιημένη παράσταση της πραγματικότητας.

    Σχεδιάζουμε για να μπορέσουμε να καταλάβουμε το σύστημα που αναπτύσσουμε. Έτσι δημιουργώντας ένα σχέδια επιτυγχάνουμε τέσσερις στόχους:

    1. παριστάνουμε οπτικά το σύστημα που έχουμε ή θέλουμε να κατασκευάσουμε,
    2. προσδιορίζουμε τη δομή και τη συμπεριφορά του συστήματος,
    3. δημιουργούμε ένα πρότυπο για να βασίσουμε την κατασκευή του συστήματος,
    4. τεκμηριώνουμε τις αποφάσεις που λάβαμε.

    Σε όλους τους τεχνολογικούς τομείς ο σχεδιασμός βασίζεται σε τέσερις βασικές αρχές:

    1. η επιλογή του είδους του σχεδίου έχει επίπτωση στον τρόπο και την μορφή επίλυσης του προβλήματος,
    2. όλα τα σχέδια εκφράζονται σε διαφορετικές βαθμίδες ακρίβειας,
    3. τα καλύτερα σχέδια σχετίζονται με την πραγματικότητα,
    4. ένα είδος σχεδίων δεν είναι ποτέ αρκετό.

    Η UML περιλαμβάνει τρία βασικά στοιχεία:

    1. Οντότητες
    2. Σχέσεις
    3. Διαγράμματα
    Η UML είναι μια πλήρης και πλούσια γλώσσα με εξαιρετικά ευρύ πεδίο εφαρμογής. Στο μάθημα αυτό θα εξετάσουμε εξαιρετικά συνοπτικά τον τρόπο παράστασης ορισμένων αντικειμενοστρεφών δομών σε UML.

    Κλάσεις

    Σχέσεις

    Στη UML ορίζονται τρεις βασικές σχέσεις:
    1. εξάρτηση (dependency)
    2. γενίκευση (generalisation)
    3. σύνδεση (association)

    Εξάρτηση

    Η εξάρτηση δηλώνει πως μια αλλαγή σε μιαν οντότητα θα επηρεάσει μιαν άλλη αλλά όχι απαραίτητα και το αντίστροφο. Παριστάνεται με μια διακεκομμένη γραμμή με ανοιχτό βέλος που δείχνει προς την οντότητα που υπάρχει εξάρτηση:

    Γενίκευση

    Η γενίκευση δηλώνει μια σχέση ανάμεσα σε κάτι γενικό (τη βασική κλάση ή αλλιώς γονέα) και κάτι ειδικό (μιαν υποκλάση ή αλλιώς παιδί της). Παριστάνεται με μια συνεχή γραμμή με κλειστό βέλος που δείχνει προς τη βασική κλάση:

    Σύνδεση

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

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

    Αν σχέση τα αντικείμενα που απαρτίζουν τμήματα ενός όλου έχουν την ίδια διάρκεια ζωής με το όλο, τότε αυτή απεικονίζεται ως σύνθεση (composition) με την παράσταση ενός γεμάτου διαμαντιού στην άκρη του "όλου".

    Διάγραμμα κλάσεων

    Το διάγραμμα των κλάσεων ενός συστήματος περιέχει τις κλάσεις μαζί με του αντίστοιχους δεσμούς εξάρτησης, γενίκευσης και σύνδεσης. Έτσι ένα διάγραμμα κλάσεων μπορεί να απεικονίσει τη χρήση της κληρονομικότητας στο σχεδιασμό με τη χρήση δεσμών γενίκευσης όπως στο παρακάτω σχήμα:

    Διάγραμμα αντικειμένων

    Τα διαγράμματα αντικειμένων χρησιμοποιούνται για το σχεδιασμό της στατικής κατάστασης του συστήματος κατά μια συγκεκριμένη χρονική στιγμή. Κάθε αντικείμενο σχεδιάζεται ως ένα ορθογώνιο με την παρακάτω μορφή:

    Το σύνολο των αντικειμένων σχεδιάζεται με βάση τους συνδέσμους που ορίζονται πάνω σε αυτό.

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

    Χειρισμός δεδομένων με SQL

    Το σχεσιακό μοντέλο δεδομένων

    Ένα σύστημα διαχείρισης βάσης δεδομένων (ΣΔΒΔ) (database management system (DBMS)) αποτελείται από ένα σύνολο δεδομένων και προγράμματα πρόσβασης στα δεδομένα αυτά. Το σύνολο των δεδομένων καλείται βάση δεδομένων (database). Στόχος του ΣΔΒΔ είναι η εύκολη και γρήγορη χρήση και ανάκτηση των δεδομένων. Η διαχείριση των δεδομένων περιλαμβάνει: Ο ορισμός της δομής της βάσης δεδομένων βασίζεται σε ένα μοντέλο δεδομένων το οποίο ορίζει τον τρόπο που περιγράφονται τα δεδομένα, οι σχέσεις τους, η σημασία τους και οι περιορισμοί πάνω στα δεδομένα αυτά.

    Το σχεσιακό μοντέλο (relational model) δεδομένων παριστάνει δεδομένα και τις σχέσεις τους ως ένα σύνολο πινάκων. Κάθε πίνακας (table) αποτελείται από στήλες (columns) με μοναδικά ονόματα. Μια γραμμή (row) του πίνακα παριστάνει μια σχέση (relationship) ανάμεσα σε ένα σύνολο από τιμές. Ο πίνακας που ακολουθεί παριστάνει έναν τηλεφωνικό κατάλογο. Αποτελείται από δύο στήλες και πέντε γραμμές.
    ΌνομαΤηλέφωνο
    Γιώργος32560
    Μαρία61359
    Θανάσης98756
    Λίνα78999
    Πέτρος12356

    Η SQL (structured query language) αποτελεί σήμερα την πιο διαδεδομένη γλώσσα διαχείρισης σχεσιακών βάσεων δεδομένων. Η SQL παρέχει δυνατότητες για:

    Η SQL είναι ορισμένη ως διεθνές πρότυπο. Στις επόμενες ενότητες θα εξετάσουμε ένα υποσύνολο της SQL όπως υποστηρίζεται από την εγκατεστημένη στα εργαστήρια βάση δεδομένων Microsoft Access.

    Στην περιγραφή της σύνταξης της SQL θα χρησιμοποιήσουμε τα παρακάτω σύμβολα:

    [ έκφραση ]
    η έκφραση εμφανίζεται προαιρετικά
    έκφραση1 | έκφραση2
    μπορεί να γραφεί η έκφραση1 ή η έκφραση2
    έκφραση ...
    η έκφραση μπορεί να επαναληφθεί

    Τύποι δεδομένων

    Τα δεδομένα κάθε στήλης ενός πίνακα πρέπει να έχουν ένα συγκεκριμένο τύπο. Οι βασικοί τύποι που υποστηρίζονται από την SQL είναι οι παρακάτω:
    ΒΙΤ
    Ναι ή Όχι
    CURRENCY
    Τιμή που παριστάνει με ακρίβεια αριθμούς από 922.337.203.685.477,5808 έως 922.337.203.685.477,5807
    DATETIME
    Χρόνος
    SINGLE
    Αριθμός κινητής υποδιαστολή μονής ακρίβειας
    DOUBLE
    Αριθμός κινητής υποδιαστολή διπλής ακρίβειας
    SHORT
    Ακέραιος 2 byte (-32768 έως 32767)
    LONG
    Ακέραιος 4 byte (-2.147.483.648 έως 2.147.483.647)
    TEXT
    Κείμενο μέχρι 255 χαρακτήρες
    LONGTEXT
    Κείμενο μέχρι 1.2GB

    Δημιουργία πινάκων

    Νέοι πίνακες δημιουργούνται με την εντολή CREATE TABLE. Αυτή συντάσσεται ως εξής: 
    CREATE TABLE όνομα_πίνακα (πεδίο1 τύπος [(μέγεθος)] [, πεδίο2 τύπος [(μέγεθος)] [, ...]]
    Για παράδειγμα η εντολή 
    CREATE TABLE Customer (Name TEXT (20), AccountNum SHORT)
    δημιουργεί τον πίνακα με όνομα Customer και με δύο στήλες: την Name και την AccountNum.

    Αλλαγές σε πίνακες

    Η εντολή ALTER TABLE επιτρέπει την προσθήκη νέων στηλών ή τη διαγραφή υπαρχόντων. Η προσθήκη νέων στηλών γίνεται με τη σύνταξη: 
    ALTER TABLE όνομα_πίνακα ADD COLUMN πεδίο τύπος[(μέγεθος)]
    Για παράδειγμα η εντολή: 
    ALTER TABLE Customer ADD COLUMN Notes TEXT(25)
    προσθέτει μια νέα στήλη στον πίνακα Customer.

    Η διαγραφή υπαρχόντων στηλών γίνεται με τη σύνταξη: 

    ALTER TABLE όνομα_πίνακα DROP COLUMN πεδίο
    Για παράδειγμα η εντολή: 
    ALTER TABLE Customer DROP COLUMN Notes
    αφαιρεί τη στήλη Notes από τον πίνακα Customer.

    Τέλος, η εντολή DROP TABLE επιτρέπει τη διαγραφή πινάκων. Για παράδειγμα η εντολή 

    DROP TABLE Customer
    θα διαγράψει τον πίνακα Customer

    Δείκτες

    Η πρόσβαση στα στοιχεία ενός πίνακα γίνεται ταχύτερα όταν αυτά οργανωθούν με τη βοήθεια δεικτών. Ένας δείκτης ορίζεται για μια συγκεκριμένη στήλη ή στήλες και επιτρέπει τη γρήγορη πρόσβαση σε γραμμές με βάση τιμές της συγκεκριμένης στήλης. Ουσιαστικά όταν ορίζουμε έναν δείκτη το ΣΔΒΔ υλοποιεί μια δομή δεδομένων (π.χ. ταξινομημένο ή κατακερματισμένο πίνακα ή δένδρο) για γρήγορη πρόσβαση στα αντίστοιχα δεδομένα. Δείκτες δημιουργούνται με την εντολή CREATE INDEX. Η σύνταξή της είναι η παρακάτω: 
    CREATE [ UNIQUE ] INDEX όνομα_δείκτη
ON όνομα_πίνακα (πεδίο [ASC|DESC][, πεδίο [ASC|DESC], ...])
    Η λέξη UNIQUE ορίζει πως δε θα επιτρέπονται διπλές εμφανίσεις μιας τιμής για το συγκεκριμένο δείκτη. Οι λέξεις ASC και DESC ορίζουν αύξουσα ή φθίνουσα ταξινόμηση του πίνακα με βάση το δείκτη. Παράδειγμα: 
    CREATE INDEX NameIdx ON Customer (Name)
    Δημιουργεί το δείκτη NameIdx για τη στήλη Name στον πίνακα Customer.

    Ένας δείκτης μπορεί να διαγραφεί με τη σύνταξη: 

    DROP INDEX όνομα_δείκτη ON όνομα_πίνακα

    Προσθήκη στοιχείων

    Προσθήκη δεδομένων σε έναν πίνακα γίνεται με την εντολή INSERT INTO σύμφωνα με τη σύνταξη: 
    INSERT INTO όνομα_πίνακα [(πεδίο1[, πεδίο2[, ...]])]
VALUES (τιμή1[, τιμή2[, ...])
    Παράδειγμα: 
    INSERT INTO Customer (Name, AccountNum) VALUES ("Papadopoulos", 1234)

    Επιλογή

    Επιλογή δεδομένων από έναν ή περισσότερους πίνακες γίνεται με την εντολή SELECT σύμφωνα με την παρακάτω βασική σύνταξη: 
    SELECT πεδία
FROM πίνακες
[ WHERE κριτήρια ]
    Απλό παράδειγμα: 
    SELECT Name, AccountNum FROM Customer WHERE Name LIKE "Pap*"

    Τα πεδία μπορούν να είναι ονόματα πεδίων ή συγκεντρωτικές συναρτήσεις της SQL πάνω σε πεδία. Τέτοιες συναρτήσεις είναι οι παρακάτω:

    Avg
    Μέσος όρος
    Count
    Μέτρηση
    Min
    Ελάχιστο
    Max
    Μέγιστο
    Sum
    Σύνολο
    Παράδειγμα: 
    SELECT Sum(AccountBalance) FROM Customer
    Ο αστερίσκος ως ορισμός πεδίου επιλέγει όλα τα πεδία.

    Τα κριτήρια αναζήτησης είναι εκφράσεις πάνω στα πεδία. Ορισμένοι βασικοί τελεστές είναι οι:

    Παράδειγμα: 
    SELECT * FROM Customer WHERE Balance > 10000 AND Name LIKE "Papad*"

    Βασικό στοιχείο του σχεσιακού μοντέλου είναι η αποθήκευση δεδομένων σε πίνακες που σχετίζονται μεταξύ τους. Έτσι για παράδειγμα ένας πίνακας μπορεί να φυλάει τα στοιχεία των πελατών και ένας άλλος τους λογαριασμούς. Με τον τρόπο αυτό τα στοιχεία ενός πελάτη που έχει πολλούς λογαριασμούς σε μια τράπεζα φυλάσσονται μόνο μια φορά. Ανάκτηση από δύο τέτοιους πίνακες γίνεται με τον προσδιορισμό τους στο SELECT μαζί με τη χρήση της κατάλληλης έκφρασης που θα ενώσει τους πίνακες. Παράδειγμα: 

    SELECT Customer, Balance FROM Customers, Accounts WHERE
Customer.AccountId = Accounts.AccountId

    Αλλαγή

    Αλλαγή σε στοιχεία γίνεται με την εντολή UPDATE σύμφωνα με τη σύνταξη: 
    UPDATE όνομα_πίνακα
SET πεδίο = νέα_τιμή
WHERE κριτήρια;
    Παράδειγμα: 
    UPDATE Accounts
SET Balance=100000
WHERE AccountId = 12233

    Διαγραφή

    Διαγραφή γραμμών από έναν πίνακα γίνεται με την εντολή DELETE σύμφωνα με τη σύνταξη: 
    DELETE 
FROM όνομα_πίνακα
WHERE κριτήρια
    Παράδειγμα: 
    DELETE
FROM Accounts
WHERE
AccountId = 123232

    SQL στη Microsoft Access

    Για να δώσουμε εντολές SQL στη Microsoft Access ακολουθούμε την παρακάτω διαδικασία: Τα αποτελέσματα της εντολής μπορούμε να τα δούμε στην περιοχή Tables.

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

    Ασκήσεις

    Άσκηση 10 (προαιρετική)

    1. Ορίστε με βάση SQL έναν τηλεφωνικό κατάλογο με τους φίλους σας.
    2. Εισάγετε μερικά ονόματα και τα τηλέφωνα
    3. Ανακτήστε ένα τηλέφωνο με τον τελεστή LIKE
    4. Μετρήστε τον αριθμό των φίλων σας με την έκφραση Count

    Συναρτησιακός προγραμματισμός στη Lisp

    Συναρτησιακός προγραμματισμός και η γλώσσα Lisp

    Ο συναρτησιακός προγραμματισμός (functional programming) βασίζεται στην αποτίμηση συναρτήσεων αντί για την εκτέλεση εντολών. Προγράμματα βασισμένα στο συναρτησιακό προγραμματισμό είναι γραμμένα με βάση συναρτήσεις που αποτιμούν βασικές τιμές. Μια συναρτησιακή γλώσσα προγραμματισμού υποστηρίζει και ενθαρρύνει το συναρτησιακό προγραμματισμό.

    Βασικά χαρακτηριστικά του συναρτησιακού προγραμματισμού είναι:

    Ορισμένες γνωστές συναρτησιακές γλώσσες προγραμματισμού είναι οι:

    Οι βασικές ιδέες της γλώσσας Lisp αναπτύχθηκαν από τον John McCarthy το 1956 σε ένα ερευνητικό πρόγραμμα για τεχνητή νοημοσύνη. Στόχος του McCarthy ήταν η ανάπτυξη μιας αλγευρικής γλώσσας επεξεργασίας λιστών για έρευνα στην τεχνητή νοημοσύνη. Ανάμεσα στα έτη 1960 και 1965 υλοποιήθηκε η διάλεκτος Lisp 1.5 η οποία τη δεκαετία του 1970 είχε οδηγήσει στις διαλέκτους MacLisp και InterLisp. Στα μέσα της δεκαετίας του 1970 οι Sussman και Steele Jr. ανέπτυξαν τη διάλεκτο Scheme με βάση ιδέες από τη σημασιολογία των γλωσσών προγραμματισμού. Στη δεκαετία του 1980 έγινε προσπάθεια για ενοποίηση των διαλέκτων της Lisp κάτω από το πρότυπο της Common Lisp.

    Απλές συναρτήσεις

    Παράδειγμα (ορισμός της συνάρτησης του παραγοντικού): 
    (defun factorial (n)
	(if (equal n 0)
	1
	(* n (factorial (- n 1)))))

    Λίστες

    Παράδειγμα: 
    '(1 2 3 4 42)
'word
'('Maria 'John 'Aliki)
    Βασικές συναρτήσεις επεξεργασίας λιστών είναι οι παρακάτω:
    (cons val list)
    επιστρέφει τη λίστα list με πρώτο το στοιχείο val,
    (car list)
    επιστρέφει το πρώτο στοιχείο μιας λίστας,
    (cdr list)
    επιστρέφει τα υπόλοιπα (όλα εκτός από το πρώτο) στοιχεία μιας λίστας ή nil αν αυτά δεν υπάρχουν.
    Με βάση τις συναρτήσεις αυτές μπορούμε να ορίσουμε πιο σύνθετες συναρτήσεις.

    Length

    Επιστρέφει το μήκος μιας λίστας. 
    (defun mylength (a) 
	(if (null a) 
		0 
		(+ (mylength (cdr a)) 1)))

    Append

    Ενώνει δύο λίστες. 
    (defun myappend (a b)
	(if (null a)
		b
		(cons (car a) (myappend (cdr a) b))))

    Reverse

    Αντιστρέφει μια λίστα. 
    (defun myreverse (a)
	(if (null a)
		nil
		(myappend (myreverse (cdr a)) (cons (car a) nil))))

    Συναρτήσεις ανωτέρου βαθμού

    Το παρακάτω παράδειγμα συνθέτουμε τις έννοιες αυτές για να ορίσουμε τις συναρτήσεις map και reduce.

    Map

    Η συνάρτηση map μετατρέπει μια λίστα σε μια άλλη με βάση μια συνάρτηση που έχει δοθεί ως όρισμα. 
    (defun mymap (f lst)
	(if (null lst) 
		nil 
		(cons (apply f (cons (car lst) nil)) (mymap f (cdr lst)))))
    Έτσι μπορούμε π.χ. να διπλασιάσουμε να στοιχεία της λίστας '(1 2 3) με την κλήση: 
    (mymap (lambda (x) (* 2 x)) '(1 2 3))      
(2 4 6)

    Reduce

    Η συνάρτηση reduce συμπυκνώνει μια λίστα εφαρμόζοντας αναδρομικά τη συνάρτηση σε κάθε στοιχείο της λίστας αρχίζοντας από μια αρχική τιμή. 
    (defun myreduce (f v lst)
	(if (null lst) 
		v 
		(apply f (cons (car lst) (cons (myreduce f v (cdr lst)) nil)))))
    Έτσι μπορούμε να ορίσουμε συναρτήσεις όπως τις:

    Μεταγλωττιστής Lisp

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

    Ασκήσεις

    Άσκηση 11

    1. Οι δύο πρώτοι αριθμοί της ακολουθίας Fibonacci είναι 0 και 1. Κάθε επόμενος αριθμός είναι το άθροισμα των δύο προηγούμενων. Γράψτε τη συνάρτηση που επιστρέφει τον νοστό αριθμό Fibonacci. (Οι αριθμοί Fibonacci απαντώνται συχνά στη φύση π.χ. στον αριθμό πετάλων των λουλουδιών και στις σπείρες από τα κουκουνάρια και τις αχιβάδες).
    2. Γράψτε τη συνάρτηση (member list val) που επιστρέφει αληθές αν η τιμή val περιέχεται στη λίστα list.

    Κατανεμημένος προγραμματισμός

    Εισαγωγή

    Σημείωση
    Η σημειώσεις της ενότητας αυτής έχουν γραφεί από τον υποψήφιο διδάκτορα του Τμήματος Πληροφοριακών και Επικοινωνιακών Συστημάτων του Πανεπιστημίου Αιγαίου, Κωνσταντίνο Ράπτη (mailto:krap@aegean.gr).

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

    Με την εμφάνιση και την ανάπτυξη των προσωπικών υπολογιστών και καθώς οι εφαρμογές άρχισαν να γίνονται ολοένα και πιο μεγάλες και σύνθετες, άρχισαν να μεταμορφώνονται από ενιαία προγράμματα σε κομμάτια ικανά να συνεργάζονται μεταξύ τους. Στην διάσπαση των εφαρμογών σε περισσότερα από ένα μέρη, συνέβαλλε η ανάπτυξη της αρχιτεκτονικής πελάτη/εξυπηρετητή (client/server) βάσει της οποίας γινόταν η υλοποίησή τους. Κατά την αρχιτεκτονική πελάτη/εξυπηρετητή, μία διεργασία καλείται πελάτης (client process) όταν αιτείται την υλοποίηση κάποιων υπηρεσιών-μεθόδων από μία διεργασία η οποία είναι ικανή να της προσφέρει τις επιθυμητές υπηρεσίες. Η τελευταία αυτή διεργασία καλείται διεργασία του εξυπηρετητή (server process).

    Αργότερα με την ανάπτυξη των υπολογιστικών δικτύων τα συνθετικά μέρη των εφαρμογών, προκειμένου να υπάρξει καλύτερη και αποτελεσματικότερη εκμετάλλευση των νέων δυνατοτήτων, άρχισαν να διαμοιράζονται στους υπολογιστές του δικτύου. Με τον τρόπο αυτό αυξανόταν η απόδοση και εκμετάλλευση των πόρων του δικτύου. Αυτού του είδους οι εφαρμογές ονομάζονται κατανεμημένες εφαρμογές (distributed applications).

    Η δυνατότητα διασύνδεσης, σε δίκτυα, υπολογιστικών συστημάτων διαφορετικής αρχιτεκτονικής είχε σαν αποτέλεσμα την δημιουργία ενός ανομοιογενούς υπολογιστικού περιβάλλοντος. Θα έπρεπε, λοιπόν, και οι εφαρμογές να μπορέσουν να εξελιχθούν έτσι ώστε να είναι δυνατή η λειτουργία τους σε τέτοια ετερογενή συστήματα υπολογιστών. Αυτή η εξέλιξη οδήγησε στην εμφάνιση των ετερογενών κατανεμημένων εφαρμογών (heterogeneous distributed applications).

    Λογισμικό βασιμένο σε εξαρτήματα

    Καθώς όμως η ανάπτυξη του υλικού (hardware) είχε ως αποτέλεσμα την δημιουργία όλο και πιο ισχυρών, ταχύτερων, μικρότερων και ταυτόχρονα φθηνότερων προϊόντων, το λογισμικό εξακολουθούσε να είναι όλο και πιο σύνθετο, πολύπλοκο και ακριβό. Για να ξεπεραστεί αυτή η αδυναμία του λογισμικού θα έπρεπε να υπάρχει η δυνατότητα κάθε νέο λογισμικό να μην είναι απαραίτητο να αναπτυχθεί από την αρχή αλλά να δίνετε η δυνατότητα να προστίθενται νέα κομμάτια λογισμικού τα οποία θα μπορούσαν άμεσα να χρησιμοποιηθούν μέσα από το λογισμικό. Αυτή η εξέλιξη οδήγησε στην ανάπτυξη της τεχνολογίας των εξαρτημάτων λογισμικού (software components technology). Η νέα αυτή τεχνολογία έχει ως σκοπό να επιτρέψει την χρησιμοποίηση κομματιών λογισμικού τα οποία θα είναι κατασκευασμένα από διαφορετικούς κατασκευαστές, θα είναι υλοποιημένα σε διαφορετικές γλώσσες προγραμματισμού και θα τρέχουν κάτω από διαφορετικά λειτουργικά συστήματα.

    Τεχνολογίες διαλειτουργικότητας κομματιών λογισμικού

    Συνοψίζοντας τα παραπάνω, μπορούμε τα πούμε ότι τα βασικά στοιχεία που χαρακτηρίζουν ένα σύγχρονο υπολογιστικό περιβάλλον είναι τα εξής: Με βάση τα παραπάνω στοιχεία η χρησιμοποίηση μοντέλων-μεθοδολογιών τα οποία θα διευκολύνουν την λειτουργία των εφαρμογών κάτω από τις συνθήκες ενός ετερογενούς περιβάλλοντος και θα επιτελούν τις λειτουργίες επικοινωνίας με τρόπο τέτοιο έτσι ώστε να είναι διαφανής προς τους τελικούς χρήστες, είναι επιβεβλημένη και η υιοθέτησή τους αποτελεί πλέον ζήτημα για τους οργανισμούς και τις επιχειρήσεις οι οποίες συντηρούν τέτοιου είδους υπολογιστικά συστήματα και δίκτυα.

    Τρία είναι τα βασικά μοντέλα των οποίων σκοπός είναι η υλοποίηση των παραπάνω και αυτά είναι:

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

    OMG CORBA

    Η OMG (Object Management Group) αναπτύσσει πρότυπα βασιζόμενη στην τεχνολογία του αντικειμένου.

    Σύμφωνα με την αρχιτεκτονική που προτείνεται από την OMG, την OMA (Object Management Architecture), το κάθε κομμάτι λογισμικού παρουσιάζεται σαν αντικείμενο (Object).

    Τα διάφορα αντικείμενα επικοινωνούν μεταξύ τους μέσω του ORB (Object Request Broker), ο οποίος αποτελεί το στοιχείο-κλειδί γι' αυτήν την επικοινωνία. Ο ORB παρέχει τους μηχανισμούς εκείνους μέσω των οποίων τα αντικείμενα κάνουν τις αιτήσεις και συλλέγουν τις αποκρίσεις.

    Η CORBA (Common Object Request Broker Architecture) αποτελεί το πρότυπο της OMG για τον ORB.

    Κατά την CORBA, ένας πελάτης ο οποίος ζητάει κάποιες υπηρεσίες από κάποιο αντικείμενο, κάνει μία αίτηση (request) η οποία μεταβιβάζεται στον ORB και ο οποίος είναι στη συνέχεια υπεύθυνος για την προώθηση της αίτησης προς τον κατάλληλο εξυπηρετητή.

    Η αίτηση αυτή περιέχει όλες τις απαραίτητες πληροφορίες που απαιτούνται προκειμένου να υλοποιηθεί και αυτές είναι:

    Για να είναι κατανοητή όμως η αίτηση θα πρέπει να έχει μία κατάλληλη μορφή και γι' αυτό το λόγο γίνεται προς τον ORB μέσω διασυνδετών (interfaces: "Dynamic Invocation" και "IDL Stubs").

    Για τον ίδιο λόγο η προώθηση της αίτησης προς τον εξυπηρετητή γίνεται μέσω διασυνδετών ("Static IDL Skeleton" και "IDL Skeleton").

    Ένας διασυνδέτης αποτελεί μία περιγραφή ενός συνόλου από πιθανές λειτουργίες τις οποίες ένας πελάτης μπορεί να αιτηθεί ενός αντικειμένου.

    Ένα αντικείμενο ικανοποιεί έναν διασυνδέτη εάν μπορεί να προσδιοριστεί σαν το αντικείμενο-στόχος (target object) για κάθε δυνατή αίτηση η οποία περιγράφεται από τον διασυνδέτη.

    Στο σημείο αυτό δεν θα πρέπει να αγνοήσουμε την ιδιότητα της κληρονομικότητας που χαρακτηρίζει τους διασυνδέτες και η οποία παρέχει τον συνθετικό εκείνο μηχανισμό που επιτρέπει σ' ένα αντικείμενο να υποστηρίζει πολλαπλούς διασυνδέτες.

    Οι διασυνδέτες καθορίζονται πλήρως μέσω της OMG IDL (Interface Definition Language). Η IDL δεν αποτελεί γλώσσα προγραμματισμού, όπως οι γνωστές γλώσσες προγραμματισμού, αλλά μία καθαρά περιγραφική γλώσσα η οποία δεν περιλαμβάνει δομές αλγορίθμων ή μεταβλητές. Η γραμματική της αποτελεί υποσύνολο της ANSI C++ με πρόσθετες κατασκευές για την υποστήριξη μηχανισμών για την επίκληση απομακρυσμένων λειτουργιών.

    Οι πελάτες δεν είναι "γραμμένοι" σε OMG IDL αλλά σε γλώσσα για την οποία έχει προσδιοριστεί η αντιστοιχία της με την OMG IDL.

    Microsoft COM/DCOM

    Το δεύτερο μοντέλο βασίζεται και αυτό στην τεχνολογία του αντικειμένου με την έννοια όμως εδώ των αυτόνομων συνθετικών εξαρτημάτων μίας εφαρμογής.

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

    Ο "μηχανισμός λειτουργίας του μοντέλου είναι παρόμοιος με αυτόν της CORBA. Βασικό ρόλο παίζουν οι διασυνδέτες τα οποία δεν είναι τίποτα άλλο από ένα σαφές διατυπωμένο "συμβόλαιο" μεταξύ των "κομματιών" λογισμικού, το οποίο περιέχει ένα σύνολο από σχετικές λειτουργίες. Όταν λέμε ότι ένα αντικείμενο υλοποιεί έναν διασυνδέτη αυτό σημαίνει ότι το αντικείμενο αυτό υλοποιεί κάθε λειτουργία του.

    Πως γίνεται, όμως, η διαδικασία της αιτήσεως κάποιων λειτουργιών από έναν πελάτη;

    Για να μπορέσει ένας πελάτης να εξυπηρετηθεί από κάποιο αντικείμενο, θα πρέπει η γλώσσα προγραμματισμού, στην οποία είναι υλοποιημένος, να έχει τη δυνατότητα δημιουργίας δεικτών και να καλεί συναρτήσεις μέσω των δεικτών. Θα πρέπει λοιπόν ο πελάτης να έχει τον κατάλληλο δείκτη προς τον επιθυμητό διασυνδέτη τον οποίο περιέχει τις επιθυμητές από τον πελάτη λειτουργίες.

    Στην περίπτωση όμως που ο πελάτης δεν έχει τον κατάλληλο δείκτη προς το επιθυμητό διασυνδέτη, τότε απευθύνεται προς την COM δίνοντας σαν στοιχεία την ταυτότητα της κλάσης του εξυπηρετητή που επιθυμεί ο πελάτης και τον τύπο του, δηλαδή εάν είναι:

    Η COM τότε αναλαμβάνει να βρει τον επιθυμητό εξυπηρετητή και να επιστρέψει στον πελάτη τον επιθυμητό δείκτη.

    Όπως έγινε σαφές, ο κάθε πελάτης μπορεί να είναι υλοποιημένος σε οποιαδήποτε γλώσσα προγραμματισμού, αρκεί αυτή να υποστηρίζει την κατασκευή και την χρήση δεικτών. Για τα "interfaces", όμως, υπάρχει και εδώ μία "IDL" (interface Definition Language) η οποία επιτρέπει και βοηθάει τους σχεδιαστές να κατασκευάζουν διασυνδέτες.

    Sun Java RMI

    Το μοντέλο RMI της Sun, βασίζεται και αυτό στην τεχνολογία του αντικειμένου και είναι σχεδιασμένο για να προάγει την διαλειτουργικότητα μεταξύ αντικειμένων, κατασκευασμένων σε Java, μέσα σε ένα κατανεμημένο και ετερογενές περιβάλλον.

    Η τεχνολογία RMI αφορά αποκλειστικά αντικείμενα τα οποία είναι κατασκευασμένα με τη γλώσσα προγραμματισμού Java. Αυτό έχει ως αποτέλεσμα να δίνει την δυνατότητα της πλήρους εκμετάλλευσης των δυνατοτήτων της Java αλλά και το πλεονέκτημα του ομοιογενούς, ως προς τη γλώσσα προγραμματισμού, περιβάλλοντος.

    Η αρχιτεκτονική ενός RMI συστήματος ακολουθεί την δομή των στρωμάτων-επιπέδων (layers). Υπάρχουν τρία (συν ένα) επίπεδα:

    Υπάρχει, επίσης, το επίπεδο της Εφαρμογής (Application) το οποίο όμως δεν αποτελεί καθαρό κομμάτι της τεχνολογίας και το οποίο βρίσκεται πάνω απΤ τα υπόλοιπα.

    Η διαδικασία επίκλησης κάποιων υπηρεσιών από έναν πελάτη, δεν διαφέρει, ιδιαίτερα, σε σχέση με τις προαναφερθείσες τεχνολογίες. Ένας πελάτης, ο οποίος επιθυμεί την υλοποίηση κάποιων υπηρεσιών, υποβάλλει μία αίτηση προς το RMI-σύστημα. Στην αίτηση αυτή θα πρέπει να αναφέρονται οι κατάλληλες εκείνες πληροφορίες οι οποίες απαιτούνται για την αποστολή της αίτησης προς τον κατάλληλο εξυπηρετητή. Αυτές οι πληροφορίες-παράμετροι είναι: μία αναφορά του επιθυμητού αντικειμένου (object reference), οι επιθυμητές μέθοδοι και οι κατάλληλες παράμετροι για την υλοποίηση των μεθόδων.

    Από τη στιγμή που ο πελάτης καταθέσει την αίτησή του, το RMI-σύστημα είναι υπεύθυνο για την ανεύρεση του κατάλληλου εξυπηρετητή, την μεταβίβαση της αιτήσεων και την επιστροφή των αποτελεσμάτων στον πελάτη.

    Όμοια με την CORBA και την COM/DCOM, σε ένα RMI-σύστημα, οι πελάτες δεν έρχονται ποτέ σε απευθείας επικοινωνία με τα επιθυμητά αντικείμενα παρά μόνο μέσω των διασυνδετών αυτών των αντικειμένων. Και εδώ ο διασυνδέτης είναι αυτός που περιέχει τις μεθόδους-υπηρεσίες τις οποίες μπορεί να υλοποιήσει το αντικείμενο.

    Η επικοινωνία πελάτη-αντικειμένου, σΤ ένα σύστημα RMI, είναι η ίδια ανεξάρτητα με το που βρίσκεται το επιθυμητό αντικείμενο (αν δηλαδή βρίσκεται στην ίδια διεργασία με τον πελάτη, αν βρίσκεται τοπικά ή απομακρυσμένα).

    Πηγές για έρευνα στο Internet

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

    Κατηγορήματα στην Prolog

    Εισαγωγή

    Η προστακτικές γλώσσες προγραμματισμού όπως η Fortran, η Pascal και η C έχουν κατασκευαστεί και να διευκολύνουν τον προγραμματισμό υπολογιστών αρχιτεκτονικής von Neumann (επεξεργαστής που εκτελεί κώδικα και επεξεργάζεται δεδομένα από τη μνήμη). Ιστορικά, ο στόχος για το σχεδιασμό των γλωσσών αυτών είναι να γίνει ο προγραμματισμός του υπολογιστή προσιτός στον άνθρωπο. Έτσι, η διαδικασία της λύσης ενός προβλήματος με υπολογιστή εμφανίζεται διχοτομημένη ανάμεσα στην ανάλυση του προβλήματος και, στη συνέχεια, την κωδικοποίησή του σε υπολογιστή.

    Η εξέλιξη της ισχύος των υπολογιστών και του αντίστοιχου θεωρητικού υπόβαθρου μας έχει επιτρέψει να εξετάζουμε διαφορετικές προσεγγίσεις επίλυσης προβλημάτων με υπολογιστή που να βασίζονται όχι στο να κάνουν την αρχιτεκτονική του υπολογιστή προσιτή στον άνθρωπο, αλλά στο να κάνουν τη διατύπωση των προβλημάτων από τον άνθρωπο προσιτή στον υπολογιστή. Έτσι, τόσο ο συναρτησιακός όσο και ο λογικός προγραμματισμός επιτρέπουν τη διατύπωση του προβλήματος που πρέπει να επιλυθεί με βάση έναν συμβολισμό και αφήνουν στον υπολογιστή να λύσει το πρόβλημα με βάση τη διατύπωσή του. Η βάση του λογικού προγραμματισμού μπορεί να διατυπωθεί ως εξής:

    ή τη σύνοψή της από τον Bob Kowalski: Η ιστορία του λογικού προγραμματισμού και της Prolog μπορεί να συνοψιστεί από τους παρακάτω σταθμούς:
    J. Robinson (1965)
    Διατύπωση του αλγόριθμου της ταυτοποίησης (unification). Ο αλγόριθμος αυτός βρίσκει ένα σύνολο από στοιχειώδεις αντικαταστάσεις σε μεταβλητές για να καταστήσει δύο όρους ταυτόσημους.
    R. Kowalski (1974)
    Διαδικασιακή ερμηνεία προτάσεων Horn. Προτάσεις της μορφής Α αν Β1 και Β2 και ... Βν μπορούν να ερμηνευτούν διαδικασιακά ως: για να ισχύει το Α, πρέπει να ισχύει το Β1 και το Β2 και ... το Βν.
    A. Colmerauer (1973)
    Υλοποίηση διερμηνευτή της Prolog σε Fortran.
    D. Warren (1977
    Υλοποίηση μεταγλωττιστή της Prolog (σε ενδιάμεση γλώσσα την Warren Abstract Machine).
    Ιαπωνία (1981)
    Πρόγραμμα υπολογιστών πέμπτης γενιάς. Έδωσε ώθηση στην Prolog υιοθετώντας το λογικό προγραμματισμό ως βασική τεχνολογία του προγράμματος.

    Σχέσεις

    Η βάση της Prolog είναι τα γεγονότα (facts), οι κανόνες (rules) και οι ερωτήσεις (queries). Υπάρχει μόνο μια δομή δεδομένων, ο όρος (term). Τα γεγονότα ορίζουν μια αληθή σχέση ανάμεσα σε αντικείμενα.

    Παράδειγμα 1 (ορισμός σχέσεων ανάμεσα σε ακέραιούς): 

    sum(0, 0, 0).
sum(0, 1, 1).
sum(1, 0, 1).
sum(1, 1, 2).

    Παράδειγμα 2 (ορισμός σχέσεων ανάμεσα σε ανθρώπους): 

    father(anthi, giannis).
father(petros, giannis).
father(thanasis, giannis).
father(iro, giannis).

father(nikos, thanasis).
father(giorgos, thanasis).

mother(anthi, maria).
    Οι λέξεις nikos, petros, anthi, στο παραπάνω παράδειγμα είναι σταθερές της γλώσσας (όπως και οι ακέραιοι στο προηγούμενο). Ονομάζονται άτομα (atoms) και γράφονται με αρχικό μικρό γράμμα.

    Με βάση τα παραπάνω γεγονότα μπορούμε να εκτελέσουμε ερωτήσεις για να μάθουμε αν μια σχέση είναι αληθής ή ψευδής. Όταν η Arity Prolog βρει μια αληθή λύση στην ερώτησή μας μας εμφανίζει το σύμβολο ->. Στο σημείο εκείνο μπορούμε να πατήσουμε Enter για να δηλώσουμε πως μας ικανοποιεί η λύση, ή ; για να δηλώσουμε πως θέλουμε να δούμε και άλλες λύσεις. Παράδειγμα: 

    ?- sum(0, 0, 0).
 ->

yes
?- sum(1, 1, 2).
 ->

yes
?- sum(1, 1, 0).

no
?- sum(5, 3, 9).

no

    Λογικές μεταβλητές

    Ερωτήσεις με μεταβλητές

    Οι λογικές μεταβλητές στην Prolog (γράφονται με αρχικό κεφαλαίο γράμμα) μπορούν να χρησιμοποιηθούν για να τεθούν ερωτήσεις για να μάθουμε κάποιο στοιχείο από τα γεγονότα που έχουμε ορίσει. Παράδειγμα: 
    ?- sum(1, 1, X).

X = 2
yes
?- sum(X, 1, X).

no
?- sum(X, X, 2).

X = 1
yes
?- father(iro, X).

X = giannis
yes
?- father(X, Y).

X = anthi
Y = giannis ->;

X = petros
Y = giannis ->;

X = thanasis
Y = giannis ->;

X = iro
Y = giannis ->;

X = nikos
Y = thanasis ->
yes

    Γεγονότα με μεταβλητές

    Με βάση τις μεταβλητές μπορούμε ακόμα να ορίσουμε και γενικευμένα γεγονότα (universal facts). Για παράδειγμα για να ορίσουμε πως όλοι αγαπούν τη Μαίρη γράφουμε: 

    loves(X, mairi).

    Όροι

    Με βάση τα παραπάνω μπορούμε να ορίσουμε τη δομή δεδομένων της Prolog, τον όρο. Οι όροι ορίζονται αναδρομικά. Ένας όρος μπορεί να είναι:

    • σταθερά, δηλαδή άτομο ή αριθμός
    • μεταβλητή
    • άτομο(όρος1, ... όρος_ν)
    Παραδείγματα όρων: 
    sum(0, 0, 1)
car(color(red), engine(1600), abs, speed(172), doors(2,2,1))
loves(X, Y)

    Σύζευξη

    Μπορούμε να ενώσουμε ερωτήσεις μεταξύ τους με το κόμμα (,) για να απαιτήσουμε να είναι και οι δύο αληθείς: 
    ?- sum(0, 1, 1), sum(1, 1, 2).

yes
?- sum(0, 1, 1), sum(1, 1, 3).

no
    Μπορούμε να ορίσουμε ακόμα κανόνες με βάση ένα γεγονός και κάποιες σχετικές ερωτήσεις με την παρακάτω σύνταξη: 
    a :-
	b1,
	b2,
	bn.
    Ο κανόνας διαβάζεται ως εξής: ισχύει το a αν ισχύει το b1 και το b2 και το bn. Αν ορίσουμε παραπάνω από έναν κανόνα για το ίδιο γεγονός τότε οι κανόνες ισχύουν διαζευκτικά (αρκεί να ισχύει ένας).

    Παράδειγμα: 

    
parent(X, Y) :-
        father(X, Y).
parent(X, Y) :-
        mother(X, Y).
?- parent(anthi, X).

X = giannis ->;

X = maria
yes
?- parent(X, giannis).

X = anthi ->;

X = petros ->;

X = thanasis ->;

X = iro ->;

no

    Παράδειγμα: 

    grandfather(X, Y) :-
        father(Z, X),
        father(Y, Z).
?- grandfather(X, Y).

X = giannis
Y = nikos ->;

X = giannis
Y = giorgos ->;

no

    Αριθμητική με αναδρομή

    Με βάση τον αναδρομικό ορισμό των ακεραίων μπορούμε να τους ορίσουμε αξιωματικά και στην Prolog. Ορίζουμε τον όρο s(X) να παριστάνει τον επόμενο ακέραιο από το X. Έτσι, ορίζοντας το 0 το 1 είναι s(0), το 2 είναι s(s(0)), κ.λπ. Ο κανόνας nat ορίζει τους ακέραιους αριθμούς. Μπορούμε με επαγωγή να αποδείξουμε πως όλοι οι ακέραιοι παράγονται και αναγνωρίζονται από τον nat. 
    nat(0).
nat(s(X)) :-
	nat(X).
?- nat(0).

yes
?- nat(s(0)).

yes
?- nat(s(s(s(s(0))))).

yes
?- nat(X).

X = 0 ->;

X = s(0) ->;

X = s(s(0)) ->;

X = s(s(s(0))) ->;

X = s(s(s(s(0)))) ->

X = s(s(s(s(s(0))))) ->;

X = s(s(s(s(s(s(0)))))) ->;

X = s(s(s(s(s(s(s(0))))))) ->;

X = s(s(s(s(s(s(s(s(0)))))))) ->;

X = s(s(s(s(s(s(s(s(s(0))))))))) ->;

X = s(s(s(s(s(s(s(s(s(s(0)))))))))) ->
...
    Με βάση τον ορισμό αυτό μπορούμε να ορίσουμε μια σχέση διάταξης: 
    less(0, X) :-
	nat(X).

less(s(X), s(Y)) :-
	less(X, Y).

?- less(s(0), 0).

no
?- less(s(0), s(s(0))).

yes
?- less(X, s(s(s(s(0))))).

 X = 0 ->;

 X = s(0) ->;

 X = s(s(0)) ->;

 X = s(s(s(0))) ->;

 X = s(s(s(s(0)))) ->;

no
    Με παρόμοιο τρόπο μπορούμε να ορίσουμε και την πρόσθεση: 
    plus(0, X, X) :-
	nat(X).

plus(s(X), Y, s(Z)) :-
	plus(X, Y, Z).
    Είναι αξιοσημείωτο πως το κατηγόρημα της πρόσθεσης με τη μορφή που έχει οριστεί μπορεί να υπολογίσει άθροισμα, διαφορά, όρους που δημιουργούν ένα άθροισμα, ή να ελέγξει αν ένα άθροισμα είναι αληθές: 
    ?- plus(s(0), s(0), X).

X = s(s(0))
yes
?- plus(s(0), X, s(s(s(0)))).

X = s(s(0))
yes
?- plus(X, Y, s(s(0))).

X = 0
Y = s(s(0)) ->;

X = s(0)
Y = s(0) ->;

X = s(s(0))
Y = 0 ->;

no
?- plus(s(0), 0, 0).

no
    Με τη χρήση του αθροίσματος μπορούμε να ορίσουμε και το γινόμενο: 
    times(0, X, 0)

times(s(X), Y, Z) :-
	times(X, Y, W),
	plus(W, Y, Z).
    Το κατηγόρημα για το γινόμενο που έχει οριστεί με τον τρόπο αυτό έχει και αυτό παρόμοια ευελιξία: 
    ?- times(s(s(0)), s(s(s(0))), X).

X = s(s(s(s(s(s(0))))))
yes
?- times(X, s(s(0)), s(s(s(s(0))))).

X = s(s(0)) ->.

yes
?- times(X, Y, s(s(s(s(0))))).

X = s(0)
Y = s(s(s(s(0)))) ->;

X = s(s(0))
Y = s(s(0)) ->;

?- times(s(0), s(0), s(0)).

yes

    Υπολογισμοί στην Prolog

    Αν και ο παραπάνω ορισμός των ακεραίων είναι αξιοθαύμαστος για τη λιτότητα και την πληρότητά του, οι υλοποιήσεις της Prolog για υπολογισμούς αριθμών χρησιμοποιούν το κατηγόρημα is(X, Y) και την υλοποίηση των αριθμών από τον επεξεργαστή του υπολογιστή. Αυτό υπολογίζει το αποτέλεσμα της αριθμητικής έκφρασης στο Y και την ταυτοποιεί με το X. Το κατηγόρημα αυτό είναι μεν αποδοτικό, δε συμπεριφέρεται όμως με την ευελιξία που δείξαμε στα παραπάνω παραδείγματα. Παράδειγμα: 
    ?- is(X, 1 + 2).

X = 3

?- is(2, 1 + 1).

yes
?- is(Y, 3 * 8 + 4 / 5).

Y = 24.8
yes
?- is(2, X + X).

no

    Λίστες

    Οι λίστες στην Prolog ορίζονται με τη σύνταξη [Head | Tail] όπου Head είναι το στοιχείο που αποτελεί την κεφαλή της λίστας και Tail τα υπόλοιπα στοιχεία. Η σύνταξη αυτή αποτελεί απλώς συντομογραφία για όρους των οποίων το όνομα είναι η τελεία (.). Με βάση τον ορισμό των λιστών μπορούμε πολύ εύκολα να ορίσουμε σύνθετους αλγόριθμους όπως την ταξινόμηση quick sort: 
    quicksort([X|Xs], Ys) :-
        partition(Xs, X, L, B),
        quicksort(L, Ls),
        quicksort(B, Bs),
        append(Ls, [X | Bs], Ys).

quicksort([], []).

partition([X|Xs], Y, [X|Ls], Bs) :-
        X =< Y,
        partition(Xs, Y, Ls, Bs).

partition([X|Xs], Y, Ls, [X|Bs]) :-
        X > Y,
        partition(Xs, Y, Ls, Bs).

partition([], Y, [], []).

append([], X, X).

append([H | T], X, [H | Z]) :-
        append(T, X, Z).

?- quicksort([4,2,8,12,1,7], X).

X = [1,2,4,7,8,12] ->.

yes

    Συμβολική επεξεργασία

    Με βάση μεταβλητές και όρους μπορούμε να γράψουμε ένα πρόγραμμα που να αναγνωρίζει πολυώνυμα ορισμένα με τον παρακάτω τρόπο:
    • sum(A, B) (άθροισμα)
    • diff(A, B) (διαφορά)
    • prod(A, B) (γινόμενο)
    • quot(A, B) (πηλίκο)
    • pow(A, B) (ύψωση σε δύναμη)
    • τη μεταβλητή X
    • καθώς και ακεραίους. 
    polynomial(X, X).

polynomial(N, X) :-
        number(N).

polynomial(sum(A, B), X) :-
        polynomial(A, X),
        polynomial(B, X).

polynomial(diff(A, B), X) :-
        polynomial(A, X),
        polynomial(B, X).

polynomial(prod(A, B), X) :-
        polynomial(A, X),
        polynomial(B, X).

polynomial(quot(A, B), X) :-
        polynomial(A, X),
        number(B).

polynomial(pow(A, B), X) :-
        polynomial(A, X),
        integer(B).
    Ερωτήσεις: 
    ?- p(sum(x, 1), x).
 ->.

yes
?- p(sum(x, 1), y).

no
?- polynomial(sum(prod(5,pow(x, 2)), prod(2, x)), x).
 ->.

yes
?- polynomial(sum(prod(5,pow(x, 2)), pow(y, 3)), x).

no
?- polynomial(sum(prod(5,pow(x, 2.1)), prod(2, x)), x).

no

    Σύντομες οδηγίες για τη χρήση της Arity Prolog

    • Αντιγράφετε τα αρχεία c:\apps\arity\bin\dos\ari σε έναν δικό σας κατάλογο (κάτω από το home σας).
    • Τρέχετε την εντολή api.
    • Στο ?- που εμφανίζεται μπορείτε να πληκτρολογήσετε ερωτήσεις.
    • Για να πληκτρολογήσετε κανόνες πατάτε Switch (ALT-S) και γράφετε τους κανόνες που θέλετε στο διορθωτή που εμφανίζεται.
    • Πριν βγείτε από το διορθωτή βεβαιωθείτε πως η εντολή Buffers - Reconsult on exit είναι ενεργοποιημένη (ALT-B ALT-C).
    • Για να βγείτε από το διορθωτή επιλέγετε πάλι Switch (ALT-S).
    • Το αρχείο κειμένου arity.hlp περιέχει στοιχεία για όλα τα ορισμένα από την Arity Prolog κατηγορήματα.

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

    • Μ. Κατζουράκη, Μ. Γεργατσούλης και Σ. Κόκκοτος PROγραμματίζοντας στη LOGική. Εκδόσεις Νέων Τεχνολογιών, 1991.

    • Christopher John Hogger. Introduction to Logic Programming. Academic Press, 1984.

    • Robert Kowalski. Predicate logic as programming language. In Jack L. Rosenfeld, editor, Information Processing 74, Proceedings of IFIP congress 74, pages 569–574, Stockholm, Sweden, August 1974. International Federation of Information Processing, North-Holland.

    • Robert Kowalski. Logic as a computer language. In Keith L. Clark and Sten-Åke Tärnlund, editors, Logic Programming, pages 3–16. Academic Press, 1982.

    • Francis G. McCabe. Logic and Objects. Prentice Hall, 1992.

    • Richard A. O'Keefe. The Craft of Prolog. MIT Press, 1990.

    • Uday S. Reddy. On the relationship between logic and functional languages. In Doug DeGroot and Gary Lindstrom, editors, Logic Programming, Functions, Relations and Equations, pages 3–36. Prentice Hall, Englewood Cliffs, NJ, USA, 1986.

    • J. A. Robinson. A machine-oriented logic based on the resolution principle. Journal of the ACM, 12(1):23–41, January 1965.

    • Peter H. Salus, editor. Handbook of Programming Languages, volume III: Functional and Logic Programming Languages. Macmillan Technical Publishing, 1998.

    • Leon Sterling and Ehud Shapiro. The Art of Prolog. MIT Press, 1986.

    • David H. D. Warren. An abstract Prolog instruction set. Technical Note 309, SRI International, Artificial Intelligence Center, Computer Science and Technology Division, 333 Ravenswood Ave., Menlo Park, CA, USA, October 1983.

    Ασκήσεις

    Άσκηση (προαιρετική)

    1. Ορίστε σε Prolog το κατηγόρημα 
      polynomial_value(P, X, V).
      όπου:
      • Pείναι ένα πολυώνυμο ορισμένο με βάση τους όρους:
        • sum(A, B) (άθροισμα)
        • diff(A, B) (διαφορά)
        • prod(A, B) (γινόμενο)
        • pow(A, B) (ύψωση σε δύναμη)
        • τη μεταβλητή x (προσοχή, μικρό γράμμα)
        • καθώς και ακεραίους.
      • X η τιμή της μεταβλητής x
      • V η τιμή του πολυωνύμου.

    Παράδειγμα: 

    ?- polynomial_value(prod(5, pow(x, 3)), 3, X).

X = 135 ->

yes
?- polynomial_value(sum(prod(5, pow(x, 3)), prod(x, 5)), 4, X).

X = 340 ->.

yes
    Την ύψωση ενός αριθμού σε δύναμη μπορείτε να την ορίσετε ως εξής: 
    raise(X, 0, 1).
raise(X, N, Y) :-
        N2 is N - 1,
        raise(X, N2, K),
        Y is K * X.

Ταυτοχρονισμός στα Windows NT

Παραλληλία σε επίπεδο υλικού

Παραλληλία με τη χρήση αγωγών

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

Ανάγνωση αποτελεσμάτων
υπολογισμός |
μετατροπή σε λέξη |
φωνητική ανάγνωση

bc | 
number | 
speak
Συχνότητα λέξεων
Μετατροπή κειμένου σε λέξεις |
φιλτράρισμα λέξεων |
ταξινόμηση |
μέτρηση κοινών γραμμών |
ταξινόμηση

tr -cs A-Za-z '\012' | 
grep '^A-Za-z' | 
sort | 
uniq -c | 
sort -rn

Συνθήκες ανταγωνισμού

Συνθήκες ανταγωνισμού ονομάζονται οι συνθήκες κατά τις οποίες το τελικό αποτέλεσμα της εκτέλεσης μιας σειράς διεργασιών κάτω από αυτές εξαρτάται από τη σειρά εκτέλεσής τους.

Παράδειγμα

int counter;

process_one()
{
	int i;

	i = counter;
	i = i + 1;
	counter = i;
}

process_two()
{
	int i;

	i = counter;
	i = i + 1;
	counter = i;
}

Κρίσιμα τμήματα

Το τμήμα του κώδικα μιας διεργασίας το οποίο δεν είναι ασφαλές να εκτελεστεί παράλληλα με άλλη διεργασία ονομάζεται κρίσιμο τμήμα (critical section).

Κάθε λύση στο πρόβλημα του αμοιβαίου αποκλεισμού (mutual exclusion) μεταξύ των κρίσιμων τμημάτων πρέπει να εξασφαλίζει:

  1. Μια το πολύ διεργασία μπορεί να εκτελεί ένα κρίσιμο τμήμα.
  2. Δεν επιτρέπονται υποθέσεις σχετικά με την ταχύτητα ή το πλήθος των επεξεργαστών.
  3. Διεργασία που δε βρίσκεται σε κρίσιμο τμήμα δεν επιτρέπεται να αναστείλει άλλες διεργασίες
  4. Ο χρόνος στον οποίο μια διεργασία θα εισέλθει στο κρίσιμο τμήμα της πρέπει να είναι πεπερασμένος.

Ενεργός αναμονή

Ορισμένοι τρόποι για την επίτευξη του αμοιβαίου αποκλεισμού είναι οι παρακάτω: Όλες οι παραπάνω λύσεις επιβάλουν στη διαδικασία που αναμένει να εκτελεί εντολές.

Απενεργοποίηση και αφύπνιση

Η οργάνωση της διαδιεργασιακής επικοινωνίας γίνεται χρησιμοποιώντας αφηρημένες βασικές αρχές διαδιεργασιακής επικοινωνίας (interprocess communication primitives). To ζεύγος είναι μια τέτοια αρχή. Με τις κλήσεις αυτές μπορεί να εκφραστεί το πρόβλημα του παραγωγού-καταναλωτή (producer-consumer). 

const N = 100;

int queue[N];
int count;

void
producer(void)
{
	int item;

	for (;;) {
		create(&item);
		if (count == N)
			sleep();
		count = count + 1;
		queue[count - 1] = item;
		if (count == 1)
			wakeup(consumer);
	}
}

void
consumer(void)
{
	int item;

	for (;;) {
		if (count == 0)
			sleep();
		item = queue[count - 1];
		count = count - 1;
		if (count == N - 1)
			wakeup(producer);
		consume(&item);
	}
}
Η παραπάνω λύση έχει πρόβλημα συνθήκης ανταγωνισμού ως προς τη χρήση της μεταβλητής count.

Σημαφόροι

To ζεύγος των σημαφόρων (semaphores) επιτρέπει την οργάνωση της διαδιεργασιακής επικοινωνίας μια και αυτοί εκφράζουν ατομικές ενέργειες (atomic action). Με τις κλήσεις αυτές μπορεί να λυθεί το πρόβλημα του παραγωγού-καταναλωτή. 
const N = 100;

semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void
producer(void)
{
	int item;

	for (;;) {
		create(&item);
		signal(&empty);

		signal(&mutex);
		count = count + 1;
		queue[count - 1] = item;
		wait(&mutex)

		wait(&full);
	}
}

void
consumer(void)
{
	int item;

	for (;;) {
		signal(&full);

		signal(&mutex);
		item = queue[count - 1];
		count = count - 1;
		wait(&mutex);

		wait(&empty);
		consume(&item);
	}
}

Παρακολουθητές

Οι παρακολουθητές (monitors) (ή ελεγκτές) είναι δομή της γλώσσας προγραμματισμού που εξασφαλίζει ότι σε μια συγκεκριμένη χρονική στιγμή μπορεί να εκτελείται. το πολύ μια διαδικασία μέσα στον παρακολουθητή.

Η δομή αυτή εξασφαλίζει τον αμοιβαίο αποκλεισμό κρισίμων τμημάτων. H αναστολή διεργασιών που δεν μπορούν να συνεχίσουν εξασφαλίζεται με τη χρήση των μεταβλητών συνθήκης (condition variables)

Μεταβίβαση μηνύματος

Άλλος τρόπος διαδιεργασιακής επικοινωνίας είναι η χρήση της μεταβίβαση μηνύματος (message passing) που μπορεί να εκφραστεί με τις διαδικασίες: Ο συντονισμός της αποστολής και της παραλαβής μπορεί να γίνει: Με τις κλήσεις αυτές μπορεί να εκφραστεί το πρόβλημα του παραγωγού-καταναλωτή. 

const N = 100;

int queue[N];

void
producer(void)
{
	int item;
	message m;

	for (;;) {
		create(&item);
		receive(consumer, &m);
		build_message(item, &m);
		send(consumer, &m);
	}
}

void
consumer(void)
{
	int item;
	message m;

	for (i = 0;  i < 100; i++)
		send(producer, &m);
	for (;;) {
		receive(producer, &m);
		extract_item(&m, &item);
		send(producer, &m);
		consume(&item);
	}
}

Κλασικά προβλήματα

To πρόβλημα των συνδαιτημόνων φιλοσόφων

Λύσεις (σωστές και λανθασμένες):

Ταυτοχρονισμός στα Windows NT

Νηματικές διεργασίες

Οι νηματικές διεργασίες (threads) είναι ένας τρόπος ταυτοχρονισμού στον οποίο οι διεργασίες μοιράζονται τα όλα τα δεδομένα εκτός από αυτά που υπάρχουν στη στοίβα (δηλ. τις τοπικές μεταβλητές). Η δημιουργία τους υποστηρίζεται συνήθως από το λειτουργικό σύστημα και το μεταγλωττιστή. Στα Windows NT μπορούμε να δημιουργήσουμε πολλαπλές νηματικές διεργασίες με τη συνάρτηση _beginthread Χρησιμοποιείται ως εξής: 
void
thread_function(int *parameter)
{
}

/* Used to pass a parameter to the thread */
int parameter_value;

main()
{
	parameter = 42;
	_beginthread(thread_function, 0, &parameter);
}
Ένα νήμα μπορεί να τερματίσει τη λειτουργία του με τη συνάρτηση _endthread.

Σημαφόροι

Στα Windows 32 (95/98/NT/2000/...) μια σειρά από συναρτήσεις επιτρέπουν το χειρισμό σημαφόρων. Παράδειγμα αποκλεισμού περιοχής: 
HANDLE    mutex= CreateMutex(NULL, FALSE, NULL);

WaitForSingleObject(mutex, INFINITE);
/* Critical work starts here */
fseek(fp, desired_position, 0L );
fwrite(data, sizeof( data ), 1, fp );
/* Critical work ends here */
ReleaseMutex(mutex);

Μεταγλώττιση

Δηλώσεις για τις συναρτήσεις που αναφέραμε στις προηγούμενες παραγράφους υπάρχουν στην επικεφαλίδα <windows.h> και <process.h>. Για να μεταγλωττίσουμε ένα πρόγραμμα που περιέχει νηματικές διεργασίες προσθέτουμε στην εντολή του μεταγλωττιστή τις παραμέτρους /D_MT /MT . Παράδειγμα: 
cl -D_MT /MT test.c

Παράδειγμα εφαρμογής

Το παρακάτω πρόγραμμα, bounce.c (βασισμένο σε πρόγραμμα που περιέχεται ως παράδειγμα στην τεκμηρίωση της Microsoft Visual C++) δημιουργεί ένα νέο νήμα που κινεί ένα πρόσωπο στην οθόνη κάθε φορά που πληκτρολογούμε A ή a. Τερματίζει τη λειτουργία του όταν πληκτρολογήσουμε q ή Q. 
/*
 * Bounce - Creates a new thread each time the letter 'a' is typed. Each
 * thread bounces a happy face of a different color around the screen. All
 * threads are terminated when the letter 'Q' is entered. 
 *
 * This program requires the multithread library. For example, compile with the
 * following command line: CL /MT BOUNCE.C 
 */

#include <windows.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <conio.h>
#include <process.h>

const int MAX_THREADS=32;

/*
 * getrandom returns a random number between min and max, which must be in
 * integer range. 
 */
static int
getrandom(int min, int max)
{
	return ((rand() % (int)(((max) + 1) - (min))) + (min));
}

void main(void);			/* Thread 1: main */
void KbdFunc(void);			/* Keyboard input, thread dispatch */
void BounceProc(char *MyID);		/* Threads 2 to n: display */
void ClearScreen(void);			/* Screen clear */
void ShutDown(void);			/* Program shutdown */
void WriteTitle(int ThreadNum);		/* Display title bar information */

HANDLE          hConsoleOut;	/* Handle to the console */
HANDLE          hRunMutex;	/* "Keep Running" mutex */
HANDLE          hScreenMutex;	/* "Screen update" mutex  */
int             ThreadNr;	/* Number of threads started */
CONSOLE_SCREEN_BUFFER_INFO csbiInfo;	/* Console information */


void 
main()
{				/* Thread One */
	/* Get display screen information & clear the screen. */
	hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE);
	GetConsoleScreenBufferInfo(hConsoleOut, &csbiInfo);
	ClearScreen();
	WriteTitle(0);
	/* Create the mutexes and reset thread count. */
	hScreenMutex = CreateMutex(NULL, FALSE, NULL);	/* Cleared */
	hRunMutex = CreateMutex(NULL, TRUE, NULL);	/* Set */
	ThreadNr = 0;

	/* Start waiting for keyboard input to dispatch threads or exit. */
	KbdFunc();

	/* All threads done. Clean up handles. */
	CloseHandle(hScreenMutex);
	CloseHandle(hRunMutex);
	CloseHandle(hConsoleOut);
}

/*
 * Finish processing
 */
void 
ShutDown(void)
{				/* Shut down threads */
	while (ThreadNr > 0) {
		/* Tell thread to die and record its death. */
		ReleaseMutex(hRunMutex);
		ThreadNr--;
	}
	/* Clean up display when done */
	WaitForSingleObject(hScreenMutex, INFINITE);
	ClearScreen();
}

/*
 * Read an process keyboard commands
 */
void 
KbdFunc(void)
{				/* Dispatch and count threads. */
	int             KeyInfo;

	do {
		KeyInfo = _getch();
		if (tolower(KeyInfo) == 'a' && ThreadNr < MAX_THREADS) {
			ThreadNr++;
			_beginthread(BounceProc, 0, &ThreadNr);
			WriteTitle(ThreadNr);
		}
	} while (tolower(KeyInfo) != 'q');

	ShutDown();
}

/*
 * Bounce the face around the screen.
 * This procedure is run by each thread.
 */
void 
BounceProc(char *MyID)
{
	char            MyCell, OldCell;
	WORD            MyAttrib, OldAttrib;
	char            BlankCell = 0x20;
	COORD           Coords, Delta;
	COORD           Old = {0, 0};
	DWORD           Dummy;

	/* Generate update increments and initial display coordinates. */
	srand((unsigned) *MyID * 3);
	Coords.X = getrandom(0, csbiInfo.dwSize.X - 1);
	Coords.Y = getrandom(0, csbiInfo.dwSize.Y - 1);
	Delta.X = getrandom(-3, 3);
	Delta.Y = getrandom(-3, 3);

	/* Set up "happy face" & generate color attribute from thread number. */
	if (*MyID > 16)
		MyCell = 0x01;	/* outline face */
	else
		MyCell = 0x02;	/* solid face */
	MyAttrib = *MyID & 0x0F;/* force black background */

	do {
		/* Wait for display to be available, then lock it. */
		WaitForSingleObject(hScreenMutex, INFINITE);

		/* If we still occupy the old screen position, blank it out. */
		ReadConsoleOutputCharacter(hConsoleOut, &OldCell, 1, Old, &Dummy);
		ReadConsoleOutputAttribute(hConsoleOut, &OldAttrib, 1, Old, &Dummy);
		if ((OldCell == MyCell) && (OldAttrib == MyAttrib))
			WriteConsoleOutputCharacter(hConsoleOut, &BlankCell, 1, Old, &Dummy);

		/* Draw new face, then clear screen lock */
		WriteConsoleOutputCharacter(hConsoleOut, &MyCell, 1, Coords, &Dummy);
		WriteConsoleOutputAttribute(hConsoleOut, &MyAttrib, 1, Coords, &Dummy);
		ReleaseMutex(hScreenMutex);

		/* Increment the coordinates for next placement of the block. */
		Old.X = Coords.X;
		Old.Y = Coords.Y;
		Coords.X += Delta.X;
		Coords.Y += Delta.Y;

		/* If we are about to go off the screen, reverse direction */
		if (Coords.X < 0 || Coords.X >= csbiInfo.dwSize.X) {
			Delta.X = -Delta.X;
			Beep(400, 50);
		}
		if (Coords.Y < 0 || Coords.Y > csbiInfo.dwSize.Y) {
			Delta.Y = -Delta.Y;
			Beep(600, 50);
		}
	}
	/* Repeat while RunMutex is still taken. */
	while (WaitForSingleObject(hRunMutex, 75L) == WAIT_TIMEOUT);

}

void 
WriteTitle(int ThreadNum)
{
	char            NThreadMsg[80];

	sprintf(NThreadMsg, "Threads running: %02d.  Press 'A' to start a thread,'Q' to quit.", ThreadNum);
	SetConsoleTitle(NThreadMsg);
}

void 
ClearScreen(void)
{
	DWORD           dummy;
	COORD           Home = {0, 0};
	FillConsoleOutputCharacter(hConsoleOut, ' ', csbiInfo.dwSize.X * csbiInfo.dwSize.Y, Home, &dummy);
}

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

Θέματα εξετάσεων

Εξεταστική περιόδος Ιουνίου 1999

ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΙΓΑΙΟΥ

Τμήμα Πληροφοριακών και Επικοινωνιακών Συστημάτων

Γλώσσες προγραμματισμού και δομές δεδομένων

Διδάσκων: Διομήδης Σπινέλλης

Εξεταστική περίοδος

Ιουνίου 1999

Θέμα 1ο: (3 βαθμοί)

Να ορίσετε σε C μια δομή struct s_list για την παράσταση μιας συνδεδεμένης λίστας ακεραίων με τη χρήση δεικτών. Υλοποιήστε σε C τη συνάρτηση

struct s_list *find_int(int i);

που επιστρέφει δείκτη στο πρώτο στοιχείο της λίστας που περιέχει τον ακέραιο i ή NULL αν αυτός δεν υπάρχει στη λίστα. Σε μια λίστα με N στοιχεία πόσα κατά μέσο όρο στοιχεία θα εξεταστούν για να βρεθεί ο ακέραιος i;

Θέμα 2ο: (3 βαθμοί)

Μια εφαρμογή αναγνώρισης κλήσεων για γνωστή αλυσίδα διανομής φαγητού πρέπει να μπορεί γρήγορα να εμφανίσει το όνομα που αντιστοιχεί σε κάθε έναν από 5.000.000 αριθμούς τηλεφώνου. Περιγράψτε αδρά (σε λιγότερο από μια σελίδα) μια κατάλληλη τεχνολογία ή δομή δεδομένων που να ικανοποιεί την απαίτηση αυτή καθώς και την τεχνική αναζήτησης που θα πρέπει να χρησιμοποιηθεί.

Θέμα 3ο: (3 βαθμοί)

Για την παρακάτω κλάση της C++ που ορίζει μια στοίβα 100 ακεραίων υλοποιήστε τις συναρτήσεις stack, push και pop. Γράψτε σε C++ ένα πρόγραμμα που να διαβάζει 40 ακεραίους και να τους τυπώνει με ανάποδη σειρά (από το τέλος προς την αρχή). 

class stack {
private:
        int sp;			// Stack pointer
        int elem[100];		// Stack elements
public:
        stack(void);		// Constructor
        void push(int i);
        int pop(void);
};

Θέμα 4ο: (3 βαθμοί)

Η παρακάτω συνάρτηση της Lisp επιστρέφει το παραγοντικό του αριθμού n: 

(defun factorial (n)
        (if (equal n 0)
        1
        (* n (factorial (- n 1)))))

Ορίστε με ανάλογο τρόπο συνάρτηση σε Lisp που να υπολογίζει τον νοστό όρο της ακολουθίας Fibonacci δεύτερης τάξης:

F0 = 0, F1 = 1, Fn + 2 = Fn + 1 + Fn + Fn

Το άριστα ορίζεται ως 10 βαθμοί.
Διάρκεια εξέτασης 2,5 ώρες Καλή επιτυχία!

Εξεταστική περιόδος Σεπτεμβρίου 1999

ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΙΓΑΙΟΥ

Τμήμα Πληροφοριακών και Επικοινωνιακών Συστημάτων

Γλώσσες προγραμματισμού και δομές δεδομένων

Διδάσκων: Διομήδης Σπινέλλης

Εξεταστική περίοδος

Σεπτεμβρίου 1999

Θέμα 1ο: (3 βαθμοί)

Να ορίσετε σε C μια δομή struct s_btree για την παράσταση ενός δυαδικού δένδρου αναζήτησης χαρακτήρων. Υλοποιήστε σε C τη συνάρτηση 

  struct s_btree *find_char(struct s_btree *root, char c);
που επιστρέφει δείκτη στο στοιχείο του δένδρου που περιέχει τον ακέραιο c ή NULL αν αυτός δεν υπάρχει στο δένδρο.

Θέμα 2ο: (3 βαθμοί)

Ένα ταξιδιωτικό γραφείο σας ζητάει ένα πρόγραμμα που να μπορεί να απαντά σε ερωτήσεις του τύπου "ποιες πτήσεις πρέπει να ακολουθήσω για να πάω από τη Σάμο στο Κατμαντού;" (Σάμος - Αθήνα - Άμστερνταμ - Πεκίνο - Κατμαντού). Σε ποια δομή δεδομένων θα πρέπει να βασιστεί ένα τέτοιο πρόγραμμα; Περιγράψτε (με ένα μικρό παράδειγμα σε C) έναν τρόπο υλοποίησης της δομής αυτής.

Θέμα 3ο: (3 βαθμοί)

Για την παρακάτω κλάση της C++ που ορίζει μια ουρά 100 ακεραίων υλοποιήστε τις συναρτήσεις queue, add και remove. Γράψτε σε C++ ένα πρόγραμμα που να διαβάζει ακεραίους και, αφού διαβάσει τους πρώτους 20, να τους τυπώνει με τη σειρά ανάγνωσης: έναν αριθμό για κάθε νέο ακέραιο που θα διαβάζει. (Όταν δηλαδή διαβάσει τον 21ο θα τυπώσει τον 1ο, μετά τον 22ο θα τυπώσει τον 2ο, κ.ο.κ.) 

class queue {
private:
        int head;		// Pointer to the queue head
        int tail;               // Pointer to the queue tail
        int elem[100];		// Queue elements
public:
        queue(void);		// Constructor
        void add(int i);	// Adds an integer to the queue tail
        int remove(void);	// Removes and returns an integer from
				// the queue head
};

Θέμα 4ο: (3 βαθμοί)

Τα παρακάτω κατηγορήματα της Prolog ορίζουν τους ακέραιους αριθμούς (nat) και την πρόσθεση με βάση τον όρο suc που ορίζει τον επόμενο ενός ακεραίου: 

nat(0).
nat(suc(X)) :-
        nat(X).	

plus(0, X, X) :-
        nat(X).

plus(suc(X), Y, suc(Z)) :-
        plus(X, Y, Z).
Να ορίσετε, βασισμένοι στα παραπάνω, το κατηγόρημα double(X, Y) που είναι αληθές όταν και μόνο όταν το Υ είναι το διπλάσιο του Χ.

Το άριστα ορίζεται ως 10 βαθμοί.
Διάρκεια εξέτασης 2,5 ώρες Καλή επιτυχία!

Αποτελέσματα ασκήσεων

Βαθμοί ασκήσεων 1-6

Α.Μ.    Βαθμός
-----   ------
98001	5
98002	0
98003	0
98004	7
98005	0
98006	2
98007	7
98008	0
98009	6
98010	0
98011	6
98012	3
98013	0
98014	0
98015	1
98016	0
98017	6
98018	0
98019	4
98020	5
98021	0
98022	7
98023	0
98024	0
98025	0
98026	0
98027	7
98028	4
98029	7
98030	1
98031	0
98032	0
98033	0
98034	0
98035	1
98036	1
98037	7
98038	0
98039	1
98040	0
98041	0
98042	5
98043	0
98044	1
98045	6
98046	6
98047	7
98048	7
98049	6
98050	2
98051	0

Creative Commons License  Τελευταία αλλαγή: Δευτέρα, 2 Αυγούστου 2004 12:52 πμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».