Wstęp do programowania: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m Poprawki edytorskie |
m Poprawki edytorskie |
||
| Linia 14: | Linia 14: | ||
=== Zawartość === | === Zawartość === | ||
* Pojęcie algorytmu | * 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 | * 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 | * 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 | * Zmienne i wyrażenia | ||
** | ** typ zmiennej i wartościowanie zmiennych | ||
** | ** wyrażenia arytmetyczne i logiczne: składnia i semantyka | ||
* Instrukcje while-programów | * Instrukcje while-programów | ||
** pusta, przypisania, warunkowa, iteracji, wyboru, czytania, pisania, wywołania procedury | ** 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 | * 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 | * Typy danych | ||
** tablice | ** tablice | ||
| Linia 49: | Linia 49: | ||
** pliki tekstowe | ** pliki tekstowe | ||
* Funkcje i procedury | * 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 | * 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ły === | ||
Wersja z 07:18, 7 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
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
Moduły
- Moduł 1 Ćwiczenia do Modułu 1 (zadania na tablice)
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
