Radosław Ziemann
mail: rziemann@inf.ug.edu.pl
konsultacje: piątek 12.00-13.00,z powodu epidemii konsultacje odbywają się drogą mailową, jesli to nie wystarczy mozna umówić się na MSTeams
INFORMACJE ORGANIZACYJNE:
Grupa 4: poniedziałek 12.15-13.45
Grupa 3: wtorek 10.15-11.45
Dopuszczalne są 2 nieusprawiedliwione nieobecności. Nieobecności trzeba usprawiedliwiać na pierwszych zajęciach po zwolnieniu.
OCENA KOŃCOWA O składa się z 2 składowych: punktów za programy P oraz punktów za sprawdziany S, gdzie P=~70%O i S=~30%O.
PROGRAMY:
Programy piszemy samodzielnie, będą sprawdzane programem antyplagiatowym.
Programy są oceniane w 2 etapach. Najpierw należy w odpowiednim terminie przesłać kod żródłowy na portal edukacyjny (w pierwszym tygodniu na maila), a następnie zgłosić się na zajęciach
do jego osobistego omówienia.
Programy można pisać w dowolnym języku programowania, przy czym preferowane języki to:
python, C/C++, Java.
W przypadku wyboru innych języków należy powiadomić o tym mailowo prowadzącego zajęcia w pierwszym tygodniu zajęć.
Programy oddane w terminie mogą otrzymać maksimum punktów, tydzień po terminie o połowę mniej.
SPRAWDZIANY:
Sprawdziany będą zapowiedziane tydzień wcześniej.
Nie można ich poprawiać.
Po okazaniu usprawiedliwienia można umówić się na NAJBLIŻSZE konsultacje w celu napisania zaległego sprawdzianu.
ZADANIA:
1. (22/23.02.2021) Eksperymentalne badanie złożoności czasowej algorytmów,
Termin: 01/02.03.2021
Wstęp
W pliku
czas.py znajdują się definicje pięciu funkcji: f1, f2, ... , f5 oraz pomiar sprawdzający, czy rzeczywisty czas działania funkcji f1(n) (wyliczony w zmiennej Tn) dla różnych wartości n (równych 2000, 4000, 8000, 16000, 32000) zmienia się zgodnie z przebiegiem funkcji liniowej (Fn = n)
Wykonać podobne pomiary dla pozostałych funkcji, dobierając odpowiednie funkcje Fn. Funkcja Fn "dobrze" opisuje prawdziwy czas Tn danej funkcji, jeżeli ilorazy Fn/Tn są mniej więcej takie same dla wszystkich wartości n.
Jako rozwiązanie przesłać kod programu wykonującego pomiary z dołączonymi wynikami wygenerowanymi przez ten program dla wszystkich pięciu funkcji. Wyniki te można dołączyć np. jako komentarz na końcu kodu programu.
Dodatkowo proszę przesłać wykresy uwzględniające powyższe dane (zmienna x = rozmiar wejścia. y = czas wykonanaia), odpowiednio dla każdej funkcji. Można je wykonać np. za pomocą programu
gnuplot
2. (1/2.03.2021) Sortowanie przez kopcowanie,
Termin: 08/09.03.2021
Za tydzień (08/09.03) sprawdzian z heapsort.
Sortowanie przez kopcowanie (Heap-sort)
Zadanie z2.1
Sprawdź, czy ciąg (23, 17, 14, 6, 13, 10, 1, 5, 7, 12)
ma własność kopca typu max?
Zadanie z2.2
Zademonstruj kolejne kroki działania procedury budującej kopiec z elementów
ciągu A = [28, 6, 11, 12, 17, 8, 7, 18, 12, 14, 23]. Następnie zilustruj
kilka obrotów pętli sortującej przy sortowaniu kopcowym Heapsort.
Użyj drzewiastej reprezentacji kopca. Zaznaczaj, które elementy kopca
są ze sobą zamieniane.
Zadanie z2.3
Oszacuj czasy działania algorytmu sortowania przez kopcowanie dla
ciągu
A,
o długości
n,
w którym (a) wszystkie elementy są takie same,
(b) są posortowane malejąco, (c) są posortowane rosnąco.
Zadanie z2.4 (5 pkt.)
- Zaimplementuj omawiany na wykładzie algorytm sortowania przez
kopcowanie.(4 pkt.)
-
Zmodyfikuj funkcję
Heapify
tak, aby używała iteracji zamiast rekursji. (1 pkt)
Wejście.
Liczby zapisane są w kolejnych wierszach pliku tekstowego.
Wyjście.
Posortowane liczby z pliku wejściowego zapisane w kolejnych
wierszach pliku wyjściowego.
3. (8/9.03.2021) Sortowanie szybkie,
Termin: 22/23.03.2021
Sprawdzian z heapsort
Zadania
Za tydzień (15/16.03) sprawdzian z quicksort.
4. (15/16.03.2021) Sortowanie szybkie - kontynuacja
Sprawdzian z quicksort
USTAWIENIE LIMITU REKURSJI I WĄTKÓW ( niestety może ono powodować zaburzenia w wykonywaniu programu i tym samym wpływać na wyniki szybkości wykonywania poszczególnych algorytmów, dlatego zaleca się niekorzystanie z wątków przynajmniej dla danych losowych)
import sys # trzeba dodać 2 biblioteki
import threading
sys.setrecursionlimit() # w nawiasach podać jakaś dużą liczbę, np 100000
threading.stack_size() # podobnie
def sortowanie_szybkie():
# tutaj kod sortowania, funkcje quicksort i partition
sortowanie = threading.Thread(target=sortowanie_szybkie) # juz poza ciałem funkcji sortwanie_szybkie
sortowanie.start()
5. (22/23.03.2021) Listy dowiązaniowe,
Termin: 06.04 do godz 12.00, dla obu grup
Zadania
6. (12/13.04.2021) Tablice z haszowaniem,
Termin: 19/20.04.2021
Zadania
7. (19/20.04.2021) Haszowanie z adresowaniem otwartym,
Termin: obie grupy 12.15 4.05.2021
Sprawdzian z adresowania otwartego za tydzień
Zadania
8. (26/27.04.2021) Haszowanie z adresowaniem otwartym,
Implementacja zadania
9. (04.05.2021) Haszowanie z adresowaniem otwartym,
Sprawdzanie zadań
10. (10/11.05.2021) Drzewa poszukiwań binarnych,
Termin: 24/25.05.2021
Zadania
1. Zadanie 7.1
2. Sprawdzian za tydzień
3. Sprawdzanie zadań z adresowania otwartego
11. (17/18.05.2021) Najdłuższy wspólny podciąg (NWP),
Termin: 31.05/1.06.2021
Zadania
1. Sprawdzian z drzew binarnych
2. Zadanie 9.1
3. Sprawdzian za tydzień
12. (24/25.05.2021) Grafy - ZADANIE DODATKOWE,
Termin: 7/8.06.2021
Zadania
1. Sprawdzian z NWP
2. Zadanie 8.1
3. Sprawdzanie zadań z drzew binarnych
PRZYSZŁE ZAJĘCIA - plan może ulec zmianie
13. (31.05/01.06.2021) Grafy,
1. Sprawdzanie zadań z NWP
14. (7/8.06.2021) Grafy,
1. Sprawdzanie zadań z grafów
Oceny:
5, >= 43
4.5, >= 38.5
4, >= 33.5
3.5, >= 29
3, >= 24