Wstęp do programowania

obowiązkowe

Podstawowy przedmiot studiów wprowadzający w dziedzinę informatyki, 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.

• Pojęcie algorytmu:

◦ historia powstania pojęcia algorytmu

◦ przykłady algorytmów (Euklidesa, Archimedesa, Hornera, rozwiązywanie równań liniowych i kwadratowych)

◦ pojęcie dziedziny algorytmicznej

• Podstawy języka programowania:

◦ notacja do opisu składni języka (np. gramatyki bezkontekstowe lub BNF),

◦ pojęcie składni i semantyki

◦ dziedzina algorytmiczna:

▪ wyrażenia arytmetyczne (liczby całkowite i zmiennopozycyjne)

▪ wyrażenia logiczne

▪ znaki i napisy

◦ zmienne, ich typ, instrukcja przypisania

◦ definiowanie funkcji (bez rekurencji):

▪ parametry

▪ wartość przekazywana i typ void

▪ wywoływanie funkcji

▪ zmienne lokalne

◦ instrukcja warunkowa,

◦ pętla while

◦ pętla for

◦ instrukcja wyboru

◦ znaki i napisy

◦ wczytywanie i wypisywanie

◦ instrukcja pusta

◦ reprezentacja liczb całkowitych

◦ reprezentacja liczb zmiennopozycyjnych, pojęcie zakresu i błędów zaokrągleń

• Dekompozycja problemu i weryfikacja programów:

◦ specyfikacja problemu, warunek początkowy i końcowy,

◦ częściowa poprawność i własność stopu,

◦ asercje

◦ formuły Hoare’a

◦ niezmienniki pętli

◦ własność stopu i metody jej dowodzenia

◦ uzasadnianie poprawności programów

◦ przykłady dekompozycji problemów i weryfikacji programów

• Typy danych:

◦ tablice,

◦ struktury,

◦ unie,

◦ deklaracje typów

◦ reguły zgodności typów

• Pliki:

◦ nośniki pamięci

◦ pliki tekstowe

◦ mechanizm buforowania

◦ standardowe wejście i wyjście jako strumienie

• Przydatne narzędzia i technikalia

◦ makrodefinicje i pre-processing

◦ definicje stałych

◦ klasy: typy obiektów z ograniczonym zestawem metod operujących na nich

◦ wywoływanie metod obiektu

◦ metody wywoływane implicite: konstruktory, destruktory, kopiowanie, rzutowanie typów

◦ przeładowanie operatorów

◦ typy wyliczeniowe

◦ przydatne typy danych

• Typy wskaźnikowe:

◦ pojęcie wskaźnika, dereferencja,

◦ przekazywanie argumentów (i wyników) przez wartość, wskaźnik i referencję

◦ zmienne globalne i lokalne,

◦ pamięć alokowana dynamicznie,

◦ smart pointers -- wskaźniki unikalne i współdzielone

• Modularyzacja i bariery abstrakcji

◦ pliki nagłówkowe i implementacja

• Rekurencja:

◦ rekurencja i jej sposób implementacji

◦ rekurencyjne wyrażanie problemów

◦ weryfikacja programów rekurencyjnych

• Analiza złożoności algorytmów:

◦ rachunek rzędów funkcji

◦ koszty algorytmu: czasowy i pamięciowy, pesymistyczny i średni

◦ rozmiar danych

◦ analiza programów rekurencyjnych

◦ koszt zamortyzowany

◦ przykłady wyznaczania kosztów

• Metoda "dziel i rządź":

◦ metoda inkrementacyjna

◦ podział binarny, w tym wyszukiwanie binarne

◦ przykłady -- algorytmy sortowania

• Dynamiczne struktury danych:

◦ typy wskaźnikowe

◦ wskaźnikowa realizacja list

◦ podstawowe operacje na listach

◦ listy jednokierunkowe, dwukierunkowe i cykliczne

◦ stosy i kolejki

◦ atrapy i strażnicy

•  Drzewa:

◦ drzewa binarne, BST

◦ implementacja drzew dowolnego rzędu

◦ obiegi drzew

• Przydatne biblioteczne struktury danych:

◦ słowniki (mapy)

◦ tablice haszujące

◦ zbiory

◦ kolejki

◦ stosy

• Programowanie z nawrotami:

◦ przeszukiwanie pełnej przestrzeni stanów

◦ heurystyki przyspieszające

◦ ucinanie rekursji

• Programowanie dynamiczne

◦ metoda spamiętywania

◦ tablicowanie

◦ programowanie dynamiczne na drzewach

• Programowanie zachłanne:

◦ algorytm Huffmana

◦ inne przykłady

• Przeszukiwanie grafów:

◦ implementacja macierzowa i listowa grafów

◦ przeszukiwanie wszerz

◦ przeszukiwanie w głąb

◦ algorytm Floyda-Warshalla

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. W. Kernighan, Dennis M. Ritchie, Język ANSI C. Programowanie. Wydanie II, Wydawnictwo Helion, Gliwice 2010

4. N.Wirth, Wstęp do programowania systematycznego, Wydawnictwa Naukowo - Techniczne 1999.

5. N.Wirth, Algorytmy+Struktury danych=Programy, Wydawnictwa Naukowo-Techniczne, Warszawa 2001.

Wiedza: student zna i rozumie:

* teoretyczne podstawy z zakresu programowania, algorytmów i złożoności, architektury systemów komputerowych, systemów operacyjnych, technologii sieciowych, wybranych języków i paradygmatów programowania, baz danych, inżynierii oprogramowania (K_W02);

* w zaawansowanym stopniu podstawowe konstrukcje programistyczne (przypisanie, instrukcje sterujące, wywoływanie podprogramów i przekazywanie parametrów, deklaracje i typy, mechanizmy abstrakcji) oraz pojęcia składni i semantyki języków programowania (K_W03);

* podstawowe metody projektowania, analizowania i programowania algorytmów (projektowanie strukturalne, rekurencja, metoda dziel i rządź, programowanie z nawrotami, poprawność, metoda niezmienników, złożoność obliczeniowa) (K_W04);

* podstawowe struktury danych i wykonywane na nich operacje (reprezentacja danych liczbowych, arytmetyka i błędy zaokrągleń, tablice, napisy, zbiory, struktury, pliki, wskaźniki i referencje, struktury wskaźnikowe, listy, stosy, kolejki, drzewa i grafy) (K_W05).

Umiejętności: student potrafi:

* zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania związanych z informatyką zadań (K_U01);

* czytać ze zrozumieniem programy zapisane w językach programowania bazujących na wybranych paradygmatach (K_U06);

* posługiwać się przyjętymi formatami reprezentacji różnego rodzaju danych stosownie do sytuacji (liczby, tablice, tekst) pamiętając o ich ograniczeniach, np. związanych z arytmetyką komputera (K_U08).

Kompetencje społeczne: student jest gotów do:

* krytycznej oceny posiadanej wiedzy i odbieranych treści (K_K01);

* pracy z poszanowaniem uczciwości intelektualnej w działaniach własnych i innych osób; przestrzegania zasad etyki zawodowej i wymagania tego od innych oraz dbałości o dorobek i tradycje zawodu informatyka (K_K02);

* uznawania znaczenia wiedzy w rozwiązywaniu problemów poznawczych i praktycznych oraz wyszukiwania informacji w literaturze oraz zasięgania opinii ekspertów (K_K03).