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ęciem 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

Wymagania wstępne

• brak

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. Moduł 1 Ćwiczenia do Modułu 1 (zadania na tablice)

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