MIMINF:Wstęp do programowania

Forma zajęć

Wykład (60 godzin) + ćwiczenia (60 godzin) + laboratorium (30 godzin)

Opis

Podstawowy przedmiot studiów, mający zapoznać studentów z pojęciami algorytmu i programu, jak i nauczyć 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

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