Wstęp do programowania

* Pojęcie algorytmu:

o historia powstania pojęcia algorytmu

o algorytmy znane ze szkoły (Euklidesa, Hornera, rozwiązywanie równań liniowych i kwadratowych)

* Języki formalne:

o alfabet, składnia i semantyka

o gramatyki bezkontekstowe jako narzędzie definiowania składni

o definiowanie semantyki przez interpretację wyrażeń poprawnych składniowo

* Reprezentacja liczb w komputerze:

o stałe całkowite i rzeczywiste

o reprezentacje binarne stało- i zmiennopozycyjne

o systemy znak-moduł i uzupełnieniowy

o rachunek zmiennopozycyjny ? pojęcie zakresu i błędu zaokrągleń

* Zmienne i wyrażenia:

o typ zmiennej i wartościowanie zmiennych

o wyrażenia arytmetyczne i logiczne: składnia i semantyka

* Instrukcje while-programów:

o pusta, przypisania, warunkowa, iteracji, wyboru, czytania, pisania, wywołania procedury

o składnia i semantyka powyższych instrukcji

o obliczenia skończone i nieskończone

o błędy obliczeń

o przykłady algorytmów

* Asercje w programach i niezmienniki pętli:

o formuły Hoare'a

o uzasadnianie poprawności programów

o własność stopu i metody jej dowodzenia

* Typy danych:

o tablice

o rekordy

o zbiory

o pliki

o typy wyliczeniowe i okrojone

o typy wskaźnikowe

* Pliki:

o pliki o dostępie bezpośrednim

o pliki tekstowe

* Funkcje i procedury:

o składnia i semantyka

o sposoby przekazywania parametrów: przez wartość i przez zmienną

o widoczność zmiennych w zagnieżdżonych procedurach

* Miary złożoności algorytmów:

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

o rozmiar danych

o przykłady wyznaczania kosztów

o koszt zamortyzowany

* Rekurencja:

o rekurencyjne wyrażanie pojęć

o zastosowania i implementacja

o dowodzenie poprawności procedur rekurencyjnych

* Programowanie z nawrotami:

o przeszukiwanie pełnej przestrzeni stanów

o ucinanie rekursji

* Metoda dziel i rządź:

o metoda inkrementacyjna

o podział binarny

* Dynamiczne struktury danych:

o typy wskaźnikowe

o wskaźnikowa realizacja list

o podstawowe operacje na listach

o listy jednokierunkowe, dwukierunkowe i cykliczne

o atrapy i strażnicy

* Liniowe struktury danych: stosy i kolejki:

o implementacja tablicowa i listowa

o implementacja grafu za pomocą list sąsiedztwa

o algorytmy DFS i BFS

* Drzewa:

o implementacja drzew dowolnego rzędu

o drzewa binarne

o obiegi drzew

o konwersja wyrażeń z postaci infiksowej na prefiksową i postfiksową (ONP)

* Programowanie zachłanne:

o algorytm Huffmana

* Metoda spamiętywania:

o programowanie dynamiczne

Wiedza: student zna i rozumie

* uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie programowania, algorytmów i złożoności, architektury systemów komputerowych, systemów operacyjnych, technologii sieciowych, 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) 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, rekordy, 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ń o średnim poziomie złożoności (K_U01);

* czytać ze zrozumieniem programy zapisane w języku programowania imperatywnego (K_U06).

Kompetencje społeczne: student jest gotów do

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

* pracy z zachowaniem 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).