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 — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

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
  • definiowanie 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 i 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
• Rekursja

Moduły

1. Wstęp do algorytmów (Ćwiczenia: prostokąty i odcinki)
2. Wprowadzenie do programowania (Ćwiczenia: tablice)
3. Gramatyki – definiowanie składni i semantyki wyrażeń (Ćwiczenia)
4. Reprezentacja liczb (Ćwiczenia)
5. Składnia i semantyka instrukcji (Ćwiczenia: wyszukiwanie binarne)
6. Dowodzenie poprawności programów (Ćwiczenia)
7. Pliki (Ćwiczenia)
8. Pamięć dynamiczna (Ćwiczenia: wskaźniki)
9. Rekursja (Ćwiczenia)

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