Wstęp do programowania: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m →Autor |
|||
| Linia 10: | Linia 10: | ||
=== 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 | ** gramatyki bezkontekstowe jako narzędzie definiowania składni | ||
** | ** definiowanie 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 | ||
** rachunek zmiennopozycyjny | ** rachunek zmiennopozycyjny — pojęcie zakresu i błędu zaokrągleń | ||
* Zmienne i wyrażenia | * Zmienne i wyrażenia: | ||
** typ zmiennej i wartościowanie zmiennych | ** typ zmiennej i wartościowanie zmiennych | ||
** wyrażenia arytmetyczne i logiczne: składnia i semantyka | ** 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 | ** składnia i semantyka powyższych instrukcji | ||
| Linia 31: | Linia 31: | ||
** błędy obliczeń | ** błędy obliczeń | ||
** przykłady algorytmów | ** przykłady algorytmów | ||
* Asercje w programach i niezmienniki pętli | * Asercje w programach i niezmienniki pętli: | ||
** formuły Hoare'a | ** formuły Hoare'a | ||
** uzasadnianie poprawności programów | ** uzasadnianie poprawności programów | ||
** własność stopu i metody jej dowodzenia | ** własność stopu i metody jej dowodzenia | ||
* Typy danych | * Typy danych: | ||
** tablice | ** tablice | ||
** rekordy | ** rekordy | ||
| Linia 42: | Linia 42: | ||
** typy wyliczeniowe i okrojone | ** typy wyliczeniowe i okrojone | ||
** typy wskaźnikowe | ** typy wskaźnikowe | ||
* Pliki | * Pliki: | ||
** pliki o dostępie bezpośrednim | ** pliki o dostępie bezpośrednim | ||
** pliki tekstowe | ** pliki tekstowe | ||
* Funkcje i procedury | * Funkcje i procedury: | ||
** składnia i semantyka | ** składnia i semantyka | ||
** sposoby przekazywania parametrów: przez wartość i przez zmienną | ** sposoby przekazywania parametrów: przez wartość i przez zmienną | ||
** widoczność zmiennych w zagnieżdżonych procedurach | ** 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 | ** koszty algorytmu: czasowy i pamięciowy, pesymistyczny i średni | ||
** rozmiar danych | ** rozmiar danych | ||
** przykłady wyznaczania kosztów | ** przykłady wyznaczania kosztów | ||
Wersja z 11:26, 27 wrz 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 — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
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
- definiowanie 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 i 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
- Wstęp do algorytmów
- Wprowadzenie do programowania Ćwiczenia do Modułu 2 (rekurencja, tablice)
- Gramatyki – definiowanie składni i semantyki wyrażeń Ćwiczenia do Modułu 3 (gramatyki)
- Reprezentacja liczb Ćwiczenia do Modułu 4 (prostokaty i odcinki)
- Składnia i semantyka instrukcji Ćwiczenia do Modułu 5 (wyszukiwanie binarne)
- Dowodzenie poprawności programów Ćwiczenia do Modułu 6 (logika Hoare'a)
- Moduł 7 Ćwiczenia do Modułu 7 (pliki)
- Moduł 8 Ćwiczenia do Modułu 8 (wskaźniki)
- Moduł 9 Ćwiczenia do Modułu 9 (binaria)
Ć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
