- 01.10.2007
Wykład: Poprawność i złożoność algorytmu, rzędy wielkości funkcji
Laboratorium: Porównanie trzech metod obliczania potęgi (patrz slajdy z wykładu 1.1-1.3).
Należy dla każdej metody obliczyć ilość wykonanych mnożeń oraz podać czas działania
(przykład oblicznia czasu działania: czas.pas).
Żeby czas był miarodajny należy obliczenia wykonać odpowiednio dużą ilość razy (np. 30000).
- 08.10.2007
Wykład: Hierarchia wielkości funkcji. Algorytmy obliczania symbolu Newtona - metoda dynamiczna
Laboratorium: Porównanie metod obliczania symbolu Newtona (patrz slajdy do wykładu):
- metody 1,2,3 - slajd 5,
- metoda 4 - funkcja wywolująca metode 2 lub 3 w zależności jakie jest n,
- metoda 5 - funkcja rekurencyjna ze slaidu 5.2,
- metoda 6 - slajd 5.3,
- metoda 7 - slajd 5.5.
Należy sprogramować każdą metodę jako oddzielną funkcję
function MetodaX(m,n: integer): integer;
begin
...
end;
Funkcje te mają tylko dokonywać obliczeń bez instrukcji czytania i pisania oraz bez mierzenia czasu.
Należy dla każdej metody policzyć (używając odpowiednich liczników) ilość
wykonanych mnożeń (metody 1-4) lub dodawań (metody 5-7)
oraz podać czas działania
(przykład oblicznia czasu działania: czas.pas).
Żeby czas był miarodajny należy obliczenia wykonać odpowiednio dużą ilość razy (np. 30000).
- 15.10.2007
Wykład: Metody sortowania: zliczanie, wybieranie, wstawianie, bąbelkowe, Shella
26.10.2006
Laboratorium: Porównanie 3 metod sortowania.
Należy wczytać liczby z pliku liczby.txt do trzech tablic. Każdą tablicę
należy posortować inną metodą licząc porównania i przypisania w oddzielnych
licznikach. Wynikowe tablice należy porównać i podać wartości liczników.
- 22.10.2007
Wykład: Listy, kolejki, stosy.
Laboratorium: Zaimplementować stos jako listę jednokierunkową z ilością elementów:
type
List = ^Element;
Element = record
nbr: integer;
next: List;
end;
Stack = record
First: List;
Count: word;
end;
procedure Init(var S: Stack);
function Empty(S: Stack): boolean;
function First(S: Stack): integer;
procedure Push(var S: Stack; i: integer);
procedure Pop(var S: Stack);
- 28.11.2007
Wykład: Sortowanie przez scalenie i szybkie. Metoda ,,dziel i zwyciężaj''
Laboratorium: Zaimplementować sortowanie przez scalanie przy użyciu kolejek.
Należy użyć jednostki LISTY.TPU (uses LISTY), której interfejs wyglada tak
(tego nie należy kopiować do programu)
Pełna wersja: listy.pas.
Program powinien wyglądać tak:
Program MergeSort;
uses Listy, crt;
procedure Dziel(var K,K1,K2: Kolejka);
begin
{ Dzieli kolejkę K na dwie części, które zapisuje do K1 i K2}
end;
procedure Scal(var K1,K2,K: Kolejka);
begin
{ scala posortowane kolejki K1 i K2 w pustą kolejkę K }
end;
procedure SortowaniePrzezScalanie(var K: Kolejka);
var K1,K2: Kolejka;
begin
Init(K1);
Init(K2);
if K.Count > 1 then
begin
Dziel(K,K1,K2);
SortowaniePrzezScalanie(K1);
SortowaniePrzezScalanie(K2);
Scal(K1,K2,K);
end;
end;
var K: Kolejka;
begin
{ Wczytanie z pliku 'dane.txt' liczb do sortowanie do kolejki K }
SortowaniePrzezScalanie(K);
{ Wypisanie kolejki K }
end.
- 05.11.2007
Wykład: Sortowanie przez kopcowanies.
Laboratorium: Implementacja sortowania szybkiego przy użyciu kolejek.
Program QuickSort;
uses Listy, crt;
procedure Dziel(var K: Kolejka; var x: real; var K1,K2: Kolejka);
begin
{ Dzieli kolejkę K na trzy części:
x - pierwszy element w kolejce K,
K1 - elementy z kolejki K mniejsze od x,
K2 - pozostałe elementy}
end;
procedure Scal(var K1: Kolejka; x: real; var K2,K: Kolejka);
begin
{ robi jedną kolejkę K z K1, x i K2}
end;
procedure SortowanieSzybkie(var K: Kolejka);
var K1,K2: Kolejka; x: real;
begin
if K.Count > 1 then
begin
Init(K1);
Init(K2);
Dziel(K,x,K1,K2);
SortowanieSzybkie(K1);
SortowanieSzybkie(K2);
Scal(K1,x,K2,K);
end;
end;
var K: Kolejka;
begin
{ Wczytanie z pliku 'dane.txt' liczb do sortowanie do kolejki K }
SortowanieSzybkie(K);
{ Wypisanie kolejki K }
end.
- 12.11.2007
Wykład: Sortowanie przez wstawianie połówkowe, sortowanie leksykograficzne (pozycyjne).
Laboratorium: Implementacja sortowania leksykograficznego przy użyciu kolejek.
Należy przerobić jednostkę listy.pas tak, aby w kolejkach trzymać liczby całkowite.
function Cyfra(k,x: integer): integer; { (k-ta od końca cyfra liczby x) = (x div (10^(k-1)) mod 10 }
begin ... end;
var GK: Kolejka; {główna kolejka}
KolejkiCyfr: array[0..9] of Kolejka;
k,x: integer;
begin
... {zerowanie kolejek}
... {wczytowanie liczb 4-cyfrowych do posortowania do kolejki GK}
for k:=1 to 4 do
begin
while not Pusta(GK) do
begin
{Pobranie liczby x z kolejki GK}
{Wstawienie liczby x do kolejki z tablicy KolejkiCyfr pod numerem Cyfra(k,x)}
end;
... {przerzucenie liczb z KolejekCyfr do GK}
end;
... {wypisanie liczb z GK}
end.
- 19.11.2007
Wykład: Drzewa binarnego wyszukiwania (BST).
Laboratorium: Implementacja podstawowych operacji na drzewach BST.
- IX(26.11.2007)
Wykład: Drzewa AVL.
Laboratorium: Implementacja podstawowych operacji na drzewach AVL.
- X(03.12.2007)
Wykład: UNION-FIND
Laboratorium: Implementacja podstawowych operacji na drzewach AVL.
- XI(10.12.2007)
Wykład: Grafy, tablica list incydencji , przeglądanie grafu wszerz i w głąb. Algorytm Kruskala (użycie UNION-FIND)
Laboratorium: Implementacja algorytmu Kruskala.
{UNION-FIND}
var Ojciec: array[1..n] of 0..n; (* 0 - brak ojca *)
var Ilosc: array[1..n] of 1..n; (* ilosc reprezentowanych elementow *)
procedure Init_UNION_FIND; (* wpisuje zera do Ojciec i jedynki do Ilosc *)
function FIND(i: integer): integer; (* rekurencyjnie znajduje reprezentanta elementu i *)
(* uzywajac tablicy Ojciec *)
procedure UNION(i,j: integer); (* zakladamy, ze i <> j oraz i i j nie maja ojcow *)
(* laczymy zbiory reprezentowane przez i i j *)
{KRUSKAL}
var Wedges: array[1..m] of record
start, koniec, waga: integer;
end;
ReadGraph; { wczytuje z pliku m krawedzi (trojek liczb) }
SortWedges; { sortuje krawedzie wg wag }
Init_UNION_FIND;
for i:=1 to m do
begin
p:=FIND(Wedges[i].start);
k:=FIND(Wedges[i].koniec);
if p <> k then
begin
{ wypisz krawedz }
UNION(p,k);
end;
end;
- XII(17.12.2007)
Wykład: Algorytmy znajdujące najkrótsze drogi w grafie z wagami. Algorytm Dijkstry.
Laboratorium: Implementacja algorytmu Dijkstry.
const n = 30;
var G : array[1..n,1..n] of integer;
var D,Z : array[1..n] of integer;
var Kopiec :
record
rozmiar : integer;
wierzcholki : array[1..n] of 1..n;
miejsce : array[1..n] of 1..n;
end;
procedure Popraw(a : integer);
var b,c : integer;
begin
b:=a;
if (2*a <= Kopiec.rozmiar) and (D[Kopiec.wierzcholki[a]] > D[Kopiec.wierzcholki[2*a]])
then b := 2*a
else
if (2*a+1 <= Kopiec.rozmiar) and (D[Kopiec.wierzcholki[b]] > D[Kopiec.wierzcholki[2*a+1]])
then b := 2*a+1;
if (a <> b) then
begin
Kopiec.miejsce[Kopiec.wierzcholki[a]] := b;
Kopiec.miejsce[Kopiec.wierzcholki[b]] := a;
c := Kopiec.wierzcholki[b];
Kopiec.wierzcholki[b] := Kopiec.wierzcholki[a];
Kopiec.wierzcholki[a] := c;
Popraw(b);
end;
end; { Popraw }
procedure TwotrzKopiec;
var a : integer;
begin
Kopiec.rozmiar := n;
for a:=1 to n do Kopiec.miejsce[a] := a;
for a:=n div 2 downto 1 do
Popraw(a);
end; { TwotrzKopiec }
function UsunZKopca: integer;
var a : integer;
begin
a := Kopiec.wierzcholki[1];
Kopiec.wierzkolki[1]:=Kopiec.wierzcholki[Kopiec.rozmiar];
dec(Kopiec.rozmiar);
Popraw(1);
UsunZKopca := a;
end; { UsunZKopca }
procedure ReorganizujKopiec(b : integer);
var a1,a2,c : integer;
begin
a1 := Kopiec.miejsce[b];
a2 := a1 div 2;
while (a1 > 1) and (D[Kopiec.wierzcholki[a1]] < D[Kopiec.wierzcholki[a2]]) do
begin
Kopiec.miejsce[Kopiec.wierzcholki[a1]] := a2;
Kopiec.miejsce[Kopiec.wierzcholki[a2]] := a1;
c := Kopiec.wierzcholki[a2];
Kopiec.wierzcholki[a2] := Kopiec.wierzcholki[a1];
Kopiec.wierzcholki[a1] := c;
a1 := a2;
a2 := a1 div 2;
end;
end; { ReorganizujKopiec }
var A,B : integer; Q : Kolejka;
begin
{wczytanie grafu do tablicy G
G[a,a] = 0
G[a,b] - waga krawedzi a-b
jesli nie ma krawedzi a-b wtedy G[a-b] = 1000
}
{inicjalizacja tablicy odleglosci D
D[1] = 0
D[a] = waga krawedzi 1-a
}
TworzKopiec; {tworzymy Kopiec wierzcholkow: najblizszy na szczycie}
while Kopiec.rozmiar > 0 do
begin
A := UsunZKopieca; {usuwa szczyt i reorganizuje Kopiec}
for B := 1 to n do
if D[A]+G[A,B] < D[B] then
begin
D[B] := D[A]+G[A,B];
Z[B] := A; {przedostatnim przystatnkiem w najkrotszej drodze z 1 do B jest A}
ReorganizujKopiec(B);
end;
end;
write('Podaj wierzcholek: '); readln(A);
writeln('Najkrotsza droga: 1');
B:=A;
Init(Q);
while B <> 1 do
begin
Inject(Q, B);
B:=Z[B];
end;
while not Empty(Q) do
begin
write(' -> ',First(Q));
Pop(Q);
end;
writeln;
writeln('Waga = ',D[A]);
end;
- XIII(14.01.2008)
Wykład: Wyszukiwanie wzorca w tekście
Algorytm Knutha-Morrisa-Pratta
- XIV(21.01.2008)