Wstęp do programowania
Z Studia Informatyczne
Forma zajęć
Wykład (30 godzin) + laboratorium (30 godzin)
Opis
Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych.
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.
Literatura
- Wstęp do programowania systematycznego, N.Wirth, Wydawnictwa Naukowo - Techniczne 1999.
- Elementy analizy algorytmów, L. Banachowski, A.Kreczmar, Wydawnictwa Naukowo - Techniczne 1987
- Projektowanie programów poprawnych i dobrze zbudowanych', S.Alagić, M.Arbib, Wydawnictwa Naukowo - Techniczne 1982
