Personal tools

Wstęp do programowania

From Studia Informatyczne

Spis treści

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.