Wstęp do programowania: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
|||
| Linia 13: | Linia 13: | ||
=== Zawartość === | === Zawartość === | ||
* Pojęcie algorytmu | * Pojęcie algorytmu | ||
** Historia powstania pojęcia algorytmu | ** Historia powstania pojęcia algorytmu | ||
** Algorytmy znane ze szkoły (Euklidesa, Hornera, rozwiązywanie równań liniowych i kwadratowych) | ** Algorytmy znane ze szkoły (Euklidesa, Hornera, rozwiązywanie równań liniowych i kwadratowych) | ||
* Języki formalne | * Języki formalne | ||
** Alfabet, składnia i semantyka | ** Alfabet, składnia i semantyka | ||
** Gramatyki bezkontekstowe, jako narzędzie definiowania składni | ** Gramatyki bezkontekstowe, jako narzędzie definiowania składni | ||
** Definicja semantyki przez interpretację wyrażeń poprawnych składniowo | ** Definicja semantyki przez interpretację wyrażeń poprawnych składniowo | ||
* Reprezentacja liczb w komputerze | * Reprezentacja liczb w komputerze | ||
** Stałe całkowite i rzeczywiste | ** Stałe całkowite i rzeczywiste | ||
** Reprezentacje binarne stało- i zmiennopozycyjne | ** Reprezentacje binarne stało- i zmiennopozycyjne | ||
** Systemy znak-moduł i uzupełnieniowy | ** Systemy znak-moduł i uzupełnieniowy | ||
| Linia 38: | Linia 38: | ||
** Własność stopu i metody jej dowodzenia | ** Własność stopu i metody jej dowodzenia | ||
* Typy danych | * Typy danych | ||
** tablice | ** tablice | ||
** rekordy | ** rekordy | ||
** zbiory | ** zbiory | ||
** pliki | ** pliki | ||
** typy wyliczeniowe i okrojone | ** typy wyliczeniowe i okrojone | ||
** typy wskaźnikowe | ** typy wskaźnikowe | ||
* Pliki | * Pliki | ||
| Linia 53: | Linia 53: | ||
* Miary złożoności algorytmów | * Miary złożoności algorytmów | ||
** Koszty algorytmu czasowy i pamięciowy, pesymistyczny i średni | ** Koszty algorytmu czasowy i pamięciowy, pesymistyczny i średni | ||
** Rozmiar danych | ** Rozmiar danych | ||
** Przykłady wyznaczania kosztów. | ** Przykłady wyznaczania kosztów. | ||
** Koszt zamortyzowany | ** Koszt zamortyzowany | ||
=== Literatura === | === Literatura === | ||
Wersja z 07:55, 15 cze 2006
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
