Wstęp do programowania

Z Studia Informatyczne
Wersja z dnia 07:53, 15 cze 2006 autorstwa Pch (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

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

  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