Wstęp do programowania: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
(→Moduły) |
m (→Literatura) |
||
| (Nie pokazano 3 wersji utworzonych przez 2 użytkowników) | |||
| Linia 60: | Linia 60: | ||
# [[WDP_Wprowadzenie_do_programowania|Wprowadzenie do programowania]] ([[Wstęp_do_programowania_/_Ćwiczenia_2|Ćwiczenia: tablice]]) | # [[WDP_Wprowadzenie_do_programowania|Wprowadzenie do programowania]] ([[Wstęp_do_programowania_/_Ćwiczenia_2|Ćwiczenia: tablice]]) | ||
# [[WDP_Gramatyki_–_definiowanie_składni_i_semantyki_wyrażeń|Gramatyki – definiowanie składni i semantyki wyrażeń]] ([[Wstęp_do_programowania_/_Ćwiczenia_3|Ćwiczenia]]) | # [[WDP_Gramatyki_–_definiowanie_składni_i_semantyki_wyrażeń|Gramatyki – definiowanie składni i semantyki wyrażeń]] ([[Wstęp_do_programowania_/_Ćwiczenia_3|Ćwiczenia]]) | ||
# [[WDP_Reprezentacja_liczb|Reprezentacja liczb]] ([[ | # [[WDP_Reprezentacja_liczb|Reprezentacja liczb]] ([[Wstęp_do_programowania/Reprezentacja_liczb/Ćwiczenia|Ćwiczenia]]) | ||
# [[WDP_Składnia_i_semantyka_instrukcji|Składnia i semantyka instrukcji]] ([[Wstęp_do_programowania_/_Ćwiczenia_5|Ćwiczenia: wyszukiwanie binarne]]) | # [[WDP_Składnia_i_semantyka_instrukcji|Składnia i semantyka instrukcji]] ([[Wstęp_do_programowania_/_Ćwiczenia_5|Ćwiczenia: wyszukiwanie binarne]]) | ||
# [[WDP_Dowodzenie_poprawności_programów|Dowodzenie poprawności programów]] ([[Wstęp_do_programowania_/_Ćwiczenia_6|Ćwiczenia]]) | # [[WDP_Dowodzenie_poprawności_programów|Dowodzenie poprawności programów]] ([[Wstęp_do_programowania_/_Ćwiczenia_6|Ćwiczenia]]) | ||
# [[Wstęp do programowania/Pliki|Pliki]] ([[Wstęp_do_programowania/Pliki/Ćwiczenia|Ćwiczenia]]) | # [[Wstęp do programowania/Pliki|Pliki]] ([[Wstęp_do_programowania/Pliki/Ćwiczenia|Ćwiczenia]]) | ||
# [[Pamięć dynamiczna]] ([[Wstęp_do_programowania_/_Ćwiczenia_8|Ćwiczenia: wskaźniki]]) | # [[Pamięć dynamiczna]] ([[Wstęp_do_programowania_/_Ćwiczenia_8|Ćwiczenia: wskaźniki]]) | ||
# [[Wstęp do programowania/Rekursja|Rekursja]] ([[ | # [[Procedury i funkcje]] ([[Wstęp_do_programowania_/_Ćwiczenia_9|Ćwiczenia: procedury i funkcje]]) | ||
# [[Wstęp do programowania/Rekursja|Rekursja]] ([[Wstęp do programowania/Rekursja/Ćwiczenia|Ćwiczenia]]) | |||
=== Literatura === | === Literatura === | ||
# ''Wstęp do programowania systematycznego'', N.Wirth, Wydawnictwa Naukowo - Techniczne 1999. | # ''Wstęp do programowania systematycznego'', N.Wirth, Wydawnictwa Naukowo - Techniczne 1999. | ||
# ''Elementy analizy algorytmów'', L. Banachowski, A.Kreczmar, Wydawnictwa Naukowo - Techniczne 1987 | # ''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 | # ''Projektowanie programów poprawnych i dobrze zbudowanych'', S.Alagić, M.Arbib, Wydawnictwa Naukowo - Techniczne 1982. | ||
Aktualna wersja na dzień 19:18, 15 lis 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
- Rekursja
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)
- Pliki (Ćwiczenia)
- Pamięć dynamiczna (Ćwiczenia: wskaźniki)
- Procedury i funkcje (Ćwiczenia: procedury i funkcje)
- Rekursja (Ćwiczenia)
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.
