Hlavní obsah
Informatika
Kurz: Informatika > Kapitola 1
Lekce 6: Test prvočíselnosti- Úvod
- Výzva: test prvočíselnosti
- Postupné dělení
- Co je to počítáčová paměť?
- Efektivita algoritmů
- Úroveň 3: Výzva
- Eratosthenovo síto
- Úroveň 4: Eratosthenovo síto
- Test prvočíselnosti se sítem
- Úroveň 5: Postupné dělení pomocí síta
- Věta o prvočíslech
- Prvočíselná spirála
- Mezery mezi prvočísly
- Kompromis mezi časovou a paměťovou složitostí
- Shrnutí (co bude dál?)
Výzva: test prvočíselnosti
Jak může přístroj zjistit, zda je nějaké číslo prvočíslem? Tvůrce: Brit Cruise.
Chceš se zapojit do diskuze?
Zatím žádné příspěvky.
Transkript
Začneme velice jednoduchou otázkou. Jde spíše o výzvu. Potřebujeme postavit přístroj,
který vezme vstupní hodnotu... Vstupní hodnota bude
nějaké celé číslo 'x'. Náš přístroj musí pouze odpovědět "Pravda" nebo "Nepravda". To je první krok. Teď použijeme nástroje informatiky, abychom skutečně vytvořili zmíněný přístroj. A některé z otázek,
které se položíme, se týkají dvou vlastnosti
tohoto přístroje. Kolik času... Toto jsou hodiny. Za jak dlouho
získáme řešení? A kolik prostoru potřebujeme? Prostorem myslím v případě tohoto
mechanického počítače fyzický prostor. Kolik místností potřebujeme
pro náš přístroj? Nebo, když se jedná o počítač,
kolik paměti zabere program? Takže se k těmto myšlenkám
ještě vrátíme.