Zajecia

07.06.2013: Kopce (stogi)

Poznamy dziś nową strukturę danych nazywaną kopcem lub stogiem (są to tłumaczenia angielskiego terminu heap). Kopiec służy do przechowywania liczb. Pozwala na

1. Szybkie wstawianie dodatkowych liczb.

2. Szybkie odnajdywanie liczby najmniejszej.

3. Szybkie usuwanie wybranej liczby (np. tej najmniejszej).

Co to znaczy szybkie? Koszt każdej z powyższych operacji jest proporcjonalny do logarytmu rozmiaru kopca. Logarytm (dwójkowy) to (w przybliżeniu) liczba cyfr liczby w zapisie dwójkowym. Przykładowo logarytm dwójkowy z liczby 4 to 2, z liczby 8 to 3 a z liczby 1024 to 10.

Ćwiczenie. Oblicz logarytm dwójkowy z liczb 537 i 65536.

Logarytm z miliona równy jest około 20. Wstawienie, usunięcie elementu do kopca o milionie elementów zajmuje tylko 20 operacji. Znalezienie najmniejszego elementu to tylko jedna operacja. Gdyby nasze dane nie były w żaden sposób uporządkowane musielibyśmy przeszukać całą tablicę, wykonując 1000000 operacji. To istotna różnica!

Budowę kopca omówimy na tablicy. Tu tylko dla utrwalenia zapisuję niezmiennik kopca:

t[i] < t[2*i] && t[i] < t[2*i+1]

Elementy kopca numerujemy od '1'. Lewy i prawy syn elementu 'i' ma numer '2i' i '2i+1', zaś ojciec elementu o numerze 'i' ma numer 'i/2' (dzielenie całkowite, z zaokrągleniem w dół).

Zadanie. Zaimplementuj kopiec. Napisz program wczytujący liczbę 'n' a następnie n liczb i wyświetlający najmniejszą z nich. Program powinien do tego wykorzystać strukturę kopca.

Zadanie. Jak wyżej, ale program powinien wypisać liczby od najmniejszej do największej.

Zmierz czas działania tak napisanego programu sortującego i porównaj go z czasem działania sortowania bąbelkowego i przez wybór.

31.05.2013: Dzień wolny (Uroczystość Najświętszego Ciała i Krwi Pańskiej)

24.05.2013: Potyczki algorytmiczne.

W najbliższy wtorek zaczynają się potyczki algorytmiczne. Z regulaminu:

Uczniowie szkół ponadgimnazjalnych, gimnazjów i szkół podstawowych mogą przystąpić do konkursu w dwu- lub >trzyosobowej drużynie. Przepisy dotyczące uczestników konkursu odnoszą się do wszystkich członków drużyn.

Zachęcam do rejestracji i zmierzenia się z zadaniami. Dziś omówimy dwa zadania z potyczek z zeszłych lat

1. Bandżo

2. Przekątne

i spróbujemy zaimplementować rozwiązania.

Zapraszam też na jutrzejsze "Warsztaty myślenia problemowego", które odbędą się na Wydziale Matematyki, Informatyki i Mechaniki UW o godz. 10 w sali 3180.

10.05.2013, 17.05.2013: Kółko nie odbyło się.

03.05.2013: Uroczystość Najświętszej Maryi Panny Królowej Polski

26.04.2013: Sortowanie kubełkowe

Kto nie napisał sortowania bąbelkowego lub przez wybieranie zgłasza się! (Poza Biedronkami.)

Testowanie szybkości algorytmu

1. Zapoznaj się z artykułem o losowaniu liczb i wykonaj ćwiczenia.

2. W katalogu podstawy/losowanie znajdziesz program generator.cpp. Służy on do generowania długich ciągów liczb losowych. Przykład użycia:

$ cd podstawy/losowanie

$ g++ generator.cpp -o generator

$ ./generator 1000

Ostatnie polecenie generuje ciąg 1000 liczb z przedziału od zera do miliarda.

3. Zmodyfikuj swoje algorytmy sortowania tak, by sortowały n liczb, gdzie n jest liczbą podaną jako pierwsza na wejściu.

4. Za pomocą generatora ciągów losowych będziesz mógł przetestować swoje algorytmy sortowania. Przejdź do swojego podkatalogu w katalogu zajecia, skompiluj sortowanie bąbelkowe

$ g++ bubble_sort.cpp -o bubble_sort

i wykonaj polecenie

$ time ../../podstawy/losowanie/generator 10 | ./bubble_sort

Po wykonaniu tego polecenia powinien zostać wyświetlony ciąg dziesięciu posortowanych liczb a następnie czas wykonania programu.

Sprawdź działanie instrukcji

$ time ../../podstawy/losowanie/generator 100 | ./bubble_sort

$ time ../../podstawy/losowanie/generator 1000 | ./bubble_sort

$ time ../../podstawy/losowanie/generator 10000 | ./bubble_sort

Przy coraz większych danych wyjściowych istotny stanie się czas wypisywania wyniku na terminalu. Wyświetlanie można wyłączyć wpisując

$ time ../../podstawy/losowanie/generator 100 | ./bubble_sort > /dev/null

$ time ../../podstawy/losowanie/generator 1000 | ./bubble_sort > /dev/null

$ time ../../podstawy/losowanie/generator 10000 | ./bubble_sort > /dev/null

Jakie są Twoje czasy? Jakie czasy osiąga selection_sort? Sprawdź!

Sortowanie kubełkowe

Algorytm omówimy na zajęciach. Do jego testowania i porównania z np. sortowaniem bąbelkowym użyjesz ciągu generowanego poleceniem

$ ../../podstawy/losowanie/generator 100000 1000000

Ciąg ten zawiera 100000 liczb z przedziału od 0 do 999999.

Biedronki

Dzisiaj waszym celem będzie zaprojektowanie witrażu i napisanie programu, który go wyświetla. Dwie inspiracje:

Zacznijcie od aktualizacji repozytorium

$ cd kinf/

$ git pull

Sprawdzenia, czy ustawiony jest prawidłowy adres email

$ git config user.email

Przejścia do katalogu allegro5/primitives

$ cd allegro5/primitives

Skompilowania przykładowego programu

$ make

I uruchomienia go

$ ./primitives

(wychodzi się klawiszem Escape). Następnie skopiujcie ten program do swojego katalogu.

$ cd ../../zajecia/nazwatwojegokatalogu

$ cp ../../allegro5/primitives/primitves.cpp .

(klawisz Tab może być przydatny. Dlaczego?)

I zacznijcie czytać kod.

$ gedit primitives.cpp &

Po zrozumieniu kodu (omówimy go też wspólnie) zaprojektujcie własny witraż i napiszcie program, który go wyświetla. Opis wszystkich dostępnych funkcji znajdziecie tutaj. Powodzenia!

19.04.2013: Uzupełnianie zaległości

Krótki przegląd tabeli wyników pokazuje, że dziś i przez najbliższy tydzień zajmować się będziemy uzupełnianiem zaległości.

Tytułowe sortowanie kubełkowe i sortowanie napisów przeniesione niniejszym zostaje o x kółek, gdzie x to liczba tygodni, które spędzimy łatając dziury w wykonanych zadaniach.

Dziś zaczniemy od zaliczeń - każdy robi dokładny przegląd swoich programów i zaznacza długopisem w tabeli zadania rozwiązane bądź zgłoszone do oceny.

Proszę zerknąć do listy tematów, które trzeba zgłębić, by zostać początkującym adeptem informatyki!

Biedronki zaczynają od ćwiczeń z git-a, potem zmienne i wyrażenia.

12.04.2013: Sortowanie bąbelkowe i przez wybieranie

Niedokońcapoważne prezentacje:

Sortowanie bąbelkowe (bubble sort)

Sortowanie przez wybieranie (selection sort)

Sortowanie bąbelkowe vs sortowanie szybkie (quick sort)

Dziś na zajęciach postaramy się wykonać ćwiczenia z sortowania. Przypominam o zaległych zadaniach z zeszłych zajęć.

Zadanie domowe

Napisz program, który wypisuje na ekranie kolejne wiersze trójkąta Pascala oraz zrób pozostałe ćwiczenia z sortowania.

Przykładowy wynik działania programu:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1

Grupa przedszkolna

Temat pętle, do zrobienia są wszystkie ćwiczenia.

05.04.2013: Piła, haft i mrówka Langtona

1. Omówimy działanie programu z katalogu allegro5/plansza2d/

2. Na rozgrzewkę zadania Postać piły i Haft z II etapu OIG.

3. Następnie zajmiemy się projektem Mrówka Langtona.

Dokąd idzie mrówka Langtona?

Grupa przedszkolna

1. Starszaki - pętle

2. Młodsi - uczymy się korzystać z github-a, poruszać w terminalu, kompilować i uruchamiać najprostsze programy a następnie piszemy pierwsze programy

22.03.2013: Dzień przed Olimpiadą

Już jutro II etap OIG. Z tego względu powalczymy dziś z zadaniami olimpijskimi. Grupa przedszkolna zajmuje się ćwiczeniami z instrukcji warunkowej.

Grupa początkująca walczy z zadaniami

1. Figura

2. Pieczątki

3. Sumy

4. Liczebniki

Z grupą zaawansowaną omówimy zadania z zeszłego tygodnia i zadania z konkursu

SKN 130302 / G4

(potraktujcie go jako trening). Rozwiązania zadań tradycyjnie umieszczamy w repozytorium. Powodzenia!

15.03.2013: Gra w życie

Grupa początkująca

Na rozgrzewkę zrobimy zadanie choinka. Rozwiązanie wysyłacie do oceny na stronę OIG oraz zamieszczacie w repozytorium, 15 minut powinno wystarczyć.

Następnie projekt gra w życie (do kontynuacji w domu). Uwaga: przed przystąpieniem do tego projektu musisz mieć skończone zadanie wzory (patterns.cpp).

Do domu: even Fibonacci numbers, figury szachowe, zapałki, czas wycieczki.

Grupa zaawansowana

Trening - archiwum zadań 2012/2013 / SKN / SKN 130119 G4. Powinniście dać sobie radę ze wszystkimi zadaniami w 60 minut. Pod koniec zajęć omówimy rozwiązania.

Już za tydzień II etap Olimpiady Informatycznej.

Wyniki konkursu sprzed tygodnia pozostawiam bez komentarza:

Zadania domowe:

1. (sobota) zadania piramida liczbowa, szachownica oraz odejmowanie.

2. (poniedziałek) drzewo, gra w czynniki.

3. (wtorek) imieninowy zbiór - napisz algorytm brute-force, sprawdzający wszystkie przypadki. Za pomocą operacji na bitach i odpowiedniego kodowania danych można szybko sprawdzić, czy w konkretnym zbiorze liczb wszystkie pary są względnie pierwsze.

4. (środa) prezenty

5. (czwartek) lampki

Rozwiązania proszę weryfikować w serwisie OIG oraz zamieszczać w repozytorium.

08.03.2013: Wzory

1. Grupa zaawansowana: konkurs. Do domu pozostałe ćwiczenia z funkcji, slogany i zaległości.

2. Grupa początkująca: zadanie wzory. Do domu multiplies of 3 and 5 oraz kwadraty i sześciany i zaległości.

01.03.2013: Algorytm Euklidesa

1. Grupa zaawansowana: po uzupełnieniu zaległości zabieramy się za algorytm Euklidesa (ćwiczenia proszę wykonać na kartce). Następnie zapoznamy się ze strukturami.

Zadania domowe: przyciski.cpp, pieczatki.cpp (wskazówki do zadań znajdziesz w kąciku olimpijskim).

2. Grupa początkująca: uzupełniamy zaległości. Jeżeli masz zaliczone lub właśnie zaliczyłeś zaległe zadania, to pomóż innym (zwłaszcza w obsłudze git-a).

Zadania domowe (do "nadgryzienia" na zajęciach): Choinka2 (choinka2.cpp), Kasztany (kasztany.cpp). Rozwiązania zadań należy umieścić w plikach choinka2.cpp i kasztany.cpp w swoim katalogu oraz wysłać do oceny w serwisie main.

22.02.2013: Tablice dwuwymiarowe / funkcje

1. Grupa zaawansowana: funkcje i ćwiczenia 1-5 z funkcji oraz Kącik Olimpijski.

2. Grupa początkująca: jeżeli nie umieściłeś jeszcze w repozytorium swojego rozwiązania zadania WERSALIKI, zrób to teraz (w katalogu zajecia/(Twój login)/).

Pomocą służy strona jak używać git-a? z naszego wiki.

3. Rozwiążemy zadanie uʍop ǝpısdn.

Kod źródłowy rozwiązania umieść w repozytorium w odpowiednim katalogu.

4. Zadanie dysleksja z konkursu "Potyczki Algorytmiczne".

5. Jeżeli sprawnie uwiniemy się z powyższymi zadaniami, to pokażę Wam zastosowanie tablic dwuwymiarowych (Allegro 5) - zadanie arena.

15.02.2013: Tablice - napisy

1. Code review: https://github.com/anagorko/kinf/blob/master/allegro4/sokoban/sokoban.cpp.

2. Zaglądamy do Księgi kucharskiej i odpowiadamy na nagromadzone tam pytania. W szczególności na to, gdzie zapisywać rozwiązania zadań.

3. Grupa zaawansowana zabiera się za Kącik Olimpijski.

4. Z grupą początkującą rozwiązujemy zadanie WERSALIKI (na tablicy), następnie w parach implementujecie ostatnie z rozwiązań (tablice translacji).

01.02.2013: Tablice - wprowadzenie

Tablice

Ćwiczenia z tablic jednowymiarowych.

Do domu

Ćwiczenia Inicjalizacja, Na wspak, Parzyste przodem z tablic jednowymiarowych.