Homepage of Maria Donten

Wstęp do informatyki 2 (potok I) - ćwiczenia, grupa 3, semestr letni 2021/22

Termin: poniedziałki 10:15, sala 3240 lub lab 3044

Najbliższe zajęcia: 13.06 w sali 3240.

Materiały: na stronie dra hab. Zawadowskiego.

Propozycje tematów zadania programistycznego.

Zajęcia 31.05: grafy - przykłady przeszukiwania wszerz i wgłąb, sortowania topologicznego i szukania silnie spójnych składowych. Sprawdzanie zachowania spójności po usunięciu wierzchołka. Szukanie wierzchołka o najkrótszej sumie długości ścieżek do dwóch ustalonych wierzchołków.

Zajęcia 23.05: grafy - plik z tworzeniem i wypisywaniem grafu i przykładowe wejście. Programowanie podstawowych funkcji dla grafów: przejście między listą i macierzą incydencji, transpozycja, obliczanie stopni wierzchołków. Sprawdzanie, czy graf jest drzewem (przykładowy kod i dane wejściowe).

Zajęcia 16.05: grafy - przejścia pomiędzy różnymi reprezentacjami, sprawdzanie, czy graf jest cyklem prostym, przeszuiwania wszerz i w głąb.
Notatki ze zdalnych zajęć.

Zajęcia 9.05: zadanie w ramach kolokwium: treść zadania wraz z potrzebnym kodem i przykładowe dane testowe.

Zajęcia 25.04: powtórzenie przed kolokwium. Kostrukcja drzew czerwono-czarnych o zadanych kluczach węzłów. Usuwanie powtórzeń z listy dwukierunkowej. Znajdowanie wspólnych elementów trzech list uporządkowanych. Lepsze rozwiązanie zadania o wypisywaniu wartości niebdących kluczami danego drzewa BST.

Zajęcia 11.04: Dodawanie elementów do drzewa czerwono-czarnego. Usuwanie liści o parzystych kluczach większych niż dana wartość z drzewa BST.

Zajęcia 4.04: Podstawowe operacje na drzewach BST: kod.
Zadania o drzewach BST: sprawdzanie stabilności drzewa (wierzchołek jest stabilny, jeśli wszystkie drogi od niego do korzenia mają taką samą długość), szukanie najdłuższej luki pomiędzy kluczami.

Zajęcia 28.03: Zadania o drzeach BST: wypisywanie liczb, które nie są kluczami danego drzewa, zliczanie wierzchołków, które mają dokładnie jednego syna, sprawdzanie, czy drzewo jest sbalansowane (poddrzewa w dowolnym wierzchołku o prawie identycznej długości). Wprowadzenie do drzew czerwono-czarnych.

Zajęcia 24.03 (za 7.03):

Usuwanie z listy elementów z ujemnym kluczem i zwracanie sumy tych kluczy.
Scalanie list, które mają wszystkie elementy ujemne przed dodatnimi, do listy o tej samej własności (rozwiązanie).
Podział listy na dwie listy o prawie równych długościach - metodą policzenia elementów i odcięcia części listy (rozwiązanie).
Zadanie domowe: dokończyć sortowanie przez scalanie: podział listy już jest, scalanie uporządkowanych list trzeba zrobić podobnie jak w zadaniu 2, trzeba też napisać rekurencyjną procedurę mergesort, która podzieli listę, rekurencyjnie wywoła się na połowach i scali uporządkowane listy.

Zajęcia 21.03: wprowadzenie do drzew BST - dodawanie i usuwanie elementów, przykłady. Ogólna metoda: procedury wywołujące się rekurencyjnie w poddrzewach. Wypisywanie drzewa w kolejności porządku na kluczach. Zliczanie różnych kluczy w drzewie. Szukanie węzła wewnętrznego, który ma w obu poddrzewach tyle samo węzłów.

Zajęcia 14.03: ponieważ poprzednie zajęcia nie odbyły się w terminie, to zaczęliśmy implementować listy. Było dodawanie i usuwanie elementów, wypisywanie, wczytywanie ze standardowego wejścia i z pliku oraz usuwanie k-tego elementu dla danego k. Następnym razem wykorzystamy napisane funkcje do dokończenia sortowania przez scalanie i innych zadań.

Zadania na zajęcia 7.03 (zajęcia przeniesione na 24.03):

Zaprogramować listy jednokierunkowe lczb całkowitych (jak na poprzednich ćwiczeniach): tworzenie pustej listy, dodawanie i usuwanie elementu.
Zaprogramować wczytywanie liczb (int) do włożenia na listę ze standardowego wejścia i wypisywanie listy na standardowe wyjście.
Napisać procedurę, która dzieli listę na dwie prawie równe listy.
Zaprogramować scalanie dwóch posortowanych list w jedną posortowaną listę (obie dane listy są posortowane niemalejąco lub obie nierosnąco).
Zaimplementować algorytm sortowania przez scalanie na listach.

Rozwiazanie zadania.

Zajęcia 28.02: implementowaliśmy listy jednokierunkowe, za ich pomocą tworzyliśmy stos i kolejkę. Przy okazji powtórzyliśmy, jakie operacje można chcieć wykonywać na listach, jak mogłaby wyglądać implementacja listy na tablicy i do jakich operacji by się nadawała. Ponadto powtórzyliśmy algorytmy sortowania. Zadanie domowe: przemyśleć wczytywanie i wypisywanie list oraz implementację podziału listy na elementy mniejsze i większe od danej liczby (podobne procedury będziemy programować na kolejnych zajęciach).