IICp (mat.-inf.!) 2020/21

quiz z Gór Kamiennych   odpowiedzi     kartkówki, sprawdziany, poprawy, ... (z informatyki)     o blokach olimp. (z inf.!)

lista zadań (od I klasy!)     nasze programiki     Łamacze Szyfrów  


zadanka do ćwiczenia wydawania i pakowania (dla wszystkich zainteresowanych) - Warto poćwiczyć! (Gdyby ktoś nie miał dostępu do Themisa lub tej sekcji, niechaj pyta!)


O Waszych możliwych przyszłych badaniach   Jak to robią Wasi starsi koledzy


Gr. 1 - na 9/6 (przypominam!) należy obliczyć liczbę operacji w algorytmie Freta (i umieć zrealizować go w C++!) oraz zrozumieć ten cwańszy wg tego, co wrzuciłem do plików w naszym teamsowym zespole. Przypominam również, że nie omówiliśmy jeszcze problemu najkrótszej ścieżki (drogi) między dwoma wierzchołkami - jeszcze w maju 2021 mieliście spróbować wymyślić algorytm jej znajdowania (wystarczy opis dla człowieka, ale ma działać dla dowolnego grafu, tzn. także gdy nie będzie łatwo widać, którędy iść, np. od wierzchołka 1 do 8 w tym grafie).

Kto ma aspiracje szóstkowe, może pomyśleć nad eksperymentalną weryfikacją złożoności quicksorta w przypadku optymistycznym lub średnim.


Grupa 2 - jako ostatni temat w tym roku polecam https://eduinf.waw.pl/inf/alg/001_search/0138.php, do słów "Dojście do wierzchołka 5: 0–4–5, koszt 5".

Przypominam, że powinniście poza tym mieć już ze zrozumieniem zrozumiane to, co jest w PDF-ach idol i idol2, które wrzuciłem do plików w naszym zespole teamsowym, (i zastanowić się nad zapisem algorytmu wyszukiwania idola na podstawie macierzy sąsiedztwa grafu), ORAZ wysłać mi prywatnym czatem pytanie lub zagadnienie (każdy przynajmniej jedno), o którym chcielibyście porozmawiać, zupełnie dowolne, może być nawet niezwiązane z informatyką ani szkołą.

Ciekawe tematy (również do badań własnych):
- zad. z "KoALi" (patrz kartkówka grupy 1 - w pliku wyżej),
- problem komiwojażera.

Na 19 IV należało zastanowić się nad zaczerwienionymi pytaniami ze str. 3 naszego google doca, a Rozszerzeni powinni byli również wykonać polecenie na dole str. 1. Wszyscy(!) powinni (m.in.!) umieć już dawno zapisać i rozumieć funkcje Cezar (z dowolnym przesunięciem) i deCezar oraz rozumieć (ideę oraz funkcje w C++!) Vigenere'a (patrz nasz google doc) i deVigenere'a, a Osobniki Rozszerzone także samodzielnie je zapisać!
Proszę też zastanowić się, co potrzebujemy jeszcze wyjaśnić w kwestii zad. 2.2ę i f (które mieliście (ze szczegółami!) przemyśleć).
Wrócimy też do zad. 2.3.I jako funkcji (co nie obowiązywało ludzi nierozszerzonych).

Ambitniejsi mogą pomyśleć nad zrobieniem 2.2ę przez porównywanie kolejnych cyfr od lewej i od prawej. (Można je np. odrywać dzięki odpowiedniej modyfikacji naszej funkcji pierwszacyfra i powtarzać ten proces, aż... Można robić to rekurencyjnie!) Może niełatwe, ale na poziomie Waszej matury!


Z I SEMESTRU:

Na styczeń mieliście umieć:

  • to, co jest na stronach 1-3(!) http://informatyka.wroc.pl/node/801 (powinniście rozumieć opis i umieć przeprowadzić cały algorytm (wraz z ustaleniem, co należy pakować!) dla zadanych danych, ale oczywiście fajnie, jak będziecie to także umieli zaprogramować);
  • umieć zaprogramować (!, w C++!) algorytm z podręcznika (który wrzuciłem do plików naszego zespołu w MS Teams - dorzuciłem stronę z rozwiązaniem!) oraz wiedzieć, jak wygenerować informację, jakich monet użyć do optymalnego wydania - można (i warto!) przeczytać to na str. 4 http://informatyka.wroc.pl/node/801.

    Na 16 XII należało napisać:
    - pakujWgWartosciWlasciwych o takiej samej specyfikacji jak poprzednio (patrz nasz google doc, i proszę to uwzględnić!), przy czym należy wziąć pod uwagę to, o czym mówiliśmy na ostatniej lekcji (bo wśród Waszych procedur jest więcej takich, które zniszczyłyby worek Heraklesa!); warto też przy okazji poprawić poprzednią procedurkę;
    - wydaj, która napisze, w jaki sposób wydać podaną kwotę, mając do dyspozycji nieskończenie wiele monet o (zapisanych w tablicy!) nominałach 1, 2, 5, 10, 20, 50, 100, 200, 500 gr, minimalizując liczbę użytych monet (czyli np. dla wejścia 2004 (co to za wejście?) odpowiedzią powinno być: 500 500 500 500 2 2); podpowiedź: można wykorzystać pomysł Heraklesa!

    Ponadto należy zastanowić się, jak można by pomóc Heraklesowi (nadal zad. 2.1 z listy) sortowaniem (uwaga: w grę wchodzą dwie tablice!) i kiedy sortowanie do rozwiązania jego problemu się opłaci.

    Na 9 XII były zadane procedurki: odbijWpionie, transponuj, przyciemnij (zmieniającą poziom szarości każdego piksela na o połowę mniejszy), coDrugiWiersz, obroc90 (a jak to za trudne - obroc180);

    Uwagi:
    - nasza rybka znajduje się tutaj (wraz z nagłówkiem! - co uwzględniać powinny Twoje procedury - analogicznie do tej zaczętej przeze mnie); niestety przeglądarka może mieć gdzieś zapisany poprzednio pobrany pllik o tej samej nazwie, więc trzeba wtedy kazać jej jakoś dogłębnie pozapominać, ew. można ręcznie dokleić nagłówek: "P2 302 178 255";
    - jeśli ktoś ma dobrze napisane procedury transformacji macierzy (np. odbijWpionie, transponuj - mogą się nazywać tak samo jak te operujące na plikach, bo C++ rozpozna, której chcemy użyć, po podanych jej argumentach), to może wkleić je do programu i użyć ich w pisanych teraz;
    - niektóre przekształcenia zmieniają wymiary obrazka - trzeba to uwzględnić w nagłówku tworzonego pliku;
    - mam nadzieję, że udane efekty wszystkich operacji (w kolejno tworzonych plikach) z satysfakcją obejrzysz w odpowiednim programie (może być to np. IrfanView, GIMP czy Libre Office).

    Na 18 XI było:

  • podać ustawienie liczb 0, 1, 2, 3, ..., 9 o 44−n inwersjach, gdzie n jest Twoim nrem w dzienniku (* - można napisać program, który takie ustawienie generuje - dla dowolnego n - zachęcam! tak czy siak odpowiedź (swoją lub programu) warto sprawdzić funkcją, którą omawialiśmy jako zad. dom. na 4 XI); ustawienie to z uzasadnieniem poprawności wyniku proszę wkleić mi jako plik tekstowy lub dokument na MS Teams do końca wtorku;
  • ustalić, które z sortowań elementarnych (wszystkich trzech) i ew. w jakich wariantach są stabilne;
  • przygotować się na sprawdzian; kto może, niech przygotuje również kamerkę!
  • przerobić zad. 0 i 1 z tego programiku (bez wymówek, jak trudno sobie przypomnieć tablice dwuwym.! w razie potrzeby zapraszam na konsultacje we wt. 15.30-16.15, ew. w innym ustalonym ze mną terminie).

    Wcześniej należało już umieć (i nadal należy!):

  • napisać bubble sorta z ulepszeniem polegającym na porównywaniu tylko do miejsca ostatniej zamiany, (tak jak w www.youtube.com/watch?v=lyZQPjUT5B4), ew. chociaż takim, które kończy algorytm, gdy w ostatnim przebiegu nie było żadnej zamiany;
  • ustalić, jaka jest złożoność pesym. Bubble sorta z dowolnymi ulepszeniami;
  • ustalić liczbę porównań i podstawień/zamian w przypadkach optym., pesym. i średnim sort. przez prostą zamianę;
  • napisać funkcję, która dla danej tablicy ustali, ile zamian wykona się przy jej sortowaniu przez zamiany, bez wykonywania sortowania. Jaka jest jej złożoność? Czy jest szybsza niż bubble sort?
  • wszystko, o czym mowa w wykładzie www.youtube.com/watch?v=pB41Z8E90Yw do momentu 19:47, i napisać z użyciem wyszukiwania połówkowego:
    - funkcję ile - która dla danej posortowanej tablicy zer i jedynek ustali, ile jest w niej zer;
    - procedurę wstaw - która, przyjmując n-elementową tablicę, której elementy poza ostatnim są posortowane, przestawi ostatni na odp. pozycję (tzn. np. tablica (0, 4, 7, 8, 9, 5) powinna zmienić się na (0, 4, 5, 7, 8, 9)); jeśli to trudne (chociaż prawie to samo robiliście w czerwcu z p. prof. Koszowską), to może warto posłuchać wykładu do momentu 24:51, ew. proszę poszukać sobie binsearcha w Sieci (i oczywiście spróbować go zrozumieć oraz przerobić dla naszych potrzeb).
  • przeanalizować drugi algorytm p. Milczka (ten, gdzie s=⌊l+p⌋/2 - wystarczy, że będziecie umieli ten) dla wyszukiwania w tablicy (1, 3, 5, 5, 7, 9, 10, 12, 14, 16, 18, 19) liczb: 0, 2, 5, 8, 22;
  • przeanalizować liczbę porównywań wykonywanych w przypadkach optym., pesym. i średnim sortowania przez wstawianie połówkowe, porównać wyniki z wstawianiem prostym (można się upewnić, czy się je rozumie, na podstawie www.youtube.com/watch?v=ROalU379l3U);
  • przeanalizować ten program (wg wskazówek z komentarzy) i napisać własny, w którym stworzysz plik o nazwie będącej Twoim pseudonimem informatycznym, wpiszesz do niego 7 dowolnych liczb, a następnie co drugą z nich przepiszesz do pliku "wynik.txt".

    Zachęcam również nadal, żeby spróbować znaleźć najgorszy układ danych dla SelectSorta, co jest może dość trudną łamigłówką, ale może ktoś napisze sortowanie przez jednoczesny wybór min. i maks.? To fajne wyzwanie, na Waszym poziomie! (Na początek niech działa tylko dla parzystych n).

    Zadanie dla uczniów o inicjałach OF - do wyboru: polubić sortowania lub przeprowadzić analizę porównawczą dowolnych dziesięciu spośród opisanych tu algorytmów.