Powrót na stronę dydaktyki

Nazwa
Podstawy Programowania Strukturalnego
Uczelnia
Politechnika Warszawska
Wydział
Matematyki i Nauk Informacyjnych
Rok studiów
I
Semestr
zimowy
Specjalność
SI/INF
Wymiar godzinowy w/ć/l/p
2/2/1/0
Uwagi
Wykład prowadzi W.Homenda


UWAGA: bieżący rok nie będzie miał zadań z maszyny Touringa.
Plan ćwiczeń:
  1. Ćwiczenia
    1. Podstawowe pojęcia - algorytm, program, kod źródłowy i maszynowy, kompilacja i interpretacja
    2. Metody opisu algorytmu
      1. schemat blokowy (ćwiczenie z trójmianem kwadratowym)
      2. opis naturalny (ćw z rozwiązywania układu 2 równań liniowych metoda wyznaczników)
    3. Ręczna symulacja algorytmu
    4. Algorytm sortowania bąbelkowego
  2. Ćwiczenia
    1. Algorytm łączenia permutacji
      1. idea, przykład
      2. opis w języku naturalnym
      3. schemat blokowy
      4. symulacja
    2. Sortowanie przez prosty wybór
      1. Wersja podstawowa
      2. Schemat blokowy
  3. Ćwiczenia
    1. Sortowanie przez proste wstawianie
      1. Wersja podstawowa
      2. Schemat blokowy
    2. Przepisanie p.A w Pascalu i C
    3. Konwersje liczb między systemami liczbowymi schemat i opis słowny.
  4. Ćwiczenia
    1. Komputer Touringa (wszystkie zadania 3 etapach - prosty opis słowny idei, dokładny opis słowny, tabelka)
      1. Prosta negacja znaków 0 i 1 na taśmie
      2. Proste przesuniecie wyniku
      3. Wyznaczanie 2^n
  5. Ćwiczenia
    1. Komputer Touringa (wszystkie zadania 3 etapach - prosty opis słowny idei, dokładny opis słowny, tabelka)
      1. Zamiana liczb w systemie 1 na binarny.
      2. Sortowanie znaków a,b,c na taśmie
    2. Zapis liczb w zapisie IEEE
      1. Zamiana przykładowych liczb np.(-13,75) na zapis IEEE
      2. Zadanie projektowania stylu zapisu liczb zmiennopozycyjnych dla zadanych ograniczeń
      3. Algorytmy obejścia tablicy wierszami i skośnie (tylko macierz kwadratowa górna)
      4. Zapisywanie macierzy symetryczne A = AT z 1 na przekątnej w tablicy jednowymiarowej. Przeliczenie pary indeksów (i,j) na indeks w tablicy jednowymiarowej i odwrotnie.
  6. Kolokwium I
  7. Ćwiczenia
    1. Liczenie średnich (wersje ze znaną długością ciągu liczb i z 0 kończącym podawanie liczb)
    2. Algorytmy zamieniające liczbę byte na tablice 8 element-ową zawierającą reprezentacje binarną liczby i odwrotnie
    3. Konwencje nazywania zmiennych w programach
    4. Konstrukcja 3 podstawowych pętli przy pomocy instrukcji warunkowej i skoku
    5. Zamiana jednego typu pętli na inny
    6. Operacje na bitach - najprostsze maski
  8. Ćwiczenia
    1. Oddanie prac i omówienie wyników kolokwium
  9. Ćwiczenia
    1. Operacje na bitach (wszystkie operacje wykonywane na słowach o nieznanej ilości bitów, ze znakiem)
      1. Przypomnienie operacji bitowych
      2. Proste maski
        • ustawiające k-ty bit
        • zerujące k młodszych bitów
        • negujące bity od k do t
      3. Testowanie i przesuwanie sekcji bitów
      4. Zamiana miejscami sekcji bitów a1 do b1 z a2 do b2 przy założeniu że a1>b1>a2>b2
    2. Struktury,unie i funkcje na przykładzie liczb zespolonych
  10. Ćwiczenia
    1. funkcje i struktury
      1. Uwagi o projektowaniu procedur i funkcji oraz o metodach przekazywania danych
      2. Tablicowe implementacje stosu i kolejki
    2. Arytmetyka wskaźników
      1. kopiowanie
      2. dołączanie
      3. zamiana wystąpień pod-stringu
  11. Ćwiczenia
    1. Wskaźniki powtórka
    2. Listy
      1. Zaprojektowanie prototypów funkcji i procedur dla podstawowych operacji na liście jednokierunkowej
      2. Wyszukiwanie (funkcja + ręczna symulacja działania)
      3. Wstawianie wraz z obsługą ewentualnych błędów wykonania (funkcja + ręczna symulacja działania)
      4. Kasowanie (procedura + ręczna symulacja)
  12. Ćwiczenia
    1. Listy
      1. Zaprojektowanie prototypów funkcji i procedur dla podstawowych operacji na posortowanej liście dwukierunkowej cyklicznej
      2. Wyszukiwanie (funkcja + ręczna symulacja działania)
      3. Wstawianie wraz z obsługą ewentualnych błędów wykonania (funkcja + ręczna symulacja działania)
      4. Kasowanie (procedura + ręczna symulacja)
    2. Drzewa BST
      1. Opis struktury
      2. Funkcja szukająca zadany element
  13. Ćwiczenia
    1. Drzewa BST
      1. Wstawianie do drzewa z powtórzeniami elementów
      2. Kasowanie z drzewa bez powtórzeń
    2. Rekurencja
      1. Algorytm szybkiego sortowania qsort
      2. Wypisywanie drzewa binarnego inorder
      3. Wyznaczanie wysokości drzewa
  14. Kolokwium II (na ćwiczeniach)
  15. Ćwiczenia
    1. Oddanie prac i omówienie wyników kolokwium
    2. Poprawa z kolokwium I
    3. Wystawienie ocen z Ćwiczeń
Powrót na stronę dydaktyki