Par tām algoritmu lekcijām
Skatos iebladzinātās MIT algoritmu lekcijas, ko Ulzha kaut kad bija ielinkājis. Rodas baigais besis par tām algoritmu lietām iekš LU: visas tās lekcijas ir nejēgā vienkāršas, bet informāciju iedod stipri labāk nekā tajās, kuras es apskatīju klātienē.
Tagad trīs (3) idejas, kuras nezināju (varbūt biju aizmirsis?):
1.
Tas ir labi, jo atļauj rēķināt Fibonači skaitļus logaritmiskā laikā. Jē!
2.
Veselo skaitļu summu pierādīšana ar integrāļiem: vienmērīgi augošām vai dilstošām funkcijām vērtību summu no sekojošiem veseliem skaitļiem var aproksimēt ar noteikto integrāli aptuveni tajās pašās robežās.
3.
Kā pierādīt n logn nepieciešamību kārtošanas algoritmiem: katru kārtošanas algoritmu, kas veic maina vietām un salīdzina divus elementus, var aprakstīt ar vaicājumu koku (decision tree), tālāk skaita lapas meklē nepieciešamo augstumu kokam, lai būtu tik daudz lapas, cik permutācijas dotajam ievadam.
Tagad trīs (3) idejas, kuras nezināju (varbūt biju aizmirsis?):
1.
(1 1)n (F_{n+1} F_{n} )
(1 0) = (F_{n} F_{n-1})
Tas ir labi, jo atļauj rēķināt Fibonači skaitļus logaritmiskā laikā. Jē!
2.
Veselo skaitļu summu pierādīšana ar integrāļiem: vienmērīgi augošām vai dilstošām funkcijām vērtību summu no sekojošiem veseliem skaitļiem var aproksimēt ar noteikto integrāli aptuveni tajās pašās robežās.
3.
Kā pierādīt n logn nepieciešamību kārtošanas algoritmiem: katru kārtošanas algoritmu, kas veic maina vietām un salīdzina divus elementus, var aprakstīt ar vaicājumu koku (decision tree), tālāk skaita lapas meklē nepieciešamo augstumu kokam, lai būtu tik daudz lapas, cik permutācijas dotajam ievadam.
Comments