Homepage of Maria Donten

Wstęp do informatyki 2 (potok II) - ćwiczenia, grupa 3, semestr letni 2017/18

Termin: poniedziałki 10:15, sala 3250 lub lab 3041

Wykłady, zadania, stare kolokwia: w skrypcie dra hab. Kiciaka.

Ostateczny termin oddawania projektów programistycznych to 16 czerwca. Programy oddane po tym terminie, poza uzasadnionymi przypadkami, nie będą wliczane do oceny w pierwszym terminie.

Zasady zdobywania 40% punktów za ćwiczenia:
prawie co tydzień będzie praca domowa do oddania na początku ćwiczeń. Za każdym razem będą 1-2 zadania, oceniane na 0, 1/4, 1/2, 3/4 lub 1 punkt (końcowy wynik zostanie odpowiednio przeskalowany). To jest jedyna możliwość zdobycia punktów za ćwiczenia.
Rozwiązania można oddawać do 15 minut po rozpoczęciu zajęć, na kartce lub mailem.
Poza tym za kolokwium można zdobyć do 30% punktów i za projekt programistyczny także do 30% punktów za pracę w trakcie semestru. Suma tych wartości oraz liczby punktów za egzamin przekłada się wprost na ocenę końcową. (Dodatkowo, żeby uzyskać pozytywną ocenę, trzeba zdobyć przynajmniej połowę punktów z egzaminu. Zdobycie poniżej 1/3 punktów z egzaminu pisemnego wyklucza przystąpienie do egzaminu ustnego.)

Zadania uzupełniające do oddania nie później niż 16.06 (dla chętnych, którzy chcą poprawić uzyskaną dotąd liczbę punktów z prac domowych): zadania 3 i 4 z egzaminu z 6.09.2011, str. 47 w pliku ze skryptem (w aktualnej wersji skryptu - w starej ten egzamin miał datę 6.06.2011).

Zadanie domowe na 4.06: napisać program, który znajdzie silnie spójne składowe w danym grafie skierowanym (należy wysłać mailem kod działającego programu).

Zadanie domowe na 21.05: zadanie 2 z egzaminu z 8.06.2009 (str. 32 w skrypcie). Odpowiedzi proszę dokładnie uzasadnić.

Zadania domowe na 14.05:

druga część implementacji wyszukiwania najkrótszych ścieżek w grafie nieskierowanym (bez wag) za pomocą przeszukiwania wszerz (BFS). Należy przesłać kod działającego programu, który wczyta graf i parę wierzchołków, a następnie wypisze długość najkrótszej ścieżki pomiędzy tymi wierzchołkami, obliczoną za pomocą przeszukiwania wszerz.
dla grafu z zadania 4 z kolokwium z WdI z 2010 r. (strona 26 w pliku ze skryptem) podać kolejne kroki poszukiwania minimalnego drzewa rozpinającego algorytmem Prima z początkiem w v4 i algorytmem Kruskala. (W przypadku niejednoznaczności wyboru krawędzi wystarczy podać jedną z możliwości.)

Zadanie domowe na 30.04: pierwsza część implementacji wyszukiwania najkrótszych ścieżek w grafie nieskierowanym (bez wag) za pomocą przeszukiwania wszerz (BFS). Należy przesłać kod, który wczyta graf (z pliku lub standardowego wejścia - trzeba napisać jedną z opcji) i zbuduje struktury, które ten graf reprezentują. Graf jest dany jako: int n - liczba wierzchołków, int m - liczba krawędzi oraz m par intów z zakresu od 1 do n reprezentujących krawędzie (wierzchołki są numerowane liczbami od 1 do n). W programie można reprezentować graf za pomocą list sąsiedztwa lub macierzy sąsiedztwa. (Na następnych zajęciach będziemy kontynuować to zadanie. Celem jest możliwość wyszukania najkrótszej ścieżki między dwoma wierzchłkami podanymi przez użytkownika.)

Na 23.04 nie było pracy domowej.

Zadanie domowe na 16.04: Pewien tekst składa się z liter "a",...,"j", przy czym litery "a" i "b" występują po jednym razie, a liczba wystąpień każdej natępnej litery alfabetu jest sumą liczb wystąpień dwóch poprzednich liter. Znajdź kod binarny optymalny dla zakodowania tego tekstu. Nieobowiązkowe pytanie dodatkowe: jak będzie wyglądał optymalny kod binarny dla alfabetu złożonego z n liter i tekstu, w którym wystąpienia kolejnych liter spełniają tę samą regułę?

Na 9.04 nie było pracy domowej.

Zadanie domowe na 26.03: napisać procedurę, która dla danego klucza wyszukuje w drzewie BST element o tym kluczu i wypisuje na standardowe wyjście dwie liczby: informację, który z kolei jest dany wierzchołek na swoim poziomie w drzewie i informację, który z kolei byłby, gdyby drzewo zostało uzupełnione do pełnego drzewa binarnego. Należy oddać działający program (pliki do kompilacji i użytą przez Państwa instrukcję kompilatora, albo Makefile), który wczytuje klucze wierzchołków drzewa ze standardowego wejścia lub z pliku, tworzy to drzewo, a potem w nieskończonej pętli pyta o klucz wierzchołka, dla którego ma wypisać informacje.

Zadanie dodatkowe na 26.03: zaimplementować "ładne" wypisywanie drzewa - w kolejnych wierszach ma być lista kluczy z kolejnych poziomów, a w miejscach, gdzie przy uzupełnianiu do pełnego drzewa binarnego pojawiłby się wierzchołek spoza struktury danego drzewa, należy wpisać "--".

Zadanie domowe na 19.03: do struktury opisującej wierzchołek drzewa BST dodajemy pole int poziom. Napisać procedurę, która dla danego drzewa wpisze w kadym wierzchołku w polu poziom odległość tego wierzchołka od korzenia (tzn. korzeń ma poziom 0, jego synowie poziom 1 itd.)

Zadanie domowe na 12.03: napisz procedurę sortującą listę jednokierunkową intów, wczytywaną z pliku lub standardowego wejścia, algorytmem quicksort i wypisującą posortowane wartości na standardowe wyjście lub do pliku. (Można oddać rozwiązanie do poniedziałku 19.03.)

Zadanie domowe na 5.03: napisz procedurę scalającą dwie posortowane listy (jednokierunkowe) wartości typu int w jedną posortowaną listę. Parametrami mają być wskaźniki do początków list, wynikiem ma być wskaźnik do nowej listy.