Informacje dla kandydatów

Wstęp do informatyki i programowania

Szczególny nacisk położony jest na algorytmikę jako sztukę projektowania poprawnych algorytmów. Również uczymy się pisania prostych programów w języku ANSI C.

Nie zajmujemy się aplikacjami okienkowymi (na to przyjdzie właściwy czas). Wszystkie pisane aplikacje będą tak zwanymi aplikacjami konsolowymi, będą polegały na oprogramowaniu jednego algorytmu lub rozwiązania konkretnego zadania, korzystać będą tylko ze standardowych bibliotek języka C.

Wszystkie rozważane algorytmy będziemy analizowali na tyle dokładnie na ile pozwolą nam posiadane przez was na pierwszym roku studiów środki. Na przykład, o funkcji NWD (jest to implementacja algorytmu Euklidesa) znajdującej się obok tego tekstu udowodnimy, że liczy największy wspólny dzielnik podanych argumentów, oraz pokażemy, że algorytm ten działa w czasie O(min{log(a), log(b)}). Dokładniejszą jego analizę zostawimy sobie na później, gdyż na pierwszym semestrze nie będziecie jeszcze dysponować potrzebnymi narzędziami.

Drugi z kodów znajdujących się na tej stronie służy do zliczania liczby zapalonych bitów w binarnej reprezentacji liczby a.

Na ćwiczeniach będziemy pisać proste programy w pseudokodzie a następnie przeanalizujemy ich poprawność.

Na wykładzie będziemy omawiali, między innymi, następujące algorytmy:
  1. sortowanie przez wstawianie
  2. wyszukiwanie binarne
  3. problem wież z Hanoi
  4. problem Hetmanów
  5. algorytm Karatsuby szybkiego mnożenia długich liczb
  6. algorytm szybkiego mnożenia macierzy
  7. sortowanie przez scalanie
  8. problem najdłuższego wspólnego podciągu

unsigned int NWD(unsigned int a, 
                 unsigned int b)
{
  unsigned int r;
  r = a%b;
  while (r) 
  { 
    a = b;
    b = r;
    r = a%b;
  }
  return b;    
} 
int BC(unsigned int a)
{
  int c=0;
  while (a)
  { 
    a &= a-1;
    c++;
  }
  return c;
}
Stacks Image 362
Na wykładzie nauczysz się również wielu innych rzeczy: notacji \(f = O(g)\), \(f = o(g)\), rozwiązywania równań rekurencyjnych postaci \(a_{n+1} = A \cdot a_n + B\), pokazywania zbieżności pętli, korzystania z niezmienników, analizy złożoności obliczeniowej prostych programów, poznasz Master Theorem. Poznasz podstawowe techniki programowania (rekursja, "dziel i rządź", programowanie dynamiczne), nauczysz się działać bezpośrednio na bitach, dowiesz się jak są reprezentowane liczby całkowite. Dowiesz się również, że istnieją ograniczenia na metody algorytmiczne, czyli, że istnieją problemy nierozstrzygalne (problem stopu). Omówimy też podstawowe zasady poprawnego stylu programowania (czy wiesz co to jest zasada KISS?) oraz dokumentowania kodu.

Dodatkowe materiały

Katedra Informatyki
Politechnika Wrocławska
Wydział Podstawowych Problemów Techniki