Wstęp do programowania - podejście imperatywne

Opis

Podstawowy przedmiot pierwszego roku studiów, mający zapoznać studentów z pojęciami algorytmu i programu oraz nauczyć ich projektowania, zapisywania, dowodzenia poprawności i uwzględniania złożoności algorytmów. Prezentacja technik programistycznych i struktur danych wykorzystywanych w programowaniu w małej i średniej skali.

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
Rekurencja:
- rekurencyjne wyrażanie pojęć
- zastosowania i implementacja
- dowodzenie poprawności procedur rekurencyjnych
Programowanie z nawrotami:
- przeszukiwanie pełnej przestrzeni stanów
- ucinanie rekursji
Metoda dziel i rządź:
- metoda inkrementacyjna
- podział binarny
Dynamiczne struktury danych:
- typy wskaźnikowe
- wskaźnikowa realizacja list
- podstawowe operacje na listach
- listy jednokierunkowe, dwukierunkowe i cykliczne
- atrapy i strażnicy
Liniowe struktury danych: stosy i kolejki:
- implementacja tablicowa i listowa
- implementacja grafu za pomocą list sąsiedztwa
- algorytmy DFS i BFS
Drzewa:
- implementacja drzew dowolnego rzędu
- drzewa binarne
- obiegi drzew
- konwersja wyrażeń z postaci infiksowej na prefiksową i postfiksową (ONP)
Programowanie zachłanne:
- algorytm Huffmana
Metoda spamiętywania:
- programowanie dynamiczne
- problem plecakowy
- optymalne mnożenie wielu macierzy

Literatura

S.Alagić, M.Arbib, Projektowanie programów poprawnych i dobrze zbudowanych, Wydawnictwa Naukowo - Techniczne 1982
L. Banachowski, A.Kreczmar, Elementy analizy algorytmów, Wydawnictwa Naukowo - Techniczne 1987
T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, Wprowadzenie do algorytmiki, Wydawnictwa Naukowo-Techniczne, Warszawa 2004.
D.E.Knuth, Sztuka programowania komputerów tom 3, Wydawnictwa Naukowo-Techniczne, Warszawa 2002.
N.Wirth, Wstęp do programowania systematycznego, Wydawnictwa Naukowo - Techniczne 1999.
N.Wirth, Algorytmy+Struktury danych=Programy, Wydawnictwa Naukowo-Techniczne, Warszawa 2001.

Informatyka MIMUW