Wstęp do informatyki II

Semestr letni
Materiały archiwalne

Część zajęć będzie się odbywać w laboratorium komputerowym, pozostałe będą prowadzone w trybie "tablicowym".

W laboratorium będziemy pracowali w systemie Linux. Programy będziemy pisać w języku C. Ze względu na prawie stuprocentową przenośność kodu w języku C, można będzie testować tworzone w LABie programy w innych środowiskach programistycznych, takich, jak popularne w systemie Windows środowiska Microsoft Visual Studio lub Clang.

Aktualności

Najbliższe zajęcia: kartkówka.

Pisząc programy, zachowujcie Państwo ich czytelną strukturę i dodawajcie wyraziste komentarze - co prawda kompilatorowi jest obojętne, jak zapisujecie program (byleby tylko syntax był poprawny) - ale za to Wam będzie znacznie wygodniej je czytać, sprawdzać, analizować...

Treści omawiane na zajęciach

13.05.09., SALA

Znajdowanie silnych składowych w grafie. Wstęp do problemu najkrótszych ścieżek.

  1. Czym jest GT, gdy G jest macierzą sąsiedztwa
  2. Przypomnienie algorytmu DFS
  3. Algorytm znajdowania DFS
  4. Realizacja algorytmu na przykładowych grafach. Graf zredukowany.
  5. Acykliczność grafu zredukowanego
  6. Do zastanowienia w domu: jak uspójnić graf dodając doń możliwie mało krawędzi?
06.05.09., LAB

Inne zadania związanie z grafami rzadkimi - przykład: wyznaczanie rankingu stron internetowych algorytmem PageRank, kiedyś stosowanym w Google.

  1. Jeszcze jeden sposób reprezentacji grafu rzadkiego: macierz rzadka w formacie współrzędnych
  2. Wczytywanie grafu rzadkiego z pliku
  3. Mnożenie macierzy rzadkiej przez wektor (na razie w wersji bardzo wolnej)
  4. Jak pokonywać problem webringów oraz istnienia liści w grafie: wersja z grafem pełnym, dodajemy ścieżki o (zwykle bardzo małej, ale niezerowej wadze) (chociaż w implementacji PageRank wciąż rzadkim! - dzięki znakomitej własności mnożenia wektora przez macierz jedynkową)
  5. Pierwszy testowy graf (oryginalny graf linków dla naszego wydziałowego portalu): macierz lab.txt. Ta macierz nie jest stochastyczna, bo w grafie są liście, tzn. strony z których nie ma żadnych linków.

Praca domowa

Na za tydzień. Rozwiązaniem obu zadań jest 5 par liczb z opisem.

  1. Opracuj funkcję mnożenia SparseMult() znacznie szybciej działającą od SparseMultSlow() z programu opracowanego w labie.
  2. Uruchom nasz algorytm PageRank na grafie (bez liści i bez webringów) danym w pliku test.txt (pierwszy wiersz zawiera liczbę węzłów i liczbę krawędzi w grafie) Podaj indeksy i rangę 5 stron o najwyższym rankingu. Uwaga: tego zadania nie da się zrobić bez zadania poprzedniego ;-)
29,04.09., SALA

Algorytm DFS. Parę uwag o kolokwium.

  1. Struktury danych dla DFS (zob. także praca domowa poniżej).
  2. Przykładowe DFS na przykładowym grafie
  3. Klasyfikacja krawędzi.
  4. Częściowa charakteryzacja krawędzi przez czasy dojścia i czasy przetworzenia. Częściowa charakteryzacja przez kolory wierzchołków.
  5. Wyznaczanie typu krawędzi w trakcie DFS przez sprawdzenie czasów dojścia i kolorów.

Praca domowa

  1. Implementacja DFS w C (na za 2 tygodnie). Na zajęciach, aby reprezentować otrzymywany las, skorzystaliśmy z listy drzew, gdzie każde drzewo reprezentowaliśmy przez listę sąsiedztwa!(!!) To znaczące marnotrawstwo i niepotrzebna komplikacja! Postaraj się obmyślić (możesz też po prostu sprawdzić w wykładzie lub szukać inspiracji w algorytmie BFS z ćwiczeń), czy możliwe jest znacznie tańsze rozwiązanie tego problemu, wykorzystujące po prostu jedną tablicę rozmiaru |V|. To nie tylko uprości struktury danych, ale także samą implementację algorytmu DFS!
  2. Kilka drobnych zadań podanych na zajęciach, m.in. rodzaje krawędzi w grafie nieskierowanym oraz przeprowadzenie DFS z wierzchołka "F" grafu z ćwiczeń. Te zadania na za tydzień.
22,04.09., SALA

MST.

  1. Wyznaczanie MST algorytmem Kruskala vs. wyznaczanie algorytmem Prima (przykład)
  2. (Nie)jednoznaczność MST.
  3. (Któraś) najlżejsza krawędź musi należeć do MST.
  4. Wstępne rozważania o pierwszym zadaniu z pracy domowej.

Praca domowa

  1. Maksymalna liczba drzew w nieskierowanym grafie pełnym.
  2. Jednoznaczność MST, gdy wszystkie krawędzie mają różne wagi.
08.04.09, SALA

Grafy, ich implementacja i przeszukiwanie.

  1. Grafy skierowane i nieskierowane. Reprezentacja listowa i macierzowa.
  2. Implementacja obu reprezentacji grafu.
  3. Podstawowe własności grafów. Obliczanie stopnia zadanego wierzchołka itp.
  4. Algorytm BFS i jego implementacja z użyciem kolejki.

Praca domowa

Coś ostrzejszego do wielkanocnego jajeczka. Na najbliższe zajęcia.

  1. Podaj algorytm sprawdzenia, czy dany graf nieskierowany jest spójny. Uzasadnij.
  2. Podaj algorytm, który w czasie O(|V|) sprawdzi, czy dany graf skierowany, reprezentowany przez macierz sąsiedztwa, ma choć jeden wierzchołek o stopniu wejściowym |V|-1 i wyjściowym równym zero. Taki wierzchołek nazywa się czasem ujściem uniwersalnym lub VIPem (znają go wszyscy, a on tylko siebie; hmm....).. Uzasadnij poprawność tego algorytmu.
  3. Macierz incydencji grafu skierowanego to macierz B wymiaru |V| x |E| taka, że
    • Bij = -1, gdy krawędź j wychodzi z wierzchołka i,
    • Bij = +1, gdy krawędź j wchodzi do wierzchołka i,
    • Bij = 0, w przeciwnym przypadku.

    Podaj interpretację macierzy B*BT.

01.04.09., SALA

Kodowanie Huffmana (zobacz także zabawną animację). Kilka funkcji C przydatnych przy implementacji programu zaliczeniowego.

  1. Konstrukcja drzewa Huffmana i średnia długość kodu Huffmana.
  2. Kodowanie kodem Huffmana.
  3. Dekodowanie kodu Huffmana.
  4. Kodowanie Huffmana parami.
25.03.09., SALA/LAB

Mikrokolokwium (20 min.; tematyka: listy, drzewa binarne i BST). Drzewa AVL. "Sadzenie" drzew (BST i AVL) to może być także fajna zabawa!

  1. Wstawianie do drzewa AVL. Wszelkie możliwe rotacje i jak je robić.
  2. Usuwanie wierzchołka z drzewa AVL.

Praca domowa

Dwa zadania, dokładnie sformułowane na ćwiczeniach. Oddajemy na kartkach, najpóźniej na następnych zajęciach.

  1. Wstawianie kolejnych wierzchołków o rosnących kluczach do drzewa AVL.
  2. Drzewo przed każdą rotacją (z opisem).
18.03.09., SALA/LAB

Nieudane próby napisania procedur obsługujących drzewo BST:

  1. Tworzenie drzewa BST z losowymi kluczami będąymi znakami 'a'...'z' typu unsigned char.
  2. Sprawdzenie, czy utworzone drzewo jest faktycznie drzewem BST.
  3. Wypisanie drzewa w zadanym porządku.
  4. Usunięcie całego drzewa z pamięci.

Zobacz przykładowe rozwiązania na blogu z programami!

Praca domowa

Dokończyć zadania z zajęć (przykładowe rozwiązania na blogu z programami; zajrzyj w razie trudności z samodzielnym opracowywaniem programów, ale nie przepisuj!) Przygotować się do mikrokolokwium na następne zajęcia. Tematyka: listy, drzewa binarne i BST.

11.03.09., SALA

Drzewa (binarne) i drzewa BST (tzn. takie, których wierzchołki mają następującą własność: wszystkie wierzchołki lewego (odpowiednio: prawego) poddrzewa mają klucze nie większe (odpowiednio: nie mniejsze) od klucza danego wierzchołka.

  1. Implementacja drzewa w C
  2. Konstrukcja drzew BST
  3. Wyszukiwanie w drzewie BST (z rekurencją i bez rekurencji).
  4. Wypisywanie zawartości drzewa (w porządkach: pre-order, in-order oraz post-order)
  5. Sortowanie zawartości drzewa BST
  6. Liczenie wierzchołków drzewa

Praca domowa

Programy i procedury, o których mowa - ich kody źródłowe w języku C, a nie pliki wykonywalne - należy przesłać na mój adres email, piotr.krzyzanowski@mimuw.edu.pl, do 25. marca (środa), do godz. 9:00 (decyduje chwila dotarcia wiadomości do mojej skrzynki pocztowej). Każdy z "elementarnych" podpunktów jest wart maksymalnie 3 punkty. Zdanie na kartce oddajemy na zajęciach 25. marca (lub wcześniejszych).

  1. (niepunktowane) Proszę popraw pierwsze zadanie tak, by wszystkie wskazane drzewa miały własność BST.
  2. Napisz (na kartce) procedurę w C wyznaczającą wysokość drzewa. Pamiętaj, by zdefiniować stosowny typ "drzewiasty".
  3. Zaimplementuj w C procedurę tworzenia drzwa BST o kluczach będących kolejnymi liczbami w zadanej N-elementowej tablicy liczb rzeczywistych.
  4. Zaimplementuj także (jedną) procedurę wypisywania zawartości otrzymanego drzewa w jednym z możliwych do wyboru porządków: pre-order, in-order oraz post-order.
  5. Testuj obie procedury w jakimś sensownym programie. Nie zapomnij o Makefile, jeśli jest potrzebny.
04.03.09., SALA

Listy.

  1. Wstawianie do listy, wyszukiwanie w liście, usuwanie z listy elementu spełniającego warunek
  2. Implementacja listy w C.

Praca domowa

Programy i procedury, o których mowa - ich kody źródłowe w języku C, a nie pliki wykonywalne - należy przesłać na mój adres email, piotr.krzyzanowski@mimuw.edu.pl, do 13. marca (piątek!), do godz. 9:00 (decyduje chwila dotarcia wiadomości do mojej skrzynki pocztowej). Każdy z "elementarnych" podpunktów jest wart maksymalnie 3 punkty.

  1. Zaimplementuj następujące procedury dla listy jednokierunkowej o kluczach będących liczbami całkowitymi :
    1. Tworzenie listy składającej się z N kolejnych liczb: 1 (w głowie), 2, 3, ..., N (w ogonie)
    2. Drukowanie jej pełnej zawartości od głowy do ogona
    3. Usuwanie z listy pierwszego elementu, którego klucz jest równy zadanej liczbie całkowitej v.
    4. Dodatkowe (nieobowiązkowe, ale można dostać dodatkowe punkty): Odwracanie kolejności elementów na liście.
  2. Wykorzystaj te procedury w programie, w którym: utworzysz listę zadanego rozmiaru N, wypiszesz ją, następnie usuniesz element o kluczu 0, wypiszesz, usuniesz element o kluczu 1, wypiszesz i na końcu usuniesz element o kluczu N i wypiszesz pozostałą listę.
  3. Dodatkowe (wariant trudniejszy, punktowany dodatkowe 3 punkty): procedury obsługi listy umieść w pliku lista.c (pamiętaj o zrobieniu pliku nagłówkowego lista.h), a program testujący - w pliku testlista.c; oczywiście, powinieneś utworzyć do kompletu elegancki Makefile...
25.02.09., LAB

Dynamiczna alokacja pamięci. Dalszy rozwój biblioteczki macierzowej z poprzednich zajęć. Kilka ciekawostek z arytmetyki zmiennoprzecinkowej, jeśli czas pozwoli.

  1. Alokacja macierzy 2-wymiarowej i jej obsługa, zobacz pliki z LABu
  2. Wyznaczanie epsilona maszynowego
18.02.09., LAB

Projekty złożone z wielu plików.

  1. Zaczynamy tworzyć "biblioteczkę" funkcji macierzowych, zob. pliki c1-mx1.c i c1-mx1.h dla biblioteczki wektorowej (tablice 1-wymiarowe). Na zajęciach nie udało nam się (z powodu mojego błędu) wygenerować analogicznej biblioteczki dla tablic dwuwymiarowych, będziemy to robili na następnych zajęciach.
  2. Budowanie projektu etapami (kompilacja i linkowanie).
  3. Polecenie make i konstrukcja pliku Makefile.

Praca domowa

W tym tygodniu praca domowa nie jest obowiązkowa!

  1. Do zestawu procedur z c1-mx1.c dodaj procedurę generującą wektor zawierający losowe liczby rzeczywiste z przedziału [0,1] oraz funkcję obliczającą normę Euklidesową wektora.
  2. Obie funkcje wykorzystaj w pliku c1-testmx.c.

Zasady zaliczenia

Podstawy zostały sformułowane na pierwszym wykładzie. Na ocenę z ćwiczeń składają się:

Kartkówki będą mini-zadaniami na tematy różne. Może to być jakieś zadanie do rozwiązania na kartce, sprawdzenie znajomości zagadnień z wykładu, czy też zaprogramowanie czegoś małego przy komputerze.

Prace domowe będą zadawane z tygodnia na tydzień. Po terminie prace nie będą sprawdzane.

Za każde zadanie z pracy domowej można otrzymać maksymalnie 3 punkty. Za każde zadanie z kartkówki można dostać maksymalnie 1 punkt. Program zaliczeniowy będzie oceniany w skali 10-punktowej. Suma uzyskanych punktów z prac domowych i kartkówek zostanie na koniec semestru znormalizowana tak, by 100% punktów było równe maksimum punktów do uzyskania z kolokwium; tak samo zostanie znormalizowana ocena z programu zaliczeniowego.

Ostateczna liczba punktów uzyskanych z ćwiczeń będzie wyliczona według wzoru P = 0.3*D + 0.3*Z + 0.4*K, gdzie D - znormalizowana suma punktów z prac domowych i kartkówek, Z - znormalizowana suma punktów z programu zaliczeniowego, K - znormalizowana suma punktów z kolokwium.

Ciekawe linki

Wykładowca, P. Kiciak, udostępnia na swojej stronie WWW notatki do wykładu. Warto na bieżąco je śledzić!

Piotr Krzyżanowski | Aktualizacja: 02.03.2019, 23:12:49.