Wstęp do programowania: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 56: | Linia 56: | ||
=== Moduły === | === Moduły === | ||
# [[WDP_Wstęp_do_algorytmów|Wstęp do algorytmów]] | # [[WDP_Wstęp_do_algorytmów|Wstęp do algorytmów]] ([[Ćwiczenia do Modułu 4|Ćwiczenia: prostokąty i odcinki]]) | ||
# [[WDP_Wprowadzenie_do_programowania|Wprowadzenie do programowania]] | # [[WDP_Wprowadzenie_do_programowania|Wprowadzenie do programowania]] ([[Ćwiczenia do Modułu 2|Ćwiczenia: tablice]]) | ||
# [[WDP_Gramatyki_–_definiowanie_składni_i_semantyki_wyrażeń|Gramatyki – definiowanie składni i semantyki wyrażeń]] [[Ćwiczenia do Modułu 3]] | # [[WDP_Gramatyki_–_definiowanie_składni_i_semantyki_wyrażeń|Gramatyki – definiowanie składni i semantyki wyrażeń]] ([[Ćwiczenia do Modułu 3|Ćwiczenia]]) | ||
# [[WDP_Reprezentacja_liczb|Reprezentacja liczb]] [[Ćwiczenia | # [[WDP_Reprezentacja_liczb|Reprezentacja liczb]] ([[WDP_Reprezentacja_liczb/Ćwiczenia_4|Ćwiczenia]]) | ||
# [[WDP_Składnia_i_semantyka_instrukcji|Składnia i semantyka instrukcji]] [[Ćwiczenia do Modułu 5]] | # [[WDP_Składnia_i_semantyka_instrukcji|Składnia i semantyka instrukcji]] ([[Ćwiczenia do Modułu 5|Ćwiczenia: wyszukiwanie binarne]]) | ||
# [[WDP_Dowodzenie_poprawności_programów|Dowodzenie poprawności programów]] [[Ćwiczenia do Modułu 6]] | # [[WDP_Dowodzenie_poprawności_programów|Dowodzenie poprawności programów]] ([[Ćwiczenia do Modułu 6|Ćwiczenia]]) | ||
# Moduł 7 [[Ćwiczenia do Modułu 7]] | # Moduł 7 ([[Ćwiczenia do Modułu 7|Ćwiczenia: pliki]]) | ||
# Moduł 8 [[Ćwiczenia do Modułu 8]] | # Moduł 8 ([[Ćwiczenia do Modułu 8|Ćwiczenia: wskaźniki]]) | ||
# Moduł 9 | # Moduł 9 | ||
[[Ćwiczenia do Modułu 0 | Ćwiczenia testowe i szablony zadań]] | [[Ćwiczenia do Modułu 0 | Ćwiczenia testowe i szablony zadań]] | ||
Wersja z 20:39, 28 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 (Ćwiczenia: prostokąty i odcinki)
- Wprowadzenie do programowania (Ćwiczenia: tablice)
- Gramatyki – definiowanie składni i semantyki wyrażeń (Ćwiczenia)
- Reprezentacja liczb (Ćwiczenia)
- Składnia i semantyka instrukcji (Ćwiczenia: wyszukiwanie binarne)
- Dowodzenie poprawności programów (Ćwiczenia)
- Moduł 7 (Ćwiczenia: pliki)
- Moduł 8 (Ćwiczenia: wskaźniki)
- Moduł 9
Ć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
