Metody programowania: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
WizualnieWikikod
Pch (dyskusja | edycje)
411 edycji
Nie podano opisu zmian
 
Pch (dyskusja | edycje)
411 edycji
 
(Nie pokazano 23 wersji utworzonych przez 5 użytkowników)
Linia 1: Linia 1:
== Forma zajęć ==
== Forma zajęć ==
Wykład (30 godzin) + ćwiczenia (30 godzin)
Wykład (30 godzin) + laboratorium (30 godzin)


== Opis ==
== Opis ==
Podstawowy przedmiot informatyczny drugiego semestru studiów, mający zapoznać studentów z pojęciem algorytmu i programu. Celem zajęć jest nauczenie projektowania, zapisywania, dowodzenia poprawności i uwzględniania złożoności algorytmów.
Celem zajęć jest prezentacja technik programistycznych i struktur danych wykorzystywanych w programowaniu w małej i średniej skali.


== Sylabus ==
== Sylabus ==
=== Autor ===
=== Autor ===
* Piotr Chrząstowski-Wachtel
* Piotr Chrząstowski-Wachtel — Uniwersytet Warszawski


=== Wymagania wstępne ===
=== Wymagania wstępne ===
Linia 14: Linia 14:
=== Zawartość ===
=== Zawartość ===


* Rekurencja  
* Rekurencja:
** rekurencyjne wyrażanie pojęć  
** rekurencyjne wyrażanie pojęć  
** zastosowania i implementacja
** zastosowania i implementacja
** dowodzenie poprawności procedur rekurencyjnych.
** dowodzenie poprawności procedur rekurencyjnych
* Programowanie z nawrotami
* Programowanie z nawrotami:
** przeszukiwanie pełnej przestrzeni stanów
** przeszukiwanie pełnej przestrzeni stanów
** ucinanie rekursji
** ucinanie rekursji
* Metoda dziel i rządź
* Metoda ''dziel i rządź'':
** metoda inkrementacyjna  
** metoda inkrementacyjna  
** podział binarny
** podział binarny
* Dynamiczne struktury danych  
* Dynamiczne struktury danych:
** typy wskaźnikowe
** typy wskaźnikowe
** wskaźnikowa realizacja list
** wskaźnikowa realizacja list
** podstawowe operacje na listach
** podstawowe operacje na listach
** listy jednokierunkowe, dwukierunkowe i cykliczne
** listy jednokierunkowe, dwukierunkowe i cykliczne
** atrapy i strażnic
** atrapy i strażnicy
* Liniowe struktury danych: stosy i kolejki
* Liniowe struktury danych: stosy i kolejki:
** implementacja tablicowa i listowa
** implementacja tablicowa i listowa
** implementacja grafu za pomocą list sąsiedztwa
** implementacja grafu za pomocą list sąsiedztwa
** algorytmy DFS I BFS
** algorytmy DFS i BFS
* Drzewa  
* Drzewa:
** implementacja drzew dowolnego rzędu
** implementacja drzew dowolnego rzędu
** drzewa binarne
** drzewa binarne
** obiegi drzew
** obiegi drzew
** konwersja wyrażeń z postaci infiksowej na prefiksową i postfiksową (ONP)
** konwersja wyrażeń z postaci infiksowej na prefiksową i postfiksową (ONP)
* Programowanie zachłanne
* Programowanie zachłanne:
** algorytm Huffmana
** algorytm Huffmana
* Metoda spamiętywania  
* Metoda spamiętywania:
** programowanie dynamiczne  
** programowanie dynamiczne  
** problem plecakowy
** problem plecakowy
** optymalne mnożenie wielu macierzy.
** optymalne mnożenie wielu macierzy
 
 
1.Algorytmy+Struktury danych=Programy, N.Wirth, WNT 2001.
2.Wprowadzenie do algorytmiki, T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, WNT 2000.
3.Algorytmy w C++, R.Sedgewick, MIKON 2001
4.D. Knuth, Sztuka programowania komputerów, tom 3, WNT 2002


=== Literatura ===
#  N.Wirth, ''Algorytmy+Struktury danych=Programy'', Wydawnictwa Naukowo-Techniczne, Warszawa 2001.
# T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, ''Wprowadzenie do algorytmiki'', Wydawnictwa Naukowo-Techniczne, Warszawa 2004.
# D.E.Knuth, ''Sztuka programowania komputerów tom 3'', Wydawnictwa Naukowo-Techniczne, Warszawa 2002.


=== Literatura ===
=== Moduły ===
# ''Algorytmy+Struktury danych=Programy'', N.Wirth, Wydawnictwa Naukowo - Techniczne 2001.
# ([[Metody_programowania_/_Ćwiczenia_1|Ćwiczenia rekursja]])
# ''Wprowadzenie do algorytmiki'', T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, Wydawnictwa Naukowo - Techniczne 2004.
# [[Metody_programowania_/Listy|Listy]]([[Metody_programowania_/_Ćwiczenia_2|Ćwiczenia:listy]])
# Sztuka programowania komputerów, tom 3, WNT 2002
# [[Metody_programowania_/Drzewa|Drzewa]]([[Metody_programowania_/_Ćwiczenia_3|Ćwiczenia:drzewa]])
# [[Metody_programowania_/StosyKolejki|Stosy i kolejki]]([[Metody_programowania_/_Ćwiczenia_4|Ćwiczenia:stosy i kolejki]])
# ([[Metody_programowania_/_Ćwiczenia_5|Ćwiczenia:programowanie zachłanne]])
# ([[Metody_programowania_/_Ćwiczenia_6|Ćwiczenia:programowanie dynamiczne]])

Aktualna wersja na dzień 20:13, 11 gru 2008

Forma zajęć

Wykład (30 godzin) + laboratorium (30 godzin)

Opis

Celem zajęć jest prezentacja technik programistycznych i struktur danych wykorzystywanych w programowaniu w małej i średniej skali.

Sylabus

Autor

  • Piotr Chrząstowski-Wachtel — Uniwersytet Warszawski

Wymagania wstępne

  • Wstęp do programowania

Zawartość

  • Rekurencja:
    • rekurencyjne wyrażanie pojęć
    • zastosowania i implementacja
    • dowodzenie poprawności procedur rekurencyjnych
  • Programowanie z nawrotami:
    • przeszukiwanie pełnej przestrzeni stanów
    • ucinanie rekursji
  • Metoda dziel i rządź:
    • metoda inkrementacyjna
    • podział binarny
  • Dynamiczne struktury danych:
    • typy wskaźnikowe
    • wskaźnikowa realizacja list
    • podstawowe operacje na listach
    • listy jednokierunkowe, dwukierunkowe i cykliczne
    • atrapy i strażnicy
  • Liniowe struktury danych: stosy i kolejki:
    • implementacja tablicowa i listowa
    • implementacja grafu za pomocą list sąsiedztwa
    • algorytmy DFS i BFS
  • Drzewa:
    • implementacja drzew dowolnego rzędu
    • drzewa binarne
    • obiegi drzew
    • konwersja wyrażeń z postaci infiksowej na prefiksową i postfiksową (ONP)
  • Programowanie zachłanne:
    • algorytm Huffmana
  • Metoda spamiętywania:
    • programowanie dynamiczne
    • problem plecakowy
    • optymalne mnożenie wielu macierzy

Literatura

  1. N.Wirth, Algorytmy+Struktury danych=Programy, Wydawnictwa Naukowo-Techniczne, Warszawa 2001.
  2. T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, Wprowadzenie do algorytmiki, Wydawnictwa Naukowo-Techniczne, Warszawa 2004.
  3. D.E.Knuth, Sztuka programowania komputerów tom 3, Wydawnictwa Naukowo-Techniczne, Warszawa 2002.

Moduły

  1. (Ćwiczenia rekursja)
  2. Listy(Ćwiczenia:listy)
  3. Drzewa(Ćwiczenia:drzewa)
  4. Stosy i kolejki(Ćwiczenia:stosy i kolejki)
  5. (Ćwiczenia:programowanie zachłanne)
  6. (Ćwiczenia:programowanie dynamiczne)
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Metody_programowania&oldid=75671”