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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Aneczka (dyskusja | edycje)
700 edycji
Dorota (dyskusja | edycje)
376 edycji
 
(Nie pokazano 16 wersji utworzonych przez 5 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 ===
# [[WDP_Wstęp_do_algorytmów|Wstęp do algorytmów]]
# [[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]])
# [[WDP_Wprowadzenie_do_programowania|Wprowadzenie do programowania]] [[Ćwiczenia do Modułu 2]] (rekurencja, 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ń]] [[Ćwiczenia do Modułu 3]] (gramatyki)
# [[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]] [[Ćwiczenia do Modułu 4]] (prostokaty i odcinki)
# [[WDP_Reprezentacja_liczb|Reprezentacja liczb]] ([[Wstęp_do_programowania/Reprezentacja_liczb/Ćwiczenia|Ćwiczenia]])
# [[WDP_Składnia_i_semantyka_instrukcji|Składnia i semantyka instrukcji]] [[Ćwiczenia do Modułu 5]] (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]] [[Ć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]])
# Moduł 8 [[Ćwiczenia do Modułu 8]] (wskaźniki)
# [[Pamięć dynamiczna]] ([[Wstęp_do_programowania_/_Ćwiczenia_8|Ćwiczenia: wskaźniki]])
# Moduł 9 [[Ćwiczenia do Modułu 9]] (binaria)
# [[Procedury i funkcje]] ([[Wstęp_do_programowania_/_Ćwiczenia_9|Ćwiczenia: procedury i funkcje]])
[[Ćwiczenia do Modułu 0 | Ćwiczenia testowe i szablony zadań]]
# [[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.
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Wstęp_do_programowania&oldid=66048”