MIMINF:Wstęp do programowania

From Studia Informatyczne

Spis treści

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 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

  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.