Zofia.Kruczkiewicz@pwr.wroc.pl    
Politechnika Wrocławska 
Katedra Informatyki Technicznej (K-9) 
Zespół Inżynierii Oprogramowania i
Inteligencji Obliczeniowej
 
Aktualności  Dydaktyka  Kontakt 
 
   
  strona główna dydaktyka Języki Programowania 1 - INE2022
 
  menu
  materiały dydaktyczne
  opis kursu
  informacje dodatkowe
 

  ostatnia aktualizacja
17.10.2017 r.
 

 
  autor kursu
dr inż. Zofia Kruczkiewicz
 
  zespół dydaktyczny
dr inż. Tadeusz Jeleniewski
dr inż. Marek Piasecki
dr inż. Paweł Rogaliński
dr inż. Robert Wójcik
 
  tygodniowy wymiar godzin
wykład - 2 godziny
laboratorium - 2 godziny
 
  wymagania wstępne
Informatyka 1 - INE1007
Informatyka 2 - INE1012
Projektowanie efektywnych algorytmów - INE2044
 
  opis kursu
Kurs dostarcza niezbędnej wiedzy do budowy algorytmów i struktur danych. Decyzje dotyczące struktur danych powinny być dostosowane do wybranych algorytmów, natomiast wybór algorytmu powinien wynikać z zastosowanych struktur danych. W programie nauczania zastosowano metody formalne wspomagające specyfikację elementów programów, weryfikację kodu, oszacowanie złożoności strukturalnej i obliczeniowej. Struktury danych i operacje specyfikuje się za pomocą Abstrakcyjnych Typów Danych (ADT) i języka teorii mnogości. W praktyce kładzie się nacisk na weryfikację kodu wspomaganą formalnym udowodnieniem jego poprawności. Pomiaru złożoności strukturalnej dokonuje się za pomocą metryk. W ramach kursu zaprezentowano algorytmy wewnętrznego sortowania i wyszukiwania oraz nieuporządkowane i uporządkowane rekurencyjne struktury danych wraz z podstawowymi operacjami. Podano implementację przedstawionych algorytmów i struktur danych w języku C++. W ramach laboratorium słuchacze kursu mogą praktycznie poznać metody implementacji programów w języku C++ wspomagane metodami formalnymi.
 
  zawartość tematyczna kursu
wykład
  1. Rola metod formalnych w tworzeniu oprogramowania - 2h
  2. Metoda specyfikacja elementów programu za pomocą Abstrakcyjnych Typów Danych (ADT) - 1h
  3. Programy wieloplikowe w C++ wspomagające specyfikację ADT - 1h
  4. Zastosowanie ADT do specyfikacji operacji na statycznych i dynamicznych tablic struktur oraz ich wskaźników - 4h
  5. Dowody poprawności programów przetwarzających tablice - 2h
  6. Ocena złożoności strukturalnej programów przetwarzających tablice, zastosowanie metryk - 2h
  7. Oszacowanie wydajności programów na przykładzie przetwarzania tablic - 2h
  8. Zastosowanie ADT do specyfikacji operacji na nieuporządkowanych i uporządkowanych rekurencyjnych strukturach danych - 4h
  9. Dowody poprawności programów przetwarzających rekurencyjne struktury danych - 2h
  10. Ocena złożoności strukturalnej programów przetwarzających rekurencyjne struktury danych - 2h
  11. Oszacowanie wydajności programów przetwarzających rekurencyjne struktury danych - 2h
laboratorium

W ramach zajęć laboratoryjnych wykonuje się programy wieloplikowe przetwarzające:
  1. statyczne i dynamiczne tablice struktur oraz wskaźników na struktury
  2. nieuporządkowane i uporządkowane rekurencyjne struktury danych (stosy, kolejki, listy, drzewa, grafy)
Kładzie się nacisk na proces tworzenia efektywnych programów z wykorzystaniem metod formalnych: do specyfikacji, weryfikacji, badania poprawności oraz oszacowania złożoności strukturalnej i obliczeniowej.
 
 
m.kruczkiewicz@floweb.pl