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.

6. J.Tomasiewicz |Zaprzyjaźnij się z algorytmami", PWN 2015

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

Kryteria zaliczenia „Wstępu do programowania”.

Zaliczenie przedmiotu składa się z dwóch etapów:

1. Zaliczenie laboratoriów i ćwiczeń

2. Egzamin

Ad 1:

Na laboratoriach będą Państwo mieli 4 zadania. Liczą się wyniki 3 najlepszych. Każde zadanie jest oceniane w skali 0-20 i oceniamy zarówno poprawność kodu, jego złożoność, jak i styl rozwiązań oraz terminowość oddania zadań. Można zatem z zadań laboratoryjnych uzyskać maksymalnie 60 punktów. Aby zaliczyć przedmiot trzeba z tych zadań otrzymać co najmniej 50% maksymalnej liczby punktów, czyli 30 punktów i dodatkowo zaliczyć ćwiczenia.

Na ćwiczeniach będzie 8 kartkówek i 3 kolokwia. Kartkówki będą po 10 punktów, z tym że do ostatecznego wyniku bierzemy pod uwagę 6 najlepszych z tych 8, a kolokwia będą warte 40 punktów każde i liczą się wszystkie oceny. Maksymalnie z kartkówek i kolokwiów można uzyskać zatem odpowiednio 60 i 120 punktów.

Łącznie maksymalnie z zadań laboratoryjnych, kolokwiów i kartkówek można uzyskać 240 punktów.

Próg zaliczenia standardowo to 60%, więc 144 punkty zaliczają.

Ci, którzy uzyskają 90%, czyli 216 punktów, są uprawnieni do zdawania egzaminu zerowego i proponujemy im ocenę bardzo dobrą z tego terminu (czyli de facto zwolnienie).

Osoby, które zaliczą laboratoria i ćwiczenia mają prawo podejść do egzaminu w pierwszym terminie.

Ad 2:

Egzamin składa się z zadań pisemnych. Ocena końcowa zależy od procentowego wyniku, który jest maksimum z dwóch liczb

- czysty procentowy wynik egzaminu

- wynik ważony po 50% z procentowego wyniku z ćwiczeń i laboratoriów i 50% z egzaminu.

Wynik co najmniej 60% gwarantuje zdanie egzaminu. Wynik poniżej 50% gwarantuje niezdanie.

Przykład:

Ktoś dostał 40 punktów z kartkówek, 40 punktów z zadań laboratoryjnych i 100 punktów z kolokwiów. Łącznie uzyskał więc 180 punktów i zalicza ćwiczenia i laboratoria na poziomie 75%.

Jest dopuszczony do egzaminu i pisze go na 45%. Średnia z tych dwóch wyników, to 60%, więc wystarcza do zdania egzaminu.

Osoby, które nie zdadzą egzaminu w pierwszym terminie mogą podejść drugi raz.

Drugi termin egzaminu rządzi się tymi samymi zasadami, z tym, że dopuszczamy do niego też warunkowo osoby, które zaliczyły same laboratoria. Zdanie tego egzaminu na podanych wyżej zasadach skutkuje jednocześnie zaliczeniem ćwiczeń i przedmiotu. Niezdanie oznacza niezaliczone ćwiczenia i przedmiot.