Wstęp do informatyki - 1000-112bWI2a

Technikalia

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:

• Ważniak,
• Strona wykładowcy,
• VIPER.

Zadania zaliczeniowe:

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:

1. Wprowadzenie do algorytmów
   T.H. Cormen, C.E. Leiserson, R.L. Rivest,
2. Algorytmy i struktury danych : skrypt dla studentów informatyki
   L. Banachowski, K. Diks, W. Rytter.

Zadania:

1. ZAJĘTE

   Znajdowanie najkrótszej ścieżki pomiędzy parą wierzchołków w grafie zorientowanym (BFS). Sprawdzanie czy graf jest tzw. DAGiem i sortowanie topologiczne.

2. Znajdowanie dwuspójnych składowych grafu niezorientowanego. Wynikiem powinna być struktura dla zbiorów rozłącznych.

3. Znajdowanie silnie spójnych składowych grafu zorientowanego.

4. ZAJĘTE

   Znajdowanie minimalnego drzewa rozpinającego w grafie niezorientowanym (kopiec i algorytm Prima).

5. Znajdowanie minimalnego drzewa rozpinającego w grafie niezorientowanym (struktura dla zbiorów rozłącznych i algorytm Kruskala).

6. ZAJĘTE

   Znajdowanie najkrótszej ścieżki w grafie zorientowanym z wagami (algorytm Dijkstry).

7. ZAJĘTE

   Znajdowanie minimalnej powłoki wypukłej zbioru punktów na płaszczyźnie (algorytm Grahama).

8. 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:

   • wczytywanie z pliku tekstowego dwóch dużych (można się ograniczyć do 100 cyfr dziesiętnych) liczb całkowitych i generowanie z nich kluczy publicznego i prywatnego (należy sprawdzić czy wczytane liczby są pierwsze za pomocą testu Millera-Rabina),
   • wczytywanie z pliku tekstowego klucza publicznego i szyfrowanie nim wiadomości wczytanej z innego pliku tekstowego,
   • wczytywanie z pliku klucza prywatnego i odszyfrowywanie nim zaszyfrowanej wiadomoś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.

9. ZAJĘTE

   Implementacja drzewa AVL. Inicjacja, kasowanie, dodawanie, usuwanie i wyszukiwanie w drzewie.

2) 24 lutego 2010: listy (sala)

1. Sprawdzić czy lista jest uporządkowana niemalejąco.

2. Uporządkować listę niemalejąco.

3. Stworzyć listę dzielników pierwszych danej liczby.

Rozwiązania.

3) 03 marca 2010: listy c.d. (lab)

1. 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.

2. Napisać procedurę, która wypiszę listę liczb całkowitych na ekran monitora. Jedna liczba w jednym wierszu.

Rozwiązania

Do domu: Napisać funkcję odwarającą listę.

4) 10 marca 2010: listy c.d. (lab)

1. Zmodyfikować rozwiązania zadań z poprzednich zajęć tak, by działały z typem danych danym powyżej.

2. 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ę.

3. Do domu: Napisać funkcję, która sprawdzi, czy lista jest posortowana niemalejąco.

4. 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ń.

Rozwiązania (bez domowego)

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ę.

5) 17 marca 2010: jeszcze o listach (sala)

1. Napisać funkcję, która obliczy długość listy (tzn. liczbę elementów).

2. Napisać procedurę, która połączy dwie listy w jedną listę. Tutaj nie zakładamy niczego o porządku elementów na listach.

3. Zaimplementować kolejkę za pomocą dwóch stosów.

4. Napisać procedurę wstawiającą element do listy cyklicznej.

5. 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ę.

Rozwiązania

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.

6) 24 marca 2010: Drzewa binarne. Przechodzenie w głąb i w szerz. (sala)

1. Znaleźć zadany element w nieuporządkowanym drzewie:

   1. metodą "w głąb" rekurencyjnie,
   2. metodą "w głąb" z użyciem stosu,
   3. metodą "w szerz".

2. Policzyć liście drzewa, tzn. węzły nie mające żadnego potomka.

3. Policzyć wszystkie węzły drzewa.

Rozwiązania

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.

7) 31 marca 2010: Drzewa binarne. (sala)

1. Usunąć drzewo binarne z pamięci.

2. Obliczyć wysokość drzewa binarnego.

3. Znaleźć maksymalne pełne poddrzewo w danym drzewie binarnym. Napisać funkcję, która zwraca wskaźnik do korzenia znalezionego poddrzewa.

4. Znaleźć gałąź o maksymalnej długości. Napisać funkcję zwracającą wskaźnik do pierwszego (licząc od korzenia drzewa) elementu gałęzi.

Rozwiązania.

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!

8) 14 kwietnia 2010: Drzewa binarne i BST. (lab)

Proszę ściągnąć plik 14042010lab.pas i rozwiązać poniższe zadania dopisując odpowiednie procedury i funkcje.

1. Sprawdzić czy dane drzewo binarne jest drzewem BST.

2. Znajdowanie elementu w drzewie BST.

3. Dodawanie elementu do drzewa BST. Jak to robić, żeby drzewo nie było za wysokie?

4. Wypisywanie elementów drzewa. W jakiej kolejności wypiszą się elementy?

5. Usuwanie z drzewa BST.

Rozwiązania.

Do domu: Napisać procedurę balansuj, która stworzy nowe, zbalansowane drzewo, zawierające te same elementy co dane drzewo.

9) 21 kwietnia 2010: Grafy - podstawy. (sala)

Omówienie zadań zaliczeniowych.

Ćwiczenia:

1. Wczytać graf z pliku.

2. Sprawdzić czy graf jest cyklem (Hamiltona).

Rozwiązania.

10) 28 kwietnia 2010: Grafy c.d. (sala)

Kilka uwag o cyklach Eulera i Hamilotna.

Różne reprezentacje grafów.

1. Dana jest permutacja wierzchołków grafu (w postaci listy). Sprawdzić, czy ta permutacja wyznacza cykl Hamiltona.

2. Przeszukiwanie grafów: BFS i DFS.

3. Sprawdzić czy graf jest drzewem.

Rozwiązania.

11) 5 maja 2010: Grafy (sala)

1. 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?

2. Sprawdzić czy graf zorientowany jest drzewem.

3. 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 $G=\left(V,E\right)$, obliczyć graf $G^2=\left(V,E^2\right)$. Krawędź $\left(u,v\right)$ należy do $E^2$ wtedy i tylko wtedy gdy istnieje węzeł $w$ taki, że krawędzie $\left(u,w\right)$ oraz $\left(w,v\right)$ należą do $E$.

12) 12 maja 2010: Grafy (sala)

1. Obliczanie kwadratu grafu.

2. Obliczanie k-tej potęgi grafu.

3. Obliczyć graf transponowany.

4. Sprawdzić czy graf jest dwudzielny.

Rozwiązania.

13) 19 maja 2010: Grafy (sala)

1. Drzewo przeszukiwania w głąb. Klasyfikacja krawędzi. Czasy odwiedzenia i przetworzenia.

2. Znaleźć wszystkie punkty artykulacji w grafie niezorientowanym.

Rozwiązania.

14) 26 maja 2010: Zadania z kolokwium i RSA

1. 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.

2. 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).

3. 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.

4. Kryptografia z kluczem niesymetrycznym i algorytm Rivesta, Shamira, Adlemana.

15) 2 czerwca 2010: Oddawanie zadań zaliczeniowych. (lab)

Dane testowe do różnych zadań:

• Lista liczb.
• Inna lista liczb.
• I jeszcze jedna lista liczb.
• Graf.
• Graf z danymi w wierzchołkach.
• Graf do testowania punktów artykulacji.
• Graf, który jest drzewem.
• Graf dwudzielny.