- 16.09.2007
Wykład: Trzy algorytmy potęgowania, poprawność i złożoność algorytmu
Laboratorium: Porównanie dwóch metod obliczania potęgi (patrz slady z wykładu algorytm pierwszy i trzeci).
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).
- 23.09.2007
Wykład: Rzędy wielkości funkcji. Algorytmy obliczania symbolu Newtona - metoda dynamiczna
Laboratorium: Porównanie metod obliczania symbolu Newtona (patrz slady z 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 dla każdej metody obliczyć 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).
- 30.09.2007
Wykład: Metody sortowania: wybieranie, wstawianie, bąbelkowe, Shella
Laboratorium: Porównanie 2 metod sortowania
- 21.10.2007
Wykład: Listy, kolejki, stosy
Laboratorium: Implementacja kolejki jako dwóch stosów:
Stos należy zaimplementować jako listę liniową jednokierunkową a kolejkę jako
rekord zawierający dwa stosy: jeden do wkładania elementów a drugi do pobierania.
Jesli pobieramy pierwszy element z kolejki a stos do pobierania jest pusty, to wszystkie elementy
ze stosu do wkładania są przerzucane na stos do pobierania i wtedy pobieramy
element. Podobnie w przypadku operacji POP.
type
Lista = ^Element;
Element = record
liczba: integer;
nast: Lista;
end;
Stos = Lista;
function Pusty(S: Stos): boolean;
function NaGorze(S: Stos): integer;
procedure Push(var S: Stos; a: integer);
{ należy utworzyć nowy Element
new(e)
i przypisać
e^.liczba := a
i potem wstawić Element e na górze stosu (na początku listy)
}
procedure PopS(var S: Stos);
procedure Przerzuc(var Sin, Sout: Stos); {przerzucanie elementów ze stosu Sin do Sout}
type
Kolejka = record
stos_in, stos_out: Stos;
end;
function Pusta(K: Kolejka): boolean; {czy oba stosy są puste}
function Pierwszy(K: Kolejka): integer;
{podaje liczbę w pierwszym elemencie stos_out przerzucając wcześniej
elementy ze stos_in jeśli trzeba}
procedure Dodaj(var K: Kolejka; a: integer); {robi Push do stos_in}
procedure PopK(var K: Kolejka);
{usuwa pierwszy element ze stos_out przerzucając wcześniej
elementy ze stos_in jeśli trzeba}
- 04.11.2007
Wykład: Sortowanie przez scalenie i
szybkie.
Laboratorium: Zaimplementować sortowanie przez scalanie przy użyciu kolejek.
Należy użyć jednostki LISTY (uses LISTY), której interfejs wyglada tak
unit Listy;
interface
type
Lista = ^Element;
Element = record .... end;
Kolejka = record ....
Count: word; {ilość elemetów w kolejce}
end;
procedure Init(var K: Kolejka);
function Pusta(K: Kolejka): boolean;
function Pierwszy(K: Kolejka): real;
procedure Inject(var K: Kolejka; x: real);
procedure Pop(var K: Kolejka);
(Pełna wersja: listy.pas.)
Należy zaimplementować procedury:
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.
- 25.11.2007
Wykład: Sortowanie przez kopcowanie,
sortowanie leksykograficzne (pozycyjne).
Laboratorium: Implementacja sortowania leksykograficznego przy użyciu kolejek.
- 09.12.2007
Wykład: Sortowanie przez wstawianie połówkowe,
drzewa binarnego wyszukiwania (BST)
Laboratorium: Implementacja operacji na drzewach BST.
- 20.01.2008
Wykład: UNION-FIND
Laboratorium: Porównanie implementacji algorytmu UNION-FIND.
{listowa}
var Zbior: array[1..n] of 1..n;
var Pierwszy: array[1..n] of 0..n; (* 0 - brak elementow we zbiorze *)
var Nastepny: array[1..n] of 0..n; (* 0 - brak nastepnego elementu *)
procedure Init1;
(* Zbior[i]:=i, Pierwszy[i]:=i, Nastepny[i]:=0 *)
function FIND1(i: integer): integer;
(* zbior, do ktorego nalezy element i *)
(* tzn. Zbior[i] *)
procedure UNION1(i,j: integer);
(* zakladamy, ze i <> j; dolaczamy zbior j do i *)
{drzewiasta}
var Ojciec: array[1..n] of 0..n; (* 0 - brak ojca *)
var Ilosc: array[1..n] of 1..n; (* ilosc reprezentowanych elementow *)
procedure Init2; (* wpisuje zera do Ojciec i jedynki do Ilosc *)
function FIND2(i: integer): integer;
(* rekurencyjnie znajduje reprezentanta elementu i *)
(* uzywajac tablicy Ojciec *)
procedure UNION2(i,j: integer); (* zakladamy, ze i <> j oraz i i j nie maja ojcow *)
(* laczymy zbiory reprezentowane przez i i j *)
- 03.02.2008
Wykład: Grafy, tablica list incydencji , przeglądanie grafu wszerz i w głąb. Algorytm Kruskala (użycie UNION-FIND)
Laboratorium: Implementacja przeglądania grafu wszerz lub w głąb lub algorytmu Kruskala.
{UNION-FIND}
{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;