Termin: poniedziałek, 8:30-10:00, s. 2041 lub 2100
Prowadzący: Sławek Kolasiński
Kontakt: initial.lastname @ mimuw.edu.pl
Konsultacje: sala 4500 MIM UW, poniedziałek 10:15 - 11:45 lub po indywidualnym umówieniu się.
Uwaga! Rozwiązania nadesłane lub zmieniane po tym terminie będą oceniane w skali od 0 do 5 punktów.
Zaimplementować kolejkę za pomocą listy. Należy napisać następujące procedury i funkcje:
enqueue(Q,x)
- dodaje na koniec kolejki
Q
wartość x
,
dequeue(Q) : typ
- usuwa z początku kolejki
Q
pierwszy element i zwraca jego wartość,
is_empty(Q) : boolean
- zwraca
true
jeśli kolejka Q
jest pusta,
init(Q)
- inicjalizuje kolejkę Q
,
fst(Q) : typ
- zwraca wartość pierwszego
elementu kolejki Q
bez usuwania go.
Należy pamiętać o prawidłowym przekazywaniu parametrów (przez wartość lub przez referencję).
Rozwiązania należy napisać na komputerze i wysłać mi plik źródłowy
.pas
. Każdy kto rozwiąże zadanie może być poproszony o
zaprezentowanie go w całości lub we fragmentach na ćwiczeniach.
Dla ułatwienia załączam przykładowe rozwiązanie zadania, które było na ostatnich ćwiczeniach: stos.
Napisać procedurę
procedure flawiusz(var l : lista; k : integer);
która będzie usuwać z cyklicznej listy l
co
k
-ty element, aż zostanie na niej dokładnie jeden
element.
Przykład:
l = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
Po wykonaniu
k = 3
flawiusz(l,k)
l = [ 4 ]
Przykładowe rozwiązania zadań, które były na ostatnich ćwiczeniach: listy.
Napisać funkcję
function najblizsza(l : lista, x : real) : lista;
gdzie lista
jest teraz listą liczb rzeczywistych typu
real
. Funkcja ma znaleźć na liście element najbliższy
wartości x
i zwrócić wskaźnik na ten element listy.
Przykładowe rozwiązania zadań z zajęć 2 marca: z pliku.
Napisać funkcję
function max_pelne(t : drzewo) : drzewo;
która zwróci wskaźnik do maksymalnego pełnego poddrzewa binarnego.
Drzewo binarne jest pełne jeśli
t1
i t2
zawierają takie
same elementy. Dlaczego drzewo t1
ma wysokość 14,
a drzewo t2
tylko 5.
predfs_print
, indfs_print
oraz
postdfs_print
.
nil
.
Napisać funkcję
function jest_bst(t : drzewo) : boolean;
która sprawdzi czy dane drzewo jest drzewem BST (tzn. czy w każdym
wierzchołku spełniona jest zależność, że w lewym poddrzewie są
elementy mniejsze, a w prawym niemniejsze).
liczba_lisci
oraz
liczba_wezlow
zliczajace liście i węzły drzewa.
procedure usun_korzen(var t : drzewo);
t
tak, by wynikowe drzewo
nadal było drzewem BST.
usun_korzen
z
poprzedniego zadania, napisz procedurę
procedure usun(var t : drzewo; x : typ);
t
dowolny węzeł zawierający
wartość x
.
function zbalansowane(t : drzewo) : boolean;
Drzewo jest zbalansowane jeśli w każdym wierzchołku spełnony jest warunek, że różnica wysokości lewego i prawego poddrzewa wynosi co najwyżej 1.
procedure kasuj(var t : drzewo);
Tym razem nie ma zadania domowego.
zbalansowane
max_pelne
jest_bst
najblizsza
flawiusz
Napisać na komputerze rozwiązania zadań z poprzedniego i obecnego tygodnia. Skompilować i uruchomić. Wymyślić i napisać testy.
Napisać funkcję function galaz(t : drzewo) :
drzewo
, która zwróci wskaźnik do najdłuższej
gałęzi drzewa t
.
Przez gałąź rozumiemy drzewo, w którym każdy węzeł ma stopień 1.
Napisać funkcję function suma(t : drzewo) :
typ
, która zwróci sumę wartości zapisanych w
węzłach drzewa.
Napisać funkcję function srednia(t : drzewo) :
typ
, która zwróci srednią z wartości zapisanych
w węzłach drzewa.
Napisać funkcję function wysrodkowanie(t :
drzewo) : typ
, która obliczy współczynnik
wyśrodkowania drzewa BST.
Wyśrodkowanie drzewa to suma 3 składników:
wyśrodkowania lewego poddrzewa,
wyśrodkowania prawego poddrzewa oraz
różnicy wartości w korzeniu ze średnią z całego drzewa
Można to zapisać wzorem:
wysrodkowanie(t) = wysrodkowanie(t^.lewy) + wysrodkowanie(t^.prawy) + (t^.wartosc - srednia(t))
Napisać funkcję function ciezar(t : drzewo) :
typ
, która zwróci ciężar drzewa.
Ciężar drzewa to suma wag wszystkich węzłów. Waga węzła to wartość w nim zapisana przemnożona przez poziom, na którym się znajduje. Zakładamy, że korzeń jest na poziomie 1.
Dany jest graf zorientowany G = (V, E)
reprezentowany
przez listy incydencji. Napisać procedurę tworzącą graf
transponowany G' = (V, E')
, gdzie E'
zawiera parę (u,v)
wtedy i tylko wtedy gdy
E
zawiera parę (v,u)
.
Sciągnąć plik graph.pas, obejrzeć i skompilować.
Dopisać procedury i funkcje:
procedure gr_dodaj_krawedz(var g : graf; u,v : integer);
- dodającą krawędź (u,v)
do grafu g
.
function gr_jest_krawedz(var g : graf; u,v : typ) : boolean;
- sprawdzającą czy w grafie g
jest krawędź
(u,v)
.
function gr_stopien(var g : graf; u : integer) : integer;
- obliczającą stopień wierzchołka u
w grafie
g
.
procedure gr_drukuj(var g : graf);
- drukującą graf g
na ekranie.
Dany jest plik, w liniach którego są różne pary liczb całkowitych. Napisać procedurę, która stworzy graf reprezentowany jako listy incydencji taki, że pary z pliku to krawdzie tego grafu.
Przy testowaniu można się posłużyć plikiem graf.txt.
Zmodyfikować rozwiązanie poprzedniego zadania tak, by
stworzyć graf niezorientowany. Krawędź niezoreintowaną
{u,v}
reprezentujemy jako parę krawędzi
zorientowanych (u,v)
i
(v,u)
. Żądamy ponadto, by w wynikowym grafie,
między każdą parą wierzchołków była co najwyżej jedna
krawędź.
Dany jest spójny, niezorientowany graf G
, który jest
drzewem (tzn. nie ma cykli). Oblicz średnicę
G
, czyli długość najdłuższej ścieżki w
G
.
Dokończenie z poprzednich zajęć.
Zmodyfikować procedurę wczytującą graf z pliku tak, by
tworzyła graf niezorientowany. Krawędź niezoreintowaną
{u,v}
reprezentujemy jako parę krawędzi
zorientowanych (u,v)
i
(v,u)
. Żądamy ponadto, by w wynikowym grafie,
między każdą parą wierzchołków była co najwyżej jedna
krawędź.
Jak można by zmodyfikować naszą reprezentację grafu, by wygodniej operowało się na grafach niezorientowanych? Mając jakiś węzeł i element listy sąsiadów, reprezentujący jakąś krawędź, chcielibyśmy mieć łatwy dostęp do krawędzi skierowanej w drugą stronę. Jak to zrobić?
Zadanie domowe z poprzednich zajęć.
Dany jest graf zorientowany G = (V, E)
reprezentowany przez listy incydencji. Napisać procedurę
tworzącą graf transponowany G' = (V, E')
,
gdzie E'
zawiera parę (u,v)
wtedy i tylko wtedy gdy E
zawiera parę
(v,u)
.
Sciągnąć plik graph2.pas, obejrzeć i skompilować.
Plik ten dzieli się na kilka części oddzielonych wyraźnym
komentarzem. Jest tam implementacja listy jednokierunkowej
(operacje z prefiksem l_
), a następnie
implementacje stosu (operacje z prefiksem s_
)
i kolejki (operacje z prefiksem q_
)
korzystające z listy. Następnie jest parę podstawowych
procedur grafowych (operacje z prefiksem g_
).
Npisać procedury
procedure g_bfs_print(var g : graf; start : integer);
procedure g_dfs_print(var g : graf; start : integer);
które wypiszą numery kolejno odwiedzanych węzłów grafu
g
w porządku BFS i DFS odpowiednio. Parametr
start
wskazuje numwer węzła, od którego
zaczynamy przeszukiwanie grafu.
Napisać kopiec binarny - użyć realizacji w tablicy. Zaimplementować następujące operacje:
make_heap(var h : kopiec)
- tworzy kopiec w tablicy
h
złożony ze znajdujących się w niej elementów.
pop(var h : kopiec) : typ
- zdejmuje z kopca i
zwraca jako wynik element o najmniejszym kluczu.
insert(var h : kopiec; x : typ)
- wkłada do kopca element
x
.
decrease_key(var h : kopiec; i : integer; x : typ)
-
zmniejsza klucz elementu h[i]
do wartości klucza
x
. Zakładamy, że klucz elementu x
jest mniejszy niż klucz elementu h[i]
.
Przy pisaniu pomocna może okazać się książka
Wprowadzenie do algorytmów
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein
dostępna w naszej bibliotece.
Znajdowanie najkrótszej ścieżki pomiędzy parą wierzcholków (BFS) i sortowanie topologiczne (DFS).
Znajdowanie drogi Eulera w grafie. W tym: znajdowanie spójnych składowych grafu niezorientowanego, by sprawdzić czy graf jest spójny.
Znajdowanie silnie spójnych składowych grafu zorientowanego.
Znajdowanie minimalnego drzewa rozpinającego.
Znajdowanie najkrótszej ścieżki w grafie z wagami (algorytm Dijkstry).
Znajdowanie najmniejszej powłoki wypukłej otaczającej zbiór punktów na płaszczyźnie.
Znajdowanie dużych liczb pierwszych i kryptografia RSA.
Warto zapoznać się też z algorytmem Millera-Rabina.
Dokończenie z poprzednich zajęć. Napisać procedury g_bfs_print i
g_dfs_print
.
Ważna uwaga Przy przeszukiwaniu grafu trzeba zapamiętywać, które węzły były już odwiedzone i pilnować, by nie odwiedzać dwa razy tego samego węzła. Algorytm przeszukiwania grafu może działać skrajnie różnie w zależności od tego, w którym momencie oznaczymy węzeł jako odwiedzony.
Zadanie domowe z poprzednich zajęć. Obliczyć średnicę drzewa.
Przy testowaniu można posłużyć się plikiem drzewo.txt. Trzeba będzie też
ustawić N = 26
w kodzie.
Dodać do rekordu opisującego węzeł grafu dodatkowe pole
odl : integer
. Następnie napisać procedurę
procedure g_odleglosci_z(var g : graf; v : integer)
która dla każdego węzła obliczy jego odległość od węzła
v
i zapisze wynik w polu odl
.
Przy testowaniu można posłużyć się plikiem graf.txt. Trzeba będzie też
ustawić N = 26
w kodzie.
Zmodyfikować reprezentację grafu, by każda krawędź miała dodatowy parametr - swoją wagę (długość).
Uwaga: Po tej modyfikacji, napisane dotychczas procedury i funkcje mogą nie działać poprawnie. Co jeszcze trzeba zmodyfikować, by wszystko działało tak jak poprzednio?
Czy napisana wcześniej procedura g_odleglosci_z
nadal poprawnie oblicza odległości wierzchołków?
Zaimplementować kopiec binarny.
Dokończenie z poprzednich zajeć. Obliczyć średnicę drzewa.
Uwaga! Mimo, że nasz graf jest drzewem, to ze
względu na implementację krawędzi niezorientowanych, są w
nim cykle. Każdą krawędź niezorientowaną
{u,v}
reprezentujemy jako parę krawędzi
zorientowanych (u,v)
i (v,u)
,
więc mamy mnóstwo cykli postaci u -> v -> u
.
Trzeba zatem oznaczać wierzchołki jako odwiedzone i
sprawdzać, czy nie wchodzimy do jakiegoś wierzchołka dwa
razy.
Zmodyfikować reprezentację grafu tak, by każda krawędź miała przypisaną pewną wagę (np. odległość w km między miejscowościami).
Uwaga! Należy się dobrze zastanowić jak to zrobić, by się dużo nie narobić. Będzie też trzeba zmodyfikować procedury i funkcje operujące na listach.
Dodać do rekordu opisującego węzeł grafu dodatkowe pole
odl : integer
. Następnie napisać procedurę
procedure g_odleglosci_z(var g : graf; v : integer)
która dla każdego węzła obliczy jego odległość od węzła
v
i zapisze wynik w polu odl
.
Przy testowaniu można posłużyć się plikiem graf.txt. (Uwaga! Trzeba
ustawić N = 26
w kodzie)
Pisać program zaliczeniowy.
Zmodyfikować reprezentację grafu tak, by odpowiadała grafom niezorientowanym.
Odwiedzając jakiś wierzchołek u
i
przeglądając jego listę sąsiadów, napotykamy wierchołek
v
. Chcemy mieć szybki (tj. w czasie O(1))
dostęp do elementu listy sąsiadów wierzchołka
v
wskazującego na u
.
Innymi słowy chcemy połączyć dwie krawędzie zorientowane, reprezentujące jedną niezorientowaną, dodatkowym wskaźnikiem. Dzięki temu będziemy mogli operować na całych krawędziach, a nie tylko na połówkach.
Napisać od nowa procedurę
g_dodaj_krawedz
. Teraz ta procedura
będzie musiała dodać dwie krawędzie i połączyć je ze sobą
dodatkowym wskaźniekiem.
Przepisać procedurę g_odleglosci_z
, by
działała z nową reprezentacją grafu. Wykorzystać kolejkę,
której elementami będą pary liczb lub inne struktury
opisujące krawędzie.
Zmodyfikować reprezentację grafu tak, by każda krawędź miała dodatkowo wagę - pewną liczbę interpretowaną jako długość danej krawędzi.
Rozwiązać zadania z kolokwium.
Majc deklaracje typów
type
napisać funkcję
lista = ^element;
element = record
glowa : integer;
ogon : lista;
end;
listaList = ^element2;
element2 = record
glowa : lista;
ogon : listaList;
end;
function flatten(var l : listaList)
: lista;
, która stworzy listę zawierajcą kolejno
wszystkie elementy listy list. Kolejność elementów na
liście wynikowej musi być zachowana. Po wykonaniu funkcji
lista list powinna być pusta.
Dane jest drzewo binarne o węzłach postaci (liczba,
lewe, prawe)
, które ma wypelnione pole 'liczba'
tylko w liściach, wyłącznie wartościami dodatnimi. Napisać
funkcję wypełniającą pole liczba we wszystkich węzłach
wewnętrznych i zwracającą wartość korzenia (jeśli drzewo
jest puste funkcja ma zwrócić wrtość 0), oblicząjc
odpowiednie wartości w sposób następujcy: jeśli dany węzeł
ma głębokość parzystą (korzeń ma głębokość 0), to
wpisujemy maksimum z wartości lewe^.liczba
i
prawe^.liczba
; jeśli dany węzeł ma głębokość
nieparzystą, to wpisujemy minimum z wartości
lewe^.liczba
i prawe^.liczba
.
Dla danego grafu reprezentowanego przez listy incydencji i jego wierzchołka obliczyć z ilu wierzchołków można do niego dojść w co najwyżej dwóch krokach.
Kilka słów o kolokwium.
Listy dwukierunkowe i listy z wartownikiem.
Sciągnąć plik lista.pas
.
Obejrzeć i skompilować.
Dopisać procedury i funkcje:
dodaj(var l : lista; x : integer)
- dodającą x
przed elementem wskazywanym przez l
,
usun(var l : lista) : integer)
- usuwającą element wskazywany przez l
i zwracającą usuniętą wartość,
znajdz(var l : lista; x : integer) : lista
- zwracającą wskaźnik do węzła zawierającego x
.
Sciągnąć plik hash.pas
.
Obejrzeć i skompilować.
Sciągnąć i obejrzeć pliki dane.txt
oraz
duzedane.txt
.
Znajdują się w nich przykładowe dane do testowania tablicy haszującej.
Każdy rekord składa się z ośmioliterowego, unikalnego identyfikatora oraz
pewnej liczby przyporządkowanej temu identyfiaktorowi. W pliku
dane.txt
jest 100 rekordów, a w pliku duzedane.txt
jest 1000 rekordów
Dopisać ciało funkcji h_hash
obliczającej indeks w tablicy
danego identyfikatora. Najpierw trzeba zamienić identyfikator na liczbę
naturalną k
. Jak to zrobić? Następnie dobrać funkcję, która
zapewni jednostajny rozkład danych w tablicy. Trzeba też dobrać odpowiednio
rozmiar tablicy N
.
Wypróbować funkcję
h(k) = k mod N
dla różnych N
. Funkcja
h_alpha
zwraca maksymalną liczbę
kolidujących elementów. Sprawdzić czy lepiej jest
jeśli N
jest potęgą dwójki czy lepiej
jeśli jest pierwsza.
Wypróbować funkcję
h(k) = trunc(N * frac(k*A))
dla różnych N
i różnych 0 < A
< 1
. Łatwo widać, że parametr
N
ma mały wpływ na efektywność naszej
funkcji. Ważniejszy jest parametr A
-
najlepiej jeśli będzie to liczba
niewymierna. Wypróbować A = (sqrt(5) - 1) /
2
, czyli tzw. złoty podział.
e-mail: initial.lastname @ mimuw.edu.pl | Ostatnia aktualizacja: 29-05-2009 |