Wstęp do programowania 1000-211bWPI
• 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
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
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 oceniania
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.
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. 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
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: