Wstęp do programowania: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania (→Moduły) |
(→Moduły) |
||
| Linia 56: | Linia 56: | ||
=== Moduły === | === Moduły === | ||
| − | # Moduł 1 [[Ćwiczenia do Modułu 1]] ( | + | # Moduł 1 [[Ćwiczenia do Modułu 1]] (tablice) |
| − | # Moduł 2 [[Ćwiczenia do Modułu 2]] ( | + | # Moduł 2 [[Ćwiczenia do Modułu 2]] (rekurencja) |
| − | # Moduł 3 [[Ćwiczenia do Modułu 3]] ( | + | # Moduł 3 [[Ćwiczenia do Modułu 3]] (wyszukiwanie binarne) |
# 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) | # Moduł 6 [[Ćwiczenia do Modułu 6]] (logika Hoare'a) | ||
| + | # Moduł 7 [[Ćwiczenia do Modułu 7]] (pliki) | ||
[[Ćwiczenia do Modułu 0 | Ćwiczenia testowe i szablony zadań]] | [[Ćwiczenia do Modułu 0 | Ćwiczenia testowe i szablony zadań]] | ||
Wersja z 17:32, 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
- Moduł 1 Ćwiczenia do Modułu 1 (tablice)
- Moduł 2 Ćwiczenia do Modułu 2 (rekurencja)
- Moduł 3 Ćwiczenia do Modułu 3 (wyszukiwanie binarne)
- Moduł 4 Ćwiczenia do Modułu 4 (prostokaty i odcinki)
- Moduł 5 Ćwiczenia do Modułu 5 (gramatyki)
- Moduł 6 Ćwiczenia do Modułu 6 (logika Hoare'a)
- Moduł 7 Ćwiczenia do Modułu 7 (pliki)
Ćwiczenia testowe i szablony zadań
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
