Wstęp do programowania: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 61: Linia 61:
 
# Moduł 4 [[Ćwiczenia do Modułu 4]] (prostokaty i odcinki)
 
# Moduł 4 [[Ćwiczenia do Modułu 4]] (prostokaty i odcinki)
 
# Moduł 5 [[Ćwiczenia do Modułu 5]] (gramatyki)
 
# Moduł 5 [[Ćwiczenia do Modułu 5]] (gramatyki)
 +
# Moduł 6 [[Ćwiczenia do Modułu 6]] (logika Hoare'a)
 
[[Ćwiczenia do Modułu 0 | Ćwiczenia testowe i szablony zadań]]
 
[[Ćwiczenia do Modułu 0 | Ćwiczenia testowe i szablony zadań]]
  

Wersja z 16:54, 19 lip 2006

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

Ć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