MCM032101 L

Tematy zajęć laboratoryjnych

Zajęcia laboratoryjne odbywają się w tym semestrze na komputerach wyposażonych w system operacyjny Ubuntu 12.04.2. Różni się on nieco od systemu Windows, i z tego powodu pozwalam sobie zaprezentować bardzo elementarne informacje na jego temtat.

  1. „Ala ma kota”
    1. Program „Hello world” (czy raczej „Ala ma kota”).
    2. Struktura programu.
    3. Deklaracje zmiennych i i działania na nich (głównie liczbach całkowitych).
    4. Polecenie ifelse (instrukcja warunkowa).
    5. Polecenie for (pętla).
    6. Funkcja printf
      • wyprowadzanie tekstów,
      • przejście do nowej linii,
      • wyprowadzanie wartości liczb całkowitych.

    Zadanie do wykonania

    Napisać program wypisujący tekst „Ala ma  <  >  kota” (gdzie w miejscu  <  >  będą pojawiały się liczby od 0 do 99, a słowo kota będzie miało poprawną formę (to znaczy „Ala ma 1 kota” ale „Ala ma 2 koty”.

    Dodatkowe punkty będą za sensowne użycie polecenia break i/lub continue.

  2. ,,Algorytm E”
    1. Polecenia while
    2. Polecenie dowhile

    Zadania do wykonania

    1. Napisać program realizujący algorytm Euklidesa:
      Dane są dwie dodatnie liczby całkowite mn. Należy znaleźć ich największy wspólny dzielnik, tj. największą dodatnią liczbę całkowitą, która dzieli bez reszty zarówno m jak i n.

      E1
      [Znajdowanie reszty] Podziel m przez n i niech r oznacza resztę z tego dzielenia.
      E2
      [Czy wyszło zero?] Jeśli r = 0, zakończ algorytm; odpowiedzią jest n.
      E3
      [Upraszczanie] Wykonaj m ← n, n ← r i wróć do kroku E1.

      Algorytm powinien być zaprogramowany na dwa sposoby: z wykorzystanie instrukcji whiledowhile.

  3. ,,Algorytm B”

    Zadania do wykonania

    • Narysować schemat blokowy algorytmu B:
      1. Przyjmij k ← 0, a następnie powtarzaj operacje: k ← k + 1, u ← u / 2, v ← v / 2 zero lub więcej razy do chwili gdy przynajmniej jedna z liczb uv przestanie być parzysta.
      2. Jeśli u jest nieparzyste to przyjmij t ←  − v i przejdź do kroku [k4]. W przeciwnym razie przyjmij t ← u.
      3. [k3] (W tym miejscu t jest parzyste i różne od zera). Przyjmij t ← t / 2.
      4. [k4] Jeśli t jest parzyste to przejdź do [k3].
      5. Jeśli t > 0, to przyjmij u ← t, w przeciwnym razie przyjmij v ←  − t.
      6. Przyjmij t ← u − v. Jeśli \(t \not = 0\) to wróć do kroku [k3]. W przeciwnym razie algorytm zatrzymuje się z wynikiem u ⋅ 2k.

      Uwaga: \(t \not = 0\) oznacza różne!

    • Zaprogramować algorytm B. Najlepiej bez korzystania z instrukcji goto, używając wyłącznie instrukcji if, while i ewentualnie do while.
  4. Metoda połowienia
    1. Zadanie jest proste. Mamy funkcję f(x) ciągłą i taką, że na końcach pewnego przedziału [A, B] f(A)f(B) < 0. Zatem, funkcja ta zmienia znak w przedziale [A, B] (co najmniej raz) ma zatem (co najmniej jedno) miejsce zerowe w tym przedziale.
    2. Przedział [A, B] dzielimy na pół (wyznaczając odpowiednio punkt C).
    3. Odrzucamy ten z przedziałów [A, C], [C, B] w którym funkcja nie zmienia znaku (to znaczy ma ten sam znak na końcach przedziału).
    4. Postępowanie prowadzimy tak długo, aż długość przedziału [A, B] będzie mniejsza od zadanej liczby ɛ.

    Uwaga: Obliczenia najprościej wykonać dla funkcji sin1 wybierając 0 < A < 33, 5 < B < 6.

    Powyższe zadanie można również zaprogramować korzystając z rekurencji.

    Algorytm połowienia zaprogramowany w Blockly.

  5. Zadanie do zrobienia

    • Zaprogramować metodę połowienia.
    • Zaprogramować metodę połowienia wykorzystując funkcje (minimum dwie: pierwsza to funkcja, której miejsca zerowego szukamy, druga — metoda połowienia).
    • Zaprogramować zadanie metodą rekurencyjną.
  6. Wyszukiwanie binarne
    • Mamy tablicę zawierającą ułożone w kolejności malejącej liczby (przyjmijmy, dla skupienia uwagi — całkowite).
    • Należy stworzyć algorytm, stosując metodę wyszukiwania binarnego, sprawdzający czy zadana liczba X znajduje się w tablicy. Jeżeli tak — algorytm zwraca numer pozycji, na której znajduje się liczba.
    • Ogólny schemat blokowy algorytmu znaleźć można wśród slajdów wykładu Technologie Informacyjne „Złożoność obliczeniowa. Trudne zadania.” (slajd 33 i następne).

    Zadania do wykonania

    Po zaprogramowaniu algorytmu należy go bardzo dokładnie sprawdzić wybierając liczby z zakresu danych w tabeli (znajdujące się w tabeli i nie występujące w tabeli), spoza tego zakresu. Algorytm powinien działać dla tabeli o długości jeden element, dwa elementy, więcej…

    Jeżeli ktoś rozwiązał zadanie bez funkcji powinien rozważyć możliwość zrealizowania wersji korzystającej z funkcji.

  7. „Newton” Algorytm opisany jest na slajdach do wykładu wprowadzającego i o funkcjach (slajd 62 i natępne).
    Program może być rekurencyjny lub nie.
  8. „Wieże Hanoi” Algorytm opisany został na wykładzie z Technologii informacyjnych poświęconym różnym rodzajom algorytmów w dziale rekurencja (slajd 55 i następne). Nierekurencyjna wersja algorytmu podana została na wykładzie z Technologii Informacyjnych dotyczącym złożoności obliczeniowej (slajd 41 i następne). Wersja algorytmu w Blockly.
  9. Odwracanie napisu („głowa/ogon”). Ten algorytm omawiany był na wykładzie z Technologii Informacyjnych na wykładzie o poprawności programów (slajd 31 i następne). Przykładowa implementacja w Blockly.
  10. Statystyki tablicy. Stosunkowo prosty program, który pyta użytkownika o wymiary tablicy dwuwymiarowej (liczbę wierszy, na przykład n i liczbę kolumn, na przykład m, a następnie wykonuje następujące czynności:
    • Organizuje miejsce na tablicę i tablice pomocnicze.
    • Aby uprościć sobie życie zakładamy, że program wyposażony będzie w osobną funkcję wypełniającą tablicę losowymi danymi. Może ona wyglądać jakoś tak:

      (oczywiście, trzeba uzupełnić wszystko co potrzebne!)

    • Następnie program wylicza średnią (osobna funkcja!) i wariancję (osobna funkcja!) dla każdego wiersza i każdej kolumny oraz dla całej tablicy i wyprowadza na terminal wszystkie wyniki.

Dostępne jest najprostsze ćwiczenie pozwalające przekazać tablicę dwuwymiarową do funkcji.

Zadanie może być wykonane na dwa sposoby: korzystając deklaracji tablic (jak w ćwiczeniu) albo przydzielając na nie pamięć w sposób dynamiczny (korzystając z funkcji malloc). Tu jest ściąga.

  • Maszyna stanów Program nawiązuje do maszyny Turinga. Szerzej opisywana ona była na zajęciach z Technologii Informacyjnych. Mamy dwa zadania do wyboru:
    1. Funkcja sprawdzająca czy zadany ciąg liczb jest liczbą całkowitą.
    2. Funkcja sprawdzająca czy zadany ciąg liczb jest liczbą rzeczywistą.

    Idea zadań jest taka, że musimy wyobrazić sobie jak wygląda liczba całkowita:

    • może być poprzedzona dowolną liczbą „odstępów”2
    • pierwszym znakiem rozpoczynającym liczbę może być cyfra lub znak + albo -;
    • później mogą być już tylko cyfry;
    • liczbę kończy pierwszy znak nie będący cyfrą.

    Możemy narysować maszynę Turinga realizującą algorytm sprawdzania czy napis jest liczbą zgodny z powyższymi zasadami. Wyglądać ona będzie tak jak na rysunku

    diagram_01
    Diagram (uproszczonej) maszyny Turinga sprawdzający czy napis jest liczbą
  • Można opisać podobne zasady opisujące wygląd liczby rzeczywistej:
    • ignorujemy znaki puste na początku;
    • później może być +/–/cyfra,
    • pomiędzy cyframi może pojawić się kropka (lub przecinek) dziesiętna,
    • po cyfrach może pojawić się litera e (lub E) a po niej plus albo minus albo odstęp, a później cyfra/cyfry wykładnika.

    Uproszczony (choć niewolny od błędów) diagram maszyny Turinga sprawdzającej czy napis jest liczbą rzeczywistą przedstawia rysunek

    diagram_02
    (Uproszczony) diagram przejść maszyny Turinga sprawdzającej czy napis jest liczbą rzeczywistą

    Wybieramy jedno z tych zadań i programujemy. Wszystkie czynności sprawdzające powinna wykonywać funkcja (na potrzeby instrukcji nazwę ją czy, wywoływana w sposób następujący:

    na przykład:

    Funkcja zwraca wartość jeden gdy napis jest liczbą, zero w przeciwnym razie.

    Uwaga 1: Można zaprogramować funkcję bardziej rozbudowaną, która będzie poprawnie rozpoznawała jako liczby stałe dwójkowe, ósemkowe czy szesnastkowe…

    Uwaga 2: Pod koniec zajęć sprawdzam co udało się osiągnąć.

    Uwaga 3: Można zaprogramować oba!

  • Struktury danych: Operacje z uwzględnieniem błędów Na zajęciach z Technologii Informacyjnych pojawił się problem arytmetyki liczb obarczonych błędem bezwzględnym (slajdy począwszy od 26).Zakładamy, że liczby rzeczywiste zapisywane są jako następująca struktura:

    x.val przechowuje wartość liczby, x.err przechowuje jej błąd bezwzględny.Należy stworzyć bibliotekę operacji arytmetycznych (co najmniej suma, różnica, iloczyn, iloraz) na takich liczbach, która oprócz wykonywania samych działań, będzie za każdym razem wyliczała błąd bezwzględny wyniku.Biblioteka powinna też być wyposażona w funkcje poprawnego zaokrąglania wyniku (działającą dla dowolnych liczb: zaokrąglenie z dokładnością …,tysięcy, setek, dziesiątek, jedności, dziesiątych, setnych, tysięcznych…). Podczas zaokrąglania powinien być odpowiednio korygowany błąd bezwzględny.Następnie należy wykorzystać funkcje tej biblioteki do powtórzenia obliczeń zaprezentowanych na slajdach 40-43 (lub, jeżeli to za trudne, jakieś inne „sensowne” obliczenia — objętość jakiejś popularnej bryły geometrycznej, rozwiązanie równania kwadratowego — potrzebne będzie oszacowanie błędu pierwiastka,…).

  • Program sprawdzający czy dwa napisy są anagramami (to znaczy występują w nich dokładnie te same litery).
  • czytający tekst (bez polskich liter!) z konsoli i podający po zakończeniu czytania danych liczbę wystąpień każdego znaku.Zadanie pomocnicze:
    Napisać następujący program (o nazwie, na przykład, test.c):

    Następnie należy otworzyć okno cmd (konsolę) i przejść do kartoteki w której jest plik wykonywalny.W kartotece tej należy utworzyć plik o nazwie, na przykład a.txt z dowolną zawartością tekstową.Uruchamiamy program w oknie cmd następującym poleceniem (zakładam, że program wykonywalny nazywa się test.exe):

    Następnie należy obejrzeć plik b.txt w notatniku.Czy ta wiedza może się przydać do realizacji powyższego zadania?

  • Napisz rekurencyjny program, który wyznacza sumę liczb zawartych w tablicy bez użycia pętli.
  • program czytający z pliku informacje i wyświetlający każdy bajt w kilku formatach. Na przykład tak: plik o poniższej zawartości:

    jest drukowany tak:

    Najpierw jest anumer bajtu od początku pliku. Póżniej zawartość tekstowa. kolejne trzy linie zawierają zawartość każdego baju wyświetlną dziesiętnie, szesnastkowo i ósemkowo.

 


  1. Ale pomysły ambitniejsze będą mile widziane!
  2. Jako odstępy uważać będziemy dowolne „znaki białe” (to znaczy takie, które nie zostawiają na papierze żadnego czarnego śladu). Będą to odstęp, znak tabulacji (\t), znak nowej linii (\n) i być może jeszcze jakieś…