Homepage of Maria Donten

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

Termin: piątki 10:15, sala 3170 lub lab 3044

Najbliższe zajęcia: 8.06 w sali 3170, kolejne 15.06 również w sali 3170.

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 7.06.2010, str. 46 w pliku ze skryptem (w aktualnej wersji).

Poniższe zadanie na 15.06 to ostatnie obowiązkowe zadanie domowe.

Zadanie domowe na 15.06: napisać program, który sprawdzi, czy dany graf skierowany ma cykl, a jeśli nie, to posortuje ten graf topologicznie (nalezy wysłać mailem kod działającego programu).

Zadanie domowe na 25.05: dla grafu z zadania 4 z kolokwium z WdI z 2011 r. (strona 27 w pliku ze skryptem) podać kolejne kroki poszukiwania minimalnego drzewa rozpinającego algorytmem Prima z początkiem w v5 i algorytmem Kruskala. (W przypadku niejednoznaczności wyboru krawędzi wystarczy podać jedną z możliwości.)

Zadanie domowe na 18.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.

Zadanie domowe na 11.05: 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 27.04 nie było pracy domowej.

Zadanie domowe na 20.04: długi tekst składa się z liter "a",...,"j", przy czym prawdopodobieństwa ich wystąpienia to:
a: 0,37, b: 0,17, c: 0,12, d: 0,1, e: 0,09, f: 0,08, g: 0,03, h: 0,02, i: 0,01, j: 0,01.
Znajdź kod binarny optymalny do zakodowania tego tekstu. Oblicz współczynnik kompresji, czyli iloraz liczby bitów tekstu zakodowanego do liczby bitów reprezentujących tekst oryginalny, jeśli znaki są dane w tablicy elementów typu char.

Zadanie domowe na 13.04: Do początkowo pustego drzewa AVL zostały wstawione kolejno wierzchołki z kluczami 7, 6, 8, 5, 9, 4, 10, 3, 2, 1. Narysuj obrazy drzewa przed wykonaniem każdej rotacji oraz zaznacz wyraźnie lub opisz, w którym wierzchołku i w którą stronę ta rotacja ma być wykonana.

Zadanie domowe na 6.04: napisać program, który wczytuje liczby całkowite z pliku lub standardowego wejścia, tworzy drzewo BST, dla którego te liczby są kluczami wierzchołków, a następnie w nieskończonej pętli pyta użytkownika o liczbę naturalną n i wypisuje liczbę wierzchołków w poddrzewie zaczepionym w wierzchołku o kluczu n (jeśli w drzewie nie ma takiego klucza, to wypisuje 0). Należy oddać działający program - pliki do kompilacji i użytą przez Państwa instrukcję kompilatora, albo Makefile. Proponowane (ale nieobowiązkowe) podejście: uzupełnić strukturę drzewa o pole, w które przed uruchomieniem pętli zostanie wpisana liczba wierzchołków w poddrzewie dla każdego wierzchołka.

Zadanie dodatkowe na 6.04: napisać program, który w nieskończonej pętli pyta o liczbę całkowitą n z zakresu od 0 do 100 i wypisuje klucz k wierzchołka, który najlepiej przybliża podział listy wierzchołków wypisanych według rosnących kluczy taki, że na lewo od k jest n% wierchołków.

Zadanie domowe na 23.03: do deklaracji struktury opisującej wierzchołek drzewa BST dodajemy pole int glebokosc. Napisać procedurę, która dla danego drzewa wpisze w każdym wierzchołku w polu glebokosc długość najdłuższej ścieżki z tego wierzchołka do liścia leżącego pod nim (czyli w poddrzewie o korzeniu w tym wierzchołku).

Zadanie domowe na 16.03: napisz procedurę sortującą listę jednokierunkową intów, wczytywaną z pliku lub standardowego wejścia, algorytmem mergesort (sortowanie przez scalanie) i wypisującą posortowane wartości na standardowe wyjście lub do pliku. (Jeśli zadanie sprawi dużo problemów, to rozważę przedłużenie terminu oddawania prac.)

Zadanie domowe na 9.03: napisz procedurę dzielącą listę L (jednokierunkową) wartości typu int na dwie listy, z których jedna zawiera wszystkie elementy listy L mniejsze od danej liczby całkowitej n, a druga zawiera wszystkie elementy L większe lub równe od n. Parametrami mają być wskaźnik do początku listy L i liczba n. Wskaźniki do nowych list można zapisać na zmiennych globalnych.