Algoritmai

• Uždaviniai, kuriems nėra žinoma jokio polinominio sudėtingumo algoritmo, arba sunkūs uždaviniai, pavyzdžiui keliaujančio pirklio uždavinys.
• Algoritmo korektiškumo (teisingumo) problema: reikia nustatyti, ar konkretus algoritmas išduos atsakymą, sutampantį su tikruoju nagrinėjamo uždavinio sprendiniu;
• Algoritmo sudėtingumo problema: reikia nustatyti, kiek žingsnių daugiausia atliks konkretus algoritmas iki sustojimo, ar jis užbaigs darbą per mums priimtiną laiką, ir ar šiam algoritmui užteks turimų atminties resursų;
2
Algoritmo efektyvumo problema: nustačius algoritmo sudėtingumą, reikia įvertinti, kiek jis yra efektyvus, t.y., ar tai yra pats geriausias galimas algoritmas nagrinėjamam uždaviniui spręsti, ar galima rasti geresnį algoritmą.
3
2,Kombinatoriniai objektai ir jų vaizdavimo būdai
Paprasčiausi kombinatoriniai objektai:
1. Sveikieji skaičiai:
• Vaizdavimas skaičiavimo sistemoje su pagrindu r
• Vaizdavimas mišrioje skaičiavimo sistemoje
• Vaizdavimas liekanų vektoriais
2. Sekos:
• Nuoseklus sekų vaizdavimas
• Sekų vaizdavimas sąrašais
• Sekų vaizdavimas charakteringaisiais vektoriais
3. Medžiai
• Tėvų nuorodos
• Vaikų nuorodos
• Nurodant kairįjį ir dešinįjį brolį
4. Aibės
• Nuoseklus vaizdavimas
• Vaizdavimas sąrašais
• Vaizdavimas charakteringaisiais vektoriais
• Miškas (kartais)
4
3,Grafai ir jų vaizdavimas
Grafu vadiname porą G = (V;E), kur V yra bet kokia netuščia aibė, o E yra bet kuris aibės Porų iš V elementų multipoaibis. Jei tos poros yra vektoriai, tai grafą vadiname orientuotu grafu arba orgrafu. Jei poros yra tiesiog aibės V multipoaibiai, tai grafą vadiname neorientuotu arba tiesiog grafu. Aibė V vadinama grafo G viršūnių aibe. Orgrafuose porą e = (u; v) vadiname lanku ir sakome, kad lankas e = (u; v) jungia orgrafo G viršūnes u ir v. Dvi poros (u; v) ir (v; u) orgrafe reiškia du skirtingus lankus. Sakoma, kad briauna (lankas) e = (u; v) yra incidentinė (-is) viršūnėms u ir v . Neorientuotuose grafuose dvi poros (u; v) ir (v; u) reiškia tą pačią briauną. Aukščiau apibrėžti grafai ir orgrafai gali turėti kelias vienodas briaunas (lankus), kurios vadinamos kartotinėmis briaunomis (kartotiniais lankais). Taip pat tokie grafai gali turėti ir kilpas, t.y., briaunas (lankus). Kai kuriuose vadovėliuose grafais vadinami tik grafai,...

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!