Wstęp do programowania

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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. Procedury i funkcje (Ćwiczenia: procedury i funkcje)
  10. 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.