Nové výhodné předplatné namísto kreditů je tu! Více informací. Upravili jsme také naše provozní podmínky.
NOVINKA: Staň se datovým analytikem a získej jistotu práce, lepší plat a nové kariérní možnosti. Více informací:
Avatar
LittleOne
Člen
Avatar
LittleOne:7.11.2016 21:59

Zdravím. Práve sa snažím riešiť Korešpondenčný seminár z Informatiky (ksi.fi.muni.cz). No zasekol som sa na jednej úlohe a bez nej nemôžem pokračovať, tak som sa rozhodol požiadať vás o pomoc.

V tejto úlohe mám označiť správne tvrdenia z týchto:

1. U abstraktní datové struktury nás nezajímá časová složitost jednotlivých operací.
2. Konkrétní datová struktura není závislá na implementaci.
3. U abstraktní datové struktury je nutné mít definované CRUD operace.
4. Jednu datovou strukturu lze použít k časově optimálnímu vyřešení více
algoritmických problémů.
5. Prioritní fronta je konkrétní datovou strukturou (na rozdíl od obyčejné fronty).
6. Korektní datová struktura může mít i nulový počet prvků.
7. Jednotlivé implementace dané abstraktní datové struktury mohou mít různé
asymptotické časové složitosti jednotlivých operací.
8. Pole patří mezi nejběžnější datové struktury.
9. Konkrétní datová struktura může obsahovat nové vnější chování (vyhovující původní
abstraktní datové struktuře). Tedy může například definovat operace, které abstraktní
datová struktura nedefinovala.
10. Vhodná volba datových struktur nám umožní zapsat program přehledněji a případně jej i urychlit.
11. Neexistuje nejlepší datová struktura řešící optimálně veškeré algoritmické problémy.
12. Při posuzování vhodnosti konkrétní implementace datové struktury může být vhodným
 kritériem například asymptoticka složitost některých operací.
13. Při posuzování vhodnosti konkrétní implementace datové struktury může být vhodným
kritériem například složitost implementace.
14. Každou abstraktní datovou strukturu lze implementovat nejvýše jedním způsobem
(pokud ji vůbec lze implementovat)

Pri úlohe bol článok, z ktorého som sa, pravdupovediac, skoro nič nedozvedel.

Moje riešenie (nesprávne) bolo nasledovné:

1. Nesprávne - Vždy by som mal zvoliť to najoptimálnejšie riešenie, takže ma zložitosť zaujíma
2. ?
3. ?
4. Správne
5. Nesprávne - bolo spomenuté v článku, že Prioritní fronta je abstraktnou štruktúrou.
6. Správne
7. Správne
8. Správne
9. ?
10. Správne
11. Správne - Keby existovala univerzálna štruktúra, tak by sme ich toľko nepotrebovali
12. Správne - Vždy prihliadam na rýchlosť programu
13. Správne - Vždy chcem mať kód prehľadný
14. Nesprávne - Každý problém sa dá riešiť nespočetným množstvom spôsobov

Pri ? som vyskúšal všetky možnosti, a aj tak to nebolo správne riešenie. Vedeli by ste mi poradiť / naviesť ma kde robím chybu? Nechcel som sa tu pýtať, chcel som riešiť celý seminár sám, ale už pár hodín to riešim a bez toho nemôžem pokračovať ďalej.

Ďakujem

Editováno
 
Odpovědět
7.11.2016 21:59
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na LittleOne
Martin Dráb:8.11.2016 1:05

Hádám, že po vás chtějí, abyste odpovědi na otázky vyčetli z toho článku. Pokud sem ale nedáš na něj link, tak ti asi moc lidí nepomůže, protože ten článek může obsahovat pro něj specifické definice pojmů, popř. úhel pohledu jeho autorů, které jsou pro zodpovězení otázek důležité. Také se musíš rozhodnout, zda-li se od vás očekává čistě vědecký pohled, nebo pohled více praktický.

Třeba u té 13
Z čistě vědeckého pohledu by tě složitost implementace zajímat neměla; měl bys veškeré úsilí věnovat do vylepšení vlastností datové struktury. Výkonné implementace datových struktur také často přehledně napsané nejsou, např. protože jsou lock-free, používají vektorové operace, vyhýbají se podmíněným příkazům, alokacím paměti...

Z hlediska praktického je to samozřejmě pravda.

Působí to na mě tak, že v tom článku se definují pojmy jako abstraktní datová struktura a kokrétní datová struktura a je tam o nich nějaké větší povídání, ze kterého odvodíš odpovědi na ty otázky.

Nahoru Odpovědět
8.11.2016 1:05
2 + 2 = 5 for extremely large values of 2
Avatar
LittleOne
Člen
Avatar
LittleOne:8.11.2016 13:40

Datové struktury nám slouží k efektivnímu ukládání komplexnějších či opakujících se dat. Jedná se o jakési skladiště pro data, jednotlivé datové položky v nich nazýváme prvky datové struktury. Dalším důvodem zavedení datových struktur je také zjednodušení programu. Lépe se nám totiž bude pracovat se strukturou Clovek s prvky datum_narozeni, rodne_cislo, vyska a vaha než s obyčejným polem čísel, kde 4 po sobě jdoucí čísla určují hodnoty data narození, rodného čísla, výšky a váhy, a je zapotřebí si pamatovat význam jednotlivých indexů.

Můžeme se bavit buď o abstraktních datových strukturách nebo o konkrétních. Abstraktní datová struktura je taková, která je nezávislá na konkrétní implementaci – je definováno její vnější chování, avšak ne konkrétní způsob jakým uvnitř pracuje. Příkladem budiž prioritní fronta – struktura, která podporuje operaci vybrání prvku s nejnižší hodnotou. Nespecifikujeme však už, jak tento prvek nalézt. To lze provést například naivně projítím všech prvků anebo sofistikovaněji s využitím nějaké k tomu navržené konkrétní datové struktury. Konkrétní datová struktura je pak konkrétní implementace dané abstraktní datové struktry (např. implementace prioritní fronty pomocí lineárně spojovaného seznamu či pomocí haldy).

ZÁKLADNÍ OPERACE NAD DATOVÝMI STRUKTURAMI
V anglické literatuře jsou nazývány pojmem CRUD operace (Create, Read, Update, Delete) pro jednotlivé prvky struktury + operace na (de)inicializaci celé datové struktury.

Inicializace celé datové struktury (zavedení datové struktury do paměti včetně počátečního nastavení proměnných).

Vložení prvku (angl. push nebo insert).

Vybrání prvku (angl. pop, select nebo find).

Smazání prvku (angl. delete nebo erase).

Změna hodnoty existujícího prvku (angl. update).

Odstranění celé datové struktury (provedení závěrečných operací + samotné odstranění datové strukury z paměti).

U abstraktních datových struktur bývá obvykle definována sémantika jednotlivých operací (tj. jak jednotlivé operace mění danou datovou strukturu a data v ní uložená), u konkrétních implementací jednotlivých datových struktur pak jejich konkrétní provedení (jehož efektivitu pak lze hodnotit například pomocí asymptotické časové složitosti).

Pro každý algoritmický problém se nám může hodit jiná datová struktura, při jejím výběru zvažujeme, které z definovaných operací budeme potřebovat a jak často, díváme se na součet časových složitostí všech jednotlivých použití konkrétních operací, jenž v rámci celého programu využijeme (při použití jiné datové struktury se jejich seznam a počty použití mohou lišit). Zároveň také zvažujeme, jestli se implementace složitejší ale rychlejší datové struktury vyplatí nebo jestli je smysluplnější ušetřit čas programátorovi a nemít tak složitý kód, protože výkon nemusí být vždy klíčový. Zdroj: ksi.fi.muni.cz/u­lohy/64

Toto je celý článok, prečítal som ho asi 5x, no veľa som sa z neho nedozvedel.

 
Nahoru Odpovědět
8.11.2016 13:40
Avatar
anticary
Člen
Avatar
Odpovídá na LittleOne
anticary:9.11.2016 21:52

Mám stejný problém :) ... Pokud by se mi to povedlo nějak odhadnout a pokud by to tu ještě nebylo, tak to sem pošlu. :)

 
Nahoru Odpovědět
9.11.2016 21:52
Avatar
anticary
Člen
Avatar
Odpovídá na LittleOne
anticary:9.11.2016 22:22

Mám to :)
Napíšu jenom ty, který jsou špatně(navybrané): 2, 5, 14
Doufám, že pomůžu :)

 
Nahoru Odpovědět
9.11.2016 22:22
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 5 zpráv z 5.