Serwisy internetowe Uniwersytetu Warszawskiego Nie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Wstęp do programowania (podejście imperatywne)

Informacje ogólne

Kod przedmiotu: 1000-211bWPI Kod Erasmus / ISCED: 11.301 / (0612) Database and network design and administration
Nazwa przedmiotu: Wstęp do programowania (podejście imperatywne)
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
zobacz reguły punktacji
Język prowadzenia: polski
Rodzaj przedmiotu:

obowiązkowe

Skrócony opis:

Podstawowy przedmiot studiów, 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:

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

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

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

Metody i kryteria oceniania:

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 2020/21" (zakończony)

Okres: 2020-10-01 - 2021-01-31
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, Konrad Durnoga, Marcin Dziubiński, Piotr Hofman, Grzegorz Pierczyński, Marek Sokołowski, Michał Startek, Daria Walukiewicz-Chrząszcz, Artur Zaroda
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr zimowy 2021/22" (w trakcie)

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
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.