Složitost a korektnost algoritmu

Témata cvičení

• korektnost algoritmu
• složitost algoritmu

Průběh cvičení

• na algoritmu selection sort jsme si společně prošli
  • určení nejlepšího a nejhoršího případu
  • počítání složitosti
  • dokázání korektnosti pomocí invariantu cyklu
• na algoritmu bubble sort jste si vše zkusili sami
• podívali jsme se na návrh základního rekurzivního algoritmu pro součet prvků v poli

Domácí úkol 2

• Druhý zápočtový domácí úkol najdete zde.
• Termín odevzdání je začátek příštího cvičení.
• Pokud na cvičení nemůžete přijít, pošlete úkol do začátku cvičení mailem.

Úkoly k procvičení

• Napište pseudokód rekurzivního algoritmu pro zjištění součtu prvků pole. Nezapomeňte formálně popsat problém.
• Navrhněte algoritmus pro stejný problém (zjištění součtu prvků pole) pomocí cyklu (bez rekurze). Dokažte jeho korektnost.
• Napište pseudokód rekurzivního algoritmu pro výpočet mocniny a^b. Nezapomeňte formálně popsat problém.