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 |