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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 56: Linia 56:
  
 
=== Moduły ===
 
=== Moduły ===
# Wstęp do algorytmów [[Ćwiczenia do Modułu 1]] (tablice)
+
# [[WDP_Wstep_do_algorytmow|Wstęp do algorytmów]] [[Ćwiczenia do Modułu 1]] (tablice)
 
# Moduł 2 [[Ćwiczenia do Modułu 2]] (rekurencja)
 
# Moduł 2 [[Ćwiczenia do Modułu 2]] (rekurencja)
 
# Moduł 3 [[Ćwiczenia do Modułu 3]] (wyszukiwanie binarne)
 
# Moduł 3 [[Ćwiczenia do Modułu 3]] (wyszukiwanie binarne)

Wersja z 08:00, 21 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. Wstęp do algorytmów Ćwiczenia do Modułu 1 (tablice)
  2. Moduł 2 Ćwiczenia do Modułu 2 (rekurencja)
  3. Moduł 3 Ćwiczenia do Modułu 3 (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)
  7. Moduł 7 Ćwiczenia do Modułu 7 (pliki)

Ć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