Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Wstęp do programowania

Informacje ogólne

Kod przedmiotu: 1000-211bWPI
Kod Erasmus / ISCED: 11.301 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
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: 13.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
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.

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

Zajęcia w cyklu "Semestr zimowy 2021/22" (zakończony)

Okres: 2021-10-01 - 2022-02-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Ćwiczenia, 60 godzin więcej informacji
Laboratorium, 30 godzin więcej informacji
Wykład, 60 godzin więcej informacji
Koordynatorzy: Piotr Chrząstowski-Wachtel
Prowadzący grup: Łukasz Bożyk, Piotr Chrząstowski-Wachtel, Marcin Dziubiński, Krzysztof Fleszar, Marcin Peczarski, Grzegorz Pierczyński, Michał Startek, Tomasz Waleń, Daria Walukiewicz-Chrząszcz, Artur Zaroda
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Uwagi:

Zaliczenie przedmiotu składa się z trzech elementów:

  1. Zaliczenie laboratorium
  2. Zaliczenie ćwiczeń
  3. Zaliczenie egzaminu

Kolejne wymagania przedstawione są poniżej:

  1. 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.
  2. 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.
  3. 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.

Zajęcia w cyklu "Semestr zimowy 2022/23" (w trakcie)

Okres: 2022-10-01 - 2023-01-29
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć:
Ćwiczenia, 60 godzin więcej informacji
Laboratorium, 30 godzin więcej informacji
Wykład, 60 godzin więcej informacji
Koordynatorzy: Piotr Chrząstowski-Wachtel, Marcin Kubica
Prowadzący grup: Piotr Chrząstowski-Wachtel, Jacek Chrząszcz, Kamil Ciebiera, Marcin Dziubiński, Krzysztof Fleszar, Eryk Kopczyński, Marcin Kubica, Mirosława Miłkowska, Wojciech Nadara, Jakub Pawlewicz, Marcin Peczarski, Grzegorz Pierczyński, Jakub Radoszewski, Przemysław Rutka, Piotr Skowron, Marek Sokołowski, Michał Startek, Tomasz Waleń, Daria Walukiewicz-Chrząszcz, Artur Zaroda
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Uwagi:

Szczegółowe kryteria oceny są podane w opisach wykładów -- odpowiednio dla potoku.

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.
Krakowskie Przedmieście 26/28
00-927 Warszawa
tel: +48 22 55 20 000 https://uw.edu.pl/
kontakt deklaracja dostępności USOSweb 6.8.0.0-7 (2022-11-16)