Wstęp do programowania

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Opis

Podstawowy przedmiot pierwszego semestru studiów, mający zapoznać studentów z pojęciami algorytmu i programu. Celem zajęć jest nauczenie projektowania, zapisywania, dowodzenia poprawności i uwzględniania złożoności algorytmów.

Sylabus

Autor

• Piotr Chrząstowski-Wachtel

Zawartość

• Pojęcie algorytmu
  • historia powstania pojęcia algorytmu
  • algorytmy znane ze szkoły (Euklidesa, Hornera, rozwiązywanie równań liniowych i kwadratowych)
• Języki formalne
  • alfabet, składnia i semantyka
  • gramatyki bezkontekstowe, jako narzędzie definiowania składni
  • definicja semantyki przez interpretację wyrażeń poprawnych składniowo
• Reprezentacja liczb w komputerze
  • stałe całkowite i rzeczywiste
  • reprezentacje binarne stało- i zmiennopozycyjne
  • systemy znak-moduł i uzupełnieniowy
  • rachunek zmiennopozycyjny - pojęcie zakresu, błędu zaokrągleń
• Zmienne i wyrażenia
  • typ zmiennej i wartościowanie zmiennych
  • wyrażenia arytmetyczne i logiczne: składnia i semantyka
• Instrukcje while-programów
  • pusta, przypisania, warunkowa, iteracji, wyboru, czytania, pisania, wywołania procedury
  • składnia i semantyka powyższych instrukcji
  • obliczenia skończone i nieskończone
  • błędy obliczeń
  • przykłady algorytmów
• Asercje w programach i niezmienniki pętli
  • formuły Hoare'a
  • uzasadnianie poprawności programów
  • własność stopu i metody jej dowodzenia
• Typy danych
  • tablice
  • rekordy
  • zbiory
  • pliki
  • typy wyliczeniowe i okrojone
  • typy wskaźnikowe
• Pliki
  • pliki o dostępie bezpośrednim
  • pliki tekstowe
• Funkcje i procedury
  • składnia i semantyka
  • sposoby przekazywania parametrów: przez wartość i przez zmienną
  • widoczność zmiennych w zagnieżdżonych procedurach
• Miary złożoności algorytmów
  • koszty algorytmu czasowy i pamięciowy, pesymistyczny i średni
  • rozmiar danych
  • przykłady wyznaczania kosztów
  • koszt zamortyzowany

Moduły

1. Wstęp do algorytmów Ćwiczenia do Modułu 1 (tablice)
2. Moduł 2 Ćwiczenia do Modułu 2 (rekurencja)
3. Moduł 3 Ćwiczenia do Modułu 3 (wyszukiwanie binarne)
4. Moduł 4 Ćwiczenia do Modułu 4 (prostokaty i odcinki)
5. Moduł 5 Ćwiczenia do Modułu 5 (gramatyki)
6. Moduł 6 Ćwiczenia do Modułu 6 (logika Hoare'a)
7. Moduł 7 Ćwiczenia do Modułu 7 (pliki)

Ćwiczenia testowe i szablony zadań

Literatura

1. Wstęp do programowania systematycznego, N.Wirth, Wydawnictwa Naukowo - Techniczne 1999.
2. Elementy analizy algorytmów, L. Banachowski, A.Kreczmar, Wydawnictwa Naukowo - Techniczne 1987
3. Projektowanie programów poprawnych i dobrze zbudowanych, S.Alagić, M.Arbib, Wydawnictwa Naukowo - Techniczne 1982