Termin: środa, 10:15-11:45, s. 2041 lub 3120
Prowadzący: Sławomir Kolasiński
Konsultacje: p. 4500 MIM UW, wtorki 13-14 oraz środy 12-13
Przydatne linki:
Program zliczeniowy należy napisać w języku Pascal. Powinien się on kompilować w laboratorium komputerowym. Można pisać zarówno pod Linuxem jak i pod Windowsem. Można też korzystać zarówno z FreePascala jak i z Borland Pascala. Na początku pliku z kodem należy podać w komentarzu: swoje imię, nazwisko, numer indeksu oraz system (Linux/Winda) i kompilator (Borland/Free Pascal), z których się korzystało podczas pisania.
Napisany program w postaci pliku źródłowego pas
należy
wysłać mejlem prowadzącemu ćwiczenia najpóźniej 31 maja 2010
roku o godzinie 23:59. Za program
zaliczeniowy można dostać 10 punktów. Programy wysłane po terminie
będą oceniane maksymalnie na 5 punktów. Programy, które się nie
kompilują w ogóle nie będą sprawdzane.
Każdy student wybiera jeden temat spośród podanych poniżej i samodzielnie pisze rozwiązanie. Jeden temat może zostać przypisany najwyżej dwóm osobom - kto pierwszy ten lepszy. Rezerwacje można składać mejlowo lub osobiście po każdych zajęciach.
Przy pisaniu programów zaliczeniowych należy pamiętać, że prowadzący będzie czytał kod źródłowy i będzie starał się go zrozumieć. Należy zatem pisać przejrzyście. Poza tym każdy program powinien zawierać procedury wczytujące dane i wypisujące wyniki oraz kilka zestawów przykładowych danych testowych - najlepiej w osobnych plikach tekstowych. Wysyłając rozwiązania należy załączyć też pliki z danymi testowymi.
Przy pisaniu pomocne mogą okazać się książki:
Znajdowanie najkrótszej ścieżki pomiędzy parą wierzchołków w grafie zorientowanym (BFS). Sprawdzanie czy graf jest tzw. DAGiem i sortowanie topologiczne.
Znajdowanie dwuspójnych składowych grafu niezorientowanego. Wynikiem powinna być struktura dla zbiorów rozłącznych.
Znajdowanie silnie spójnych składowych grafu zorientowanego.
Znajdowanie minimalnego drzewa rozpinającego w grafie niezorientowanym (kopiec i algorytm Prima).
Znajdowanie minimalnego drzewa rozpinającego w grafie niezorientowanym (struktura dla zbiorów rozłącznych i algorytm Kruskala).
Znajdowanie najkrótszej ścieżki w grafie zorientowanym z wagami (algorytm Dijkstry).
Znajdowanie minimalnej powłoki wypukłej zbioru punktów na płaszczyźnie (algorytm Grahama).
Kryptografia RSA. Tutaj trzeba zaimplementować arytmetykę modularną na dużych liczbach realizowanych za pomocą list i/lub tablic. Program powinien implementować następujące funkcjonalności:
Sposób dzielenia wiadomości na kawałki do szyfrowania można wybrać dowolnie. Zaszyfrowana wiadomość będzie miała postać ciągu dużych liczb całkowitych, które najlepiej zapisać do pliku w postaci tekstowej.
Implementacja drzewa AVL. Inicjacja, kasowanie, dodawanie, usuwanie i wyszukiwanie w drzewie.
type
lista = ^element;
element = record
glowa : integer;
ogon : lista;
end;
Sprawdzić czy lista jest uporządkowana niemalejąco.
Uporządkować listę niemalejąco.
Stworzyć listę dzielników pierwszych danej liczby.
type
lista = ^element;
element = record
dane : integer;
ogon : lista;
end;
Napisać procedurę wczytującą listę liczb całkowitych z
pliku. Zakładamy, że w pliku są zapisane liczby w postaci tekstu
i jest po jednej liczbie w każdym wierszu. Liczby są z
przedziału od -30000 do 30000, więc mieszczą się w standardowym
typie integer
.
Napisać procedurę, która wypiszę listę liczb całkowitych na ekran monitora. Jedna liczba w jednym wierszu.
Do domu: Napisać funkcję odwarającą listę.
type
TLista = ^TElem;
TElem = record
wartosc : integer;
nast : TLista;
end;
Zmodyfikować rozwiązania zadań z poprzednich zajęć tak, by działały z typem danych danym powyżej.
Napisać procedurę, która scali dwie posortowane niemalejąco listy w jedną listę posortowaną niemalejąco. Wynik należy zwrócić w argumencie przekazywanym przez nazwę.
Do domu: Napisać funkcję, która sprawdzi, czy lista jest posortowana niemalejąco.
Napisać procedurę, która wczyta z pliku dwie listy, sprawdzi, czy są posortowane, a następnie scali je w jedną posortowaną listę i wypisze wynik na ekranie. Wykorzystać rozwiązania poprzednich zadań.
Do domu: Dokończyć powyższe zadania. Napisać, skompilować i uruchomić na komputerze. Proszę uważać na kolejność elementów listy. Chcemy by wynikowa lista była posortowana niemalejąco. Można w tym celu dopisać procedurę/funkcję odwracającą listę.
type
TLista = ^TElem;
TElem = record
glowa : integer;
ogon : TLista;
end;
Napisać funkcję, która obliczy długość listy (tzn. liczbę elementów).
Napisać procedurę, która połączy dwie listy w jedną listę. Tutaj nie zakładamy niczego o porządku elementów na listach.
Zaimplementować kolejkę za pomocą dwóch stosów.
Napisać procedurę wstawiającą element do listy cyklicznej.
Napisać funkcję wyszukującą na liście cyklicznej podaną
liczbę. Zwracana wartość ma być typu TLista
i
ma to być ten element listy, który zawiera szukaną liczbę.
Do domu: Napisać procedure flawiusz(var l :
TLista; n : integer)
, która będzie usuwać z listy cyklicznej
l
co n
-ty element, tak długo, aż zostanie
tylko jeden element.
type
TDrzewo = ^TWezel;
TWezel = record
dane : integer;
lewy : TDrzewo;
prawy : TDrzewo;
end;
Znaleźć zadany element w nieuporządkowanym drzewie:
Policzyć liście drzewa, tzn. węzły nie mające żadnego potomka.
Policzyć wszystkie węzły drzewa.
Do domu: Obliczyć wysokość drzewa, czyli długość najdłuższej gałęzi zaczynającej się w korzeniu, a kończącej w liściu.
Usunąć drzewo binarne z pamięci.
Obliczyć wysokość drzewa binarnego.
Znaleźć maksymalne pełne poddrzewo w danym drzewie binarnym. Napisać funkcję, która zwraca wskaźnik do korzenia znalezionego poddrzewa.
Znaleźć gałąź o maksymalnej długości. Napisać funkcję zwracającą wskaźnik do pierwszego (licząc od korzenia drzewa) elementu gałęzi.
Do domu: Sprawdzić czy drzewo jest zbalansowane. Drzewo nazywa się zbalansowane jeśli w każdym węźle wysokość lewego i prawego poddrzewa różni się o co najwyżej jeden.
Spokojnego, radosnego i pełnego nadziei czasu świątecznego!
Proszę ściągnąć plik 14042010lab.pas i rozwiązać poniższe zadania dopisując odpowiednie procedury i funkcje.
Sprawdzić czy dane drzewo binarne jest drzewem BST.
Znajdowanie elementu w drzewie BST.
Dodawanie elementu do drzewa BST. Jak to robić, żeby drzewo nie było za wysokie?
Wypisywanie elementów drzewa. W jakiej kolejności wypiszą się elementy?
Usuwanie z drzewa BST.
Do domu: Napisać procedurę balansuj
,
która stworzy nowe, zbalansowane drzewo, zawierające te same
elementy co dane drzewo.
Omówienie zadań zaliczeniowych.
Wczytać graf z pliku.
Sprawdzić czy graf jest cyklem (Hamiltona).
Kilka uwag o cyklach Eulera i Hamilotna.
Różne reprezentacje grafów.
Dana jest permutacja wierzchołków grafu (w postaci listy). Sprawdzić, czy ta permutacja wyznacza cykl Hamiltona.
Przeszukiwanie grafów: BFS i DFS.
Sprawdzić czy graf jest drzewem.
Jaka jest złożoność algorytmu sprawdzającego czy dana permutacja wierzchołków wyznacza cykl Hamiltona? Jak złożoność zależy od użytej reprezentacji grafu w komputerze?
Sprawdzić czy graf zorientowany jest drzewem.
Co zmienia się dla grafów niezorientowanych? Jak rozwiązać powyższe zadania przy różnych realizacjach grafów w pamięci komputera?
Do domu: Mając dany graf , obliczyć graf . Krawędź należy do wtedy i tylko wtedy gdy istnieje węzeł taki, że krawędzie oraz należą do .
Obliczanie kwadratu grafu.
Obliczanie k-tej potęgi grafu.
Obliczyć graf transponowany.
Sprawdzić czy graf jest dwudzielny.
Drzewo przeszukiwania w głąb. Klasyfikacja krawędzi. Czasy odwiedzenia i przetworzenia.
Znaleźć wszystkie punkty artykulacji w grafie niezorientowanym.
Dane są dwie listy liczb naturalnych o tej samej długości, posortowane ściśle rosnąco. Napisać procedurę, która urozłączni te listy w taki sposób, żeby po całej operacji listy różniły się długością o co najwyżej 1.
Napisać funkcję, która dla danego drzewa binarnego zwróci liczbę węzłów, które mają parzystą liczbę potomków (wszystkich, a nie tylko synów).
Napisać funkcję, która sprawdzi, czy dla danych dwóch
wierzchołków u
i v
grafu
G
istnieje trzeci wierzchołek w
,
do którego można dojść z obydwu wierzchołków u
i v
.
Kryptografia z kluczem niesymetrycznym i algorytm Rivesta, Shamira, Adlemana.
Dane testowe do różnych zadań:
e-mail: initial.lastname @ mimuw.edu.pl | Ostatnia aktualizacja: 26.05.2010 |