Wstęp do programowania 1000-211bWPI
* 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
Rodzaj przedmiotu
Koordynatorzy przedmiotu
W cyklu 2022Z: | W cyklu 2021Z: |
Efekty kształcenia
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).
Kryteria oceniania
Zaliczenie przedmiotu składa się z trzech elementów:
- Zaliczenie laboratorium
- Zaliczenie ćwiczeń
- Zaliczenie egzaminu
Kolejne wymagania przedstawione są poniżej:
Zaliczenie laboratorium polega na uzyskaniu co najmniej 50% punktów z 3-4 domowych zadań programistycznych. Łączna liczba punktów do zdobycia, to 60. Punkty zdobywa się za poprawnie działające kody, przy czym pewna pula punktów (1/3) przyznawana jest za styl programowania, przy czym styl uwzględniamy tylko w przypadku działających programów.Osoby, które nie zaliczą laboratorium, jednocześnie nie zaliczają ćwiczeń i nie są dopuszczane do egzaminu z żadnym terminie.
- Na zaliczenie ćwiczeń składa się wynik uzyskany z sumy trzech składników: punktów z laboratorium (maksymalnie 60), punktów z kartkówek (maksymalnie 60) oraz punktów z 3 kolokwiów (maksymalnie 120). Kartkówek w semestrze jest 10, ocenianych w skali 0-10 i do oceny bierze się pod uwagę 6 najlepszych wyników. Kolokwia są wyceniane po 40 punktów. łącznie jest więc do zdobycia 240 punktów, z czego 144 (60%) zalicza. Osoby, które zaliczą laboratorium, ale nie uzyskają wymaganej sumy punktów, nie zaliczają ćwiczeń i tracą prawo pisania egzaminu w sesji normalnej. Mogą przystąpić warunkowo do egzaminu w sesji poprawkowej, z tym że traktujemy takie przypadki indywidualnie i zastrzegamy prawo indywidualizacji wymagań w takiej sytuacji (np. dodatkowe zadanie na zaliczenie ćwiczeń lub inne progi). W przypadku pozytywnym uzyskuje się wtedy zarówno zaliczenie ćwiczeń, jak i zdanie egzaminu, a negatywnym zarówno niezaliczenie ćwiczeń, jak i niezdanie egzaminu.
- Przy samym egzaminie w pierwszym terminie osoby, które uzyskały dobre wyniki z ćwiczeń i labów, będą mogły częściowo skorzystać z sumy c=L+C+K z wagą 1/3. Zatem jeśli do zdobycia na egzaminie jest E punktów, a ktoś uzyskał z samego egzaminu e, to ostateczny wynik procentowy łączony l, to
l = c/(2.4*3) + (200e/3E)
i ostateczny wynik całości, to maksimum z procentowego wyniku czystego (100e/E) i łączonego l, czyli max (100e/E, l). Próg zaliczenia egzaminu na ocenę dostateczną, to 60%. Reszta skali - zależna od wyników.W drugim terminie liczy się czysty wynik egzaminu i nie są brane pod uwagę ani ćwiczenia ani laboratoria.
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.
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: