Każdy algorytm działa w pewnym środowisku: w jednym algorytmie wykorzystujemy liczby naturalne i operacje na nich, inny algorytm używa operacji na zbiorach, a jeszcze inny jest napisany z myślą o pewnych specjalnych obiektach, określonych przez twórcę algorytmu z myślą o pewnej specjalnej aplikacji. Środowisko, w którym działa algorytm nazywać będziemy strukturą danych tego algorytmu. Wartości zmiennych i operacje pochodzą właśnie z tej przewidzianej dla danego algorytmu struktury danych. Struktura danych dostarcza interpretacji dla formalnego tekstu, którym jest algorytm. Zdarza się nierzadko, że ten sam algorytm interpretowany w różnych strukturach danych różnie się zachowuje i, co więcej, rozwiązuje zupełnie różne problemy.

Kleene{

	for k:=1 to n do
	for i :=1 to n do
	for j := 1 to n do
	c[i,j] := c[i,j] Å (c[i,k] Ä c[k,j]);
	od od
	od ;
	result := c;
}

Pierwsza interpretacja. Jeśli 0 oznacza wartość logiczną fałsz, a 1 wartość logiczną prawda, oraz operacje Å , Ä są operacjami alternatywy i koniunkcji,

to przedstawiony algorytm znajduje tranzytywne domknięcie grafu, którego macierzą incydencji jest początkowa wartość tablicy c. Rzeczywiście, w każdym kroku zewnętrznej pętli, dla dowolnych dwóch wierzchołków i, j badamy, czy istnieje jakaś droga od i do j przechodząca przez wierzchołek k. Jeżeli istnieje droga od i do k (tzn. gdy c[i,k]=1) oraz, gdy istnieje droga od k do j (tzn.c[j,k]=1) wtedy istnieje droga od i do j, a wartością c[i,j] będzie 1.

Druga interpretacja. Jeśli przyjmiemy, że tablica c jest macierzą incydencji pewnego grafu z wagami, gdzie c[i,j] jest liczbą rzeczywistą dodatnią określającą długość drogi od wierzchołka i do wierzchołka j w tym grafie lub +¥, gdy takiej drogi nie ma, oraz operacje Å , Ä są określone następująco:

u Å w =^df min(u, w), dla dowolnych liczb rzeczywistych u, w, i +¥ Å w =^df w, u Å +¥ =^df u

u Ä w =^df (u + w), dla dowolnych liczb rzeczywistych u, w i +¥ Ä w =^df +¥, u Å +¥ =^df +¥ ,

to algorytm oblicza najkrótszą drogę od dowolnego wierzchołka do dowolnego innego. Tak jak w poprzedniej interpretacji, badamy dla ustalonego k wszystkie drogi, które przechodzą przez wierzchołek k. Jeśli istnieje droga od i do k o długości c[i,k] oraz istnieje droga od k do j o długości c[k,j], to istnieje też droga od i do j o długości c[i,k]+c[k,j]. Wybierając mniejszą z liczb c[i,j] (dotychczasowa droga) i c[i,k]+c[k,j] zapewnimy, że wartością c[i,j] jest długość najkrótszej możliwej drogi od i do j.

Definicja 3.1

Strukturą danych nazywać będziemy system algebraiczny postaci <U, o₁,...,o_n; r₁,...,r_m>, gdzie U jest dziedziną, w której określone są operacje o₁,...,o_n i relacje r₁,...,r_mstruktury. Każda operacja i każda relacja ma określony typ, tzn. liczbę i typy argumentów oraz typ wyniku. Zwykle zakłada się też, że operacje i relacje są programowalne.
Typy operacji i relacji, to sygnatura struktury.

Przykładem struktury danych są podstawowe struktury arytmetyczne zaimplementowane na każdym komputerze i umożliwiające operacje typu dodawania liczb rzeczywistych, mnożenia, porównywania itd. Innym przykładem struktury jest tablica. Operacje jakie na tablicach wykonujemy, to wstawianie elementu na wybraną pozycję, sprawdzanie zawartości wskazanego elementu etc.

Uwaga. Zwykle, będziemy milcząco zakładali, że te podstawowe struktury są integralną częścią omawianych w wykładzie struktur danych.

Działanie algorytmu zależy ściśle od struktury danych, w której on działa. Jeśli mamy badać zachowanie algorytmu, analizować jego zachowanie i koszt, musimy wcześniej poznać własności przyjętej struktury danych. Oczywiście, implementacja struktury danych, jest wystarczającym jej opisem, pozwalającym poznać wszystkie własności struktury. Czy jednak taki sposób poznawania właściwości struktury jest wygodny? Implementacja struktury danych musi zawierać definicje operacji, które mogą przecież być skomplikowanymi programami. Z punktu widzenia algorytmu, który ma działać w tej strukturze, nie zawsze jest istotne, jak została ona zaimplementowana. Często implementacją struktury danych zajmuje się inna osoba, nie autor algorytmu. Często strukturę danych możemy "wziąć z półki". Analizowanie własności takiej struktury przez "rozgryzanie" szczegółów implementacji byłoby karkołomnym zajęciem. Dlatego też, struktura danych powinna być wyspecyfikowana. Specyfikacja powinna być zwięzła, ale jednocześnie powinna zawierać wszystkie istotne cechy charakteryzujące specyfikowaną strukturę.

Definicja 3.2

Specyfikacją struktury danych nazywać będziemy parę {S, Ax}, gdzie S jest sygnaturą struktury danych, a Ax zbiorem formuł (postulatów), których prawdziwość w tej strukturze zakładamy.

Sygnatura pozwala ustalić jakiego typu operacje i relacje będą dostępne w tej strukturze. Postulaty natomiast, mają charakteryzować operacje i relacje tej struktury. Byłoby najlepiej, gdyby specyfikacja definiowała z dokładnością do izomorfizmu całą strukturę, ale nie zawsze jest to możliwe. W następnych wykładach poznamy przykłady konkretnych struktur danych i ich specyfikacji. Tu, dla przykładu, przedstawimy specyfikację struktury liczb naturalnych, ograniczonych przez stałą Max, z jednoargumentową operacją cyklicznego następnika s, stałymi 0 i Max oraz relacją identyczności =. Postulaty tej struktury są następujące

Pierwszy postulat mówi, że s jest funkcją różnowartościową, drugi postulat definiuje następnik elementu Max, a trzeci zapewnia, że każdy element struktury może być otrzymany z zera przez sukcesywne zastosowanie następnika. Ten ostatni postulat nie jest wyrażalny w języku logiki klasycznej, ale możemy go zapisać jako własność programu: program {x:= 0; while not (x=y) do x:= s(x) od} zatrzymuje się dla dowolnych danych w tej strukturze.

Pytanie 3: Co robi algorytm Kleene, jeśli operacja Å odpowiada wzięciu maksimum z dwóch liczb, a operacja Ä wzięciu minimum, oraz wartości początkowe tablicy c[i,j] zinterpretujemy jako ciężar, który może być przetransportowany wzdłuż krawędzi (i,j) pewnego grafu?