|
TwojePC.pl © 2001 - 2024
|
 |
A R C H I W A L N A W I A D O M O Ś Ć |
 |
| |
|
Potrzebna pomoc z algorytmow i struktur danych! , kaszpio 23/06/03 11:38
W sobote mam egzamin a tego przedmiotu...zaczynam gromadzic materialy, moze znacie jakies milutkie zrodla na te zagadniania, bede wdzieczny;-)
Zagadnienia egzaminacyjne;
Zagadnienia na egzamin AiSD studia zaoczne
1. Wstępne pojęcia z zakresu złożoności obliczeniowej:
- - problemy optymalizacyjne a problemy decyzyjne
- - kodowanie instancji
- - rozsądne reguły kodowania - cechy
- - modele obliczeń (DTM, NDTM, k-DTM RAM)
- - przykłady programów na DTM
- - funkcja złożoności obliczeniowej
2. Klasy złożoności problemów decyzyjnych
- - definicje klas
- - schemat klas
- - transformacja wielomianowa
- - transformacja pseudo-wielomianowa
- - metody dowodzenia NP-zupełności
- - metodologia postępowania z problemami otwartymi
3. Sformułowanie problemów NP-zupełnych:
- - problemu podziału zbioru
- - problemu znajdowania cyklu Hamiltona
- - problemu znajdowania kliki w grafie
- - problemu pokrycia grafu wierzchołkami
- - problemu trójwymiarowego skojarzenia
wraz z przykładami.
4. Algorytmy sortowania
Znajomość algorytmów sortowania:
- - szybkiego (Quicksort) - QS,
- - przez kopcowanie (Heapsort) - HS,
- - przez proste wybieranie (Selection Sort ) - SS,
- - przez proste wstawianie (Insertion Sort) - IS,
- - przez prostą zamianę (Bubble Sort) - BbS,
- - za pomocą malejących przyrostów (metoda Shella) - ShS,
- - przez zliczanie (Counting Sort) - CS,
- - (pozycyjnego (Radix Sort) - RS,)
- - kubełkowego (Bucket Sort) - BS
- - sortowanie przez scalanie - MS
obejmująca:
- - ideę tj. sposób działania algorytmu,
- - analizę zachowanie metody dla różnych rozkładów danych wejściowych z uwzględnieniem identyfikacji najlepszego i najgorszego przypadku,
- złożoność obliczeniową w przypadku średnim, najlepszym i najgorszym,
- - zalety, wady, ograniczenia poszczególnych algorytmów,
- - zalecane warunki stosowania metody.
-
5. Złożone struktury danych
Znajomość struktury listy jednokierunkowej i drzewa poszukiwań binarnych (ang. Binary Search Tree – BST) ze szczególnym uwzględnieniem:
- tworzenia oraz usuwania listy i drzewa,
- - wyszukiwania elementu w liście i drzewie,
- - usuwania elementu z listy i drzewa,
- - przeglądania drzewa w 3 porządkach: wzdłużnym, poprzecznym i wstecznym,
- - definicji drzewa wyważonego i dokładnie wyważonego.
6. Algorytmy grafowe
Znajomość:
- - definicji grafu skierowanego i nieskierowanego,
- - reprezentacji grafu (macierz incydencji, macierz sąsiedztwa wierzchołków, lista krawędzi, listy incydencji poprzedników i następników), ich złożoności pamięciowej i złożoności procesu pozyskiwania różnych typów informacji o grafie,
- - algorytmów przeszukiwania grafu „w głąb” i „wszerz”,
- - sortowanie topologiczne
- - znajdowanie składowych dwu spójnych i silnie spójnych
7. Algorytmy z powracaniem
Znajomość:
- - idei działania algorytmów z powracaniem,
- - problemów znajdowania cyklu Eulera i Hamiltona w grafie nieskierowanym oraz ich przynależności do odpowiednich klas złożoności obliczeniowej,
- - idei algorytmu z powracaniem dla problemu znajdowania cyklu Hamiltona.
8. Programowanie dynamiczne
Znajomość:
- - metody programowania dynamicznego oraz zakresu jej stosowalności, możliwej złożoności obliczeniowej,
- - sformułowania problemu plecakowego i metody jego rozwiązania.
- - algorytm zachłanny dla problemu plecakowego
- - "Dziel i zwyciężaj" dla problemu znajdowania elementu minimalnego i maksymalnego w macierzy.
9. Metoda podziału i ograniczeń na przykładzie problemu Komiwojażera.
10. Algorytmy przybliżone i oszacowania najgorszego przypadku.Toshiba Tecra S11-124 - ....... , XiSiO 23/06/03 12:02
gogle -> algorytmy =
http://www.algorytm.cad.pl/
polecam"Przyjaźń - bezcenna za wszytko inne
zapłacisz adeną" (C) XiSiO - RE: Algorytmy , ziułek 23/06/03 12:47
Podaj maila to coś ci wrzucę- prose... , kaszpio 23/06/03 12:56
Pozdrawiam!Toshiba Tecra S11-124
|
|
|
|
 |
All rights reserved ® Copyright and Design 2001-2024, TwojePC.PL |
 |
|
|
|
