Wstęp do programowania: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 42 wersji utworzonych przez 8 użytkowników)
Linia 7: Linia 7:
 
== Sylabus ==
 
== Sylabus ==
 
=== Autor ===
 
=== Autor ===
* Piotr Chrząstowski-Wachtel
+
* Piotr Chrząstowski-Wachtel — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
  
 
=== 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, jako narzędzie definiowania składni
+
** gramatyki bezkontekstowe jako narzędzie definiowania składni
** definicja semantyki przez interpretację wyrażeń poprawnych składniowo
+
** 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 - pojęcie zakresu, błędu zaokrągleń
+
** 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
 
** koszt zamortyzowany
 
** koszt zamortyzowany
 +
*Rekursja
  
 
=== Moduły ===
 
=== Moduły ===
# Moduł 1 [[Ćwiczenia do Modułu 1]] (tablice)
+
# [[Wstęp do programowania/Wstęp_do_algorytmów|Wstęp do algorytmów]] ([[Wstęp_do_programowania/Wstęp_do_algorytmów/Ćwiczenia|Ćwiczenia: prostokąty i odcinki]])
# Moduł 2 [[Ćwiczenia do Modułu 2]] (rekurencja)
+
# [[WDP_Wprowadzenie_do_programowania|Wprowadzenie do programowania]] ([[Wstęp_do_programowania_/_Ćwiczenia_2|Ćwiczenia: tablice]])
# Moduł 3 [[Ćwiczenia do Modułu 3]] (wyszukiwanie binarne)
+
# [[WDP_Gramatyki_–_definiowanie_składni_i_semantyki_wyrażeń|Gramatyki – definiowanie składni i semantyki wyrażeń]] ([[Wstęp_do_programowania_/_Ćwiczenia_3|Ćwiczenia]])
# Moduł 4 [[Ćwiczenia do Modułu 4]] (prostokaty i odcinki)
+
# [[WDP_Reprezentacja_liczb|Reprezentacja liczb]] ([[Wstęp_do_programowania/Reprezentacja_liczb/Ćwiczenia|Ćwiczenia]])
# Moduł 5 [[Ćwiczenia do Modułu 5]] (gramatyki)
+
# [[WDP_Składnia_i_semantyka_instrukcji|Składnia i semantyka instrukcji]] ([[Wstęp_do_programowania_/_Ćwiczenia_5|Ćwiczenia: wyszukiwanie binarne]])
# Moduł 6 [[Ćwiczenia do Modułu 6]] (logika Hoare'a)
+
# [[WDP_Dowodzenie_poprawności_programów|Dowodzenie poprawności programów]] ([[Wstęp_do_programowania_/_Ćwiczenia_6|Ćwiczenia]])
# Moduł 7 [[Ćwiczenia do Modułu 7]] (pliki)
+
# [[Wstęp do programowania/Pliki|Pliki]] ([[Wstęp_do_programowania/Pliki/Ćwiczenia|Ćwiczenia]])
[[Ćwiczenia do Modułu 0 | Ćwiczenia testowe i szablony zadań]]
+
# [[Pamięć dynamiczna]] ([[Wstęp_do_programowania_/_Ćwiczenia_8|Ćwiczenia: wskaźniki]])
 +
# [[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

  1. Wstęp do algorytmów (Ćwiczenia: prostokąty i odcinki)
  2. Wprowadzenie do programowania (Ćwiczenia: tablice)
  3. Gramatyki – definiowanie składni i semantyki wyrażeń (Ćwiczenia)
  4. Reprezentacja liczb (Ćwiczenia)
  5. Składnia i semantyka instrukcji (Ćwiczenia: wyszukiwanie binarne)
  6. Dowodzenie poprawności programów (Ćwiczenia)
  7. Pliki (Ćwiczenia)
  8. Pamięć dynamiczna (Ćwiczenia: wskaźniki)
  9. Procedury i funkcje (Ćwiczenia: procedury i funkcje)
  10. Rekursja (Ćwiczenia)

Literatura

  1. Wstęp do programowania systematycznego, N.Wirth, Wydawnictwa Naukowo - Techniczne 1999.
  2. Elementy analizy algorytmów, L. Banachowski, A.Kreczmar, Wydawnictwa Naukowo - Techniczne 1987.
  3. Projektowanie programów poprawnych i dobrze zbudowanych, S.Alagić, M.Arbib, Wydawnictwa Naukowo - Techniczne 1982.