Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie 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 kształcenia:

Wstęp do programowania jest podstawowym przedmiotem informatycznym na I roku. Zakładamy, że maturzyści mogli się nie zetknąć z programowaniem, więc naukę programowania prowadzimy od zera.

W trakcie nauki programowania studenci poznają jeden język (Pascal) - składnię wraz z semantyką (K_W03).

Rzecz jasna w trakcie nauki programowania nie o składnię głównie chodzi. Podstawowym celem kursu jest wyrobienie myślenia algorytmicznego - umiejętność rozpoznania problemu algorytmicznego, jego analiza, zaprojektowanie algorytmu i zakodowanie go, jak również pokazanie poprawności rozwiązania. (K_W04).

W tym celu uczymy studentów programowania oszczędnego zarówno pod względem czasowym jak i pamięciowym. Studenci poznają podstawowe struktury danych i techniki algorytmiczne umożliwiające efektywne rozwiązywanie problemów. (K_W05).

Sporo uwagi poświęcamy jakości kodu. Zwracamy zatem uwagę na jego poprawność, ale również na właściwe nazewnictwo zmiennych, estetykę tekstową, komentarze, używanie stałych. Na związanych z wykładem zajęciach laboratoryjnych studenci poznają środowisko programistyczne i podstawowe metody uruchamiania programów, (K_U05). Wymagamy też od nich rozumienia algorytmów i ich analizy (K_U06).

Ze względu na specyfikę organizacji zadań laboratoryjnych uczymy studentów sumienności i dotrzymywania terminów (K_K05).

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 2018/19" (zakończony)

Okres: 2018-10-01 - 2019-01-25
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: Michał Bernardelli, Piotr Chrząstowski-Wachtel, Konrad Durnoga, Marcin Dziubiński, Małgorzata Gałązka, Piotr Hofman, Katarzyna Jabłonowska, Łukasz Kamiński, Eryk Kopczyński, Michał Startek, Tomasz Waleń, Artur Zaroda
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr zimowy 2019/20" (w trakcie)

Okres: 2019-10-01 - 2020-01-27
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: Piotr Chrząstowski-Wachtel, Marcin Dziubiński, Katarzyna Jabłonowska, Łukasz Kamiński, Adam Malinowski, Michał Startek, Tomasz Waleń, 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.