Wstęp do programowania
Informacje ogólne
Kod przedmiotu: | 1000-211bWPI |
Kod Erasmus / ISCED: |
11.301
|
Nazwa przedmiotu: | Wstęp do programowania |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty obowiązkowe dla I roku informatyki Przedmioty obowiązkowe dla I roku JSIM |
Punkty ECTS i inne: |
12.00
|
Język prowadzenia: | polski |
Rodzaj przedmiotu: | obowiązkowe |
Skrócony opis: |
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. |
Pełny opis: |
• 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 |
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 |
Efekty uczenia się: |
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). |
Metody i 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. |
Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)
Okres: | 2023-10-01 - 2024-01-28 |
Przejdź do planu
PN WYK
WYK
CW
CW
CW
CW
CW
CW
CW
CW
CW
CW
LAB
CW
CW
CW
WT LAB
CW
ŚR CW
WYK
WYK
LAB
LAB
CW
CW
CW
CW
LAB
CW
LAB
LAB
CW
CW
CW
LAB
LAB
LAB
LAB
LAB
CW
LAB
CZ CW
PT CW
|
Typ zajęć: |
Ćwiczenia, 60 godzin
Laboratorium, 30 godzin
Wykład, 60 godzin
|
|
Koordynatorzy: | Piotr Chrząstowski-Wachtel, Marcin Kubica | |
Prowadzący grup: | Łukasz Bożyk, Paweł Brach, Piotr Chrząstowski-Wachtel, Jacek Chrząszcz, Marcin Dziubiński, Krzysztof Fleszar, Eryk Kopczyński, Marcin Kubica, Paweł Parys, Jakub Pawlewicz, Marcin Peczarski, Jakub Radoszewski, Przemysław Rutka, Marcin Smulewicz, Michał Startek, Daria Walukiewicz-Chrząszcz, Marcin Waniek, Artur Zaroda | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Zajęcia w cyklu "Semestr zimowy 2024/25" (w trakcie)
Okres: | 2024-10-01 - 2025-01-26 |
Przejdź do planu
PN WYK
WYK
CW
CW
CW
CW
CW
CW
CW
CW
CW
CW
CW
CW
CW
CW
WT CW
LAB
ŚR WYK
WYK
CW
LAB
CW
CW
LAB
LAB
CW
CW
LAB
CW
LAB
CW
LAB
LAB
CW
LAB
LAB
CW
CW
LAB
LAB
LAB
CW
LAB
CW
CZ CW
PT |
Typ zajęć: |
Ćwiczenia, 60 godzin
Laboratorium, 30 godzin
Wykład, 60 godzin
|
|
Koordynatorzy: | Piotr Chrząstowski-Wachtel, Marcin Kubica | |
Prowadzący grup: | Łukasz Bożyk, Piotr Chrząstowski-Wachtel, Jacek Chrząszcz, Marcin Dziubiński, Krzysztof Fleszar, Agata Janowska, Eryk Kopczyński, Marcin Kubica, Wojciech Nadara, Paweł Parys, Jakub Pawlewicz, Marcin Peczarski, Grzegorz Pierczyński, Jakub Radoszewski, Przemysław Rutka, Michał Startek, Tomasz Waleń, Daria Walukiewicz-Chrząszcz, Marcin Waniek, Artur Zaroda, Marek Zbysiński | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Właścicielem praw autorskich jest Uniwersytet Warszawski, Wydział Nauk Ekonomicznych.