Uniwersytet Warszawski, Wydział Nauk Ekonomicznych - 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 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, Wydział Nauk Ekonomicznych.
ul. Długa 44/50
00-241 Warszawa
tel: +48 22 55 49 126 https://www.wne.uw.edu.pl/
kontakt deklaracja dostępności USOSweb 6.8.1.0-1 (2023-01-18)