Sum up this problem and solve it: Studijní text Ondra si před deseti lety během zkoušky…
- User
Sum up this problem and solve it: Studijní text Ondra si před deseti lety během zkoušky z algoritmizace vylosoval třídicí algoritmy, které se nenaučil, a ze zkoušky dostal čtyřku. Tehdy přísahal, že se třídicím algoritmům pomstí. Pomstít se algoritmu ale není vůbec jednoduché, protože algoritmus není možné zničit ani uvěznit. Algoritmus může porazit jedině tím, že ho překoná. Proto Ondra posledních deset let strávil vývojem úplně nového modelu procesoru, který umí třídit v konstantním čase. Je si jistý, že za pár let bude počítač s Ondrovým procesorem v každé domácnosti. Na třídicí algoritmy pak všichni do pár dalších let zajisté zapomenou! Stroje na masovou výrobu integrovaných obvodů jsou ale velmi drahé, takže Ondra potřebuje pár ukázkových programů, aby získal přízeň investorů. Protože Ondra nikdy algoritmizaci nedostudoval, chce, abyste mu s tím pomohli. Ondrův procesor Ondrův procesor má N jader, každé má jiné identifikační číslo od 0 do N − 1. Jádra jsou uspořádána v řadě. Na začátku jsou seřazená podle identifikačních čísel s jádrem 0 vlevo, jejich pořadí se ale v průběhu výpočtu může měnit. Programy pro něj jsou tvořeny posloupností instrukcí, které všechna jádra vykonávají souběžně, tedy nejprve všechna jádra současně vykonají první instrukci, poté všechna jádra vykonají druhou instrukci, a tak dále. Existuje mnoho různých instrukcí, jejich seznam najdete níže. Instrukce číslujeme od jedné. Každá instrukce spočítá hodnotu, které budeme říkat výsledek. Každé jádro si pamatuje výsledky všech instrukcí, které za běh programu vykonalo. Většina instrukcí pracuje s výsledky předchozích instrukcí, například instrukce + 1 2 sečte výsledek první a druhé instrukce. Jádra mohou číst paměť svých sousedů pomocí speciálních instrukcí left a right. Instrukce left i přečte výsledek i-té instrukce vykonané jádrem nalevo od jádra, co ji vykoná, obdobně right i přečte výsledek i-té instrukce jádra napravo. Čtení probíhá cyklicky, tedy první jádro je napravo od posledního. Nakonec tu máme nejdůležitější instrukci, a to sort, která změní pořadí jader. Každé jádro si nejprve zvolí číslo zvané klíč (argument instrukce sort). Poté procesor pomocí komplikovaných obvodů jádra seřadí. Jádro s nejmenším klíčem skončí nalevo a jádro s největším klíčem skončí napravo. Třídění je stabilní, tj. jádra se stejným klíčem si zachovají vzájemné pořadí. Jádra si při přesuvání zachovávají svoje identifikační čísla i historii výsledků instrukcí, jádro s identifikačním číslem 0 tedy po přesunutí už nemusí být nalevo. Aritmetika Ondrův procesor používá 64-bitová znaménková čísla ve dvojkovém doplňku, muže tedy reprezentovat čísla v rozsahu −2 63 až 263 − 1. Pokud se výsledek nějaké operace nevejde do 64 bitů, pak budou přebytečné nejvýznamnější bity zahozeny. 9 Vstup a výstup Každé jádro má několik vstupů (počet záleží na problému) očíslovaných od 1. Vstup číslo k může jádro přečíst pomocí instrukce input k. Za výstup jádra považujeme výsledek poslední instrukce, kterou vykoná. Instrukční sada K dispozici jsou následující instrukce. V popisu instrukcí označíme výsledek i-té instrukce pro specifikované jádro ri . const x Vrátí číslo x. id Vrátí identifikační číslo jádra. input k Vrátí k-tou vstupní hodnotu tohoto jádra. copy i Vrátí ri . sort i Seřadí jádra podle klíče ri , vrátí ri . left i Vrátí ri jádra nalevo. right i Vrátí ri jádra napravo.
- a b Vrátí ra + rb.
- a b Vrátí ra − rb.
- a b Vrátí ra · rb. / a b Vrátí dolní celou část ra ÷ rb, pokud rb 6= 0, jinak vrátí 0. % a b Vrátí zbytek po dělení ra ÷ rb, pokud rb 6= 0, jinak vrátí 0. | a b Vrátí bitovou disjunkci (or) ra a rb. & a b Vrátí bitovou konjunkci (and) ra a rb. ^ a b Vrátí bitovou exkluzivní disjunkci (xor) ra a rb. = a b Vrátí 1, pokud ra = rb, jinak vrátí 0. != a b Vrátí 1, pokud ra 6= rb, jinak vrátí 0. < a b Vrátí 1, pokud ra < rb, jinak vrátí 0.
a b Vrátí 1, pokud ra > rb, jinak vrátí 0. <= a b Vrátí 1, pokud ra ≤ rb, jinak vrátí 0. = a b Vrátí 1, pokud ra ≥ rb, jinak vrátí 0. if c a b Pokud rc 6= 0, pak vrátí ra, jinak vrátí rb. Formát programu Programy pro Ondrův procesor se zapisují do textového souboru. Každá instrukce je zapsaná na svém vlastním řádku. Jméno instrukce a její argumenty jsou oddělené alespoň jednou mezerou či tabulátorem. V kódu mohou být prázdné řádky, které nic nedělají a nepočítají se mezi instrukce. Program může obsahovat i komentáře, které začínají znakem „#ÿ a končí na konci řádku. Například program pro výpočet druhé mocniny čísla procesoru můžeme zapsat takto: id # Získáme identifikační číslo procesoru
- 1 1 # Vynásobíme ho sebou samým Instrukce je možné pojmenovat; stačí na začátek řádku připsat jméno následované znakem „:ÿ. Jméno může obsahovat písmena, číslice a podtržítka, nesmí se skládat jen z číslic. Jméno instrukce je pak možné použít místo jejího čísla: 10 procesor: id mocnina: * procesor procesor Stejné jméno můžete použít vícekrát, v tom případě jméno vždy označuje poslední přecházející takto pojmenovanou instrukci. Instrukce také může mít více jmen. Například program pro sečtení tří vstupů můžete zapsat takto: součet: const 0 vstup: input 1 součet: + součet vstup vstup: input 2 součet: + součet vstup vstup: input 3 součet: + součet vstup Příklad #1: hledání minima Každé jádro dostane jako vstup jedno číslo, každé jádro jiné. Jádro s nejmenším číslem by mělo mít výstup 1, ostatní jádra výstup 0. Řešení: vstup: input 1 sort vstup vstup_nalevo: left vstup
vstup_nalevo vstup Jádra seřadíme podle čísla na vstupu, čímž dostaneme jádro s nejmenším vstupem na začátek řady. Poté každé jádro zjistí, jestli má jádro nalevo od něj větší vstup než ono samo. Pokud tomu tak je, pak se musí nacházet na začátku řady, a tedy mít nejmenší vstup. Příklad #2: hledání duplikátů Každé jádro dostane jako vstup dvě čísla. Jádro musí odpovědět 1, pokud existuje jiné jádro se stejným vstupem, jinak musí odpovědět 0. Řešení: vstup_1: input 1 vstup_2: input 2 sort vstup_2 sort vstup_1 soused_1: left vstup_1 soused_2: left vstup_2 stejné_1: = soused_1 vstup_1 stejné_2: = soused_2 vstup_2 vlevo: & stejné_1 stejné_2 soused_1: right vstup_1 soused_2: right vstup_2 stejné_1: = soused_1 vstup_1 stejné_2: = soused_2 vstup_2 vpravo: & stejné_1 stejné_2 | vlevo vpravo 11 Jádra seřadíme nejprve podle druhého vstupu, poté podle prvního vstupu. Díky tomu, že třídění zachovává pořadí jader se stejným klíčem, budou nakonec jádra seřazená primárně podle prvního vstupu a sekundárně podle druhého vstupu (a terciárně podle identifikačního čísla). Jádra se stejnými vstupy tedy skončí u sebe. Poté stačí, aby se každé jádro podívalo na levého a pravého souseda, a zjistilo, jestli některý má stejný vstup.
- Assistant
Summary of the Problem:
Ondra, who failed an exam on sorting algorithms ten years ago, has developed a new model of a processor that can sort in constant time. This processor, called Ondra's processor, has the following characteristics:
-
Processor Structure:
- Contains N cores (processors), each with a unique identification number from 0 to N−1.
- Cores are arranged in a linear sequence (a row).
- Initially, cores are ordered by their identification numbers, with core 0 on the left.
- The order of the cores can change during the computation, especially when the
sortinstruction is used.
-
Program Execution:
- Programs consist of a sequence of instructions.
- All cores execute the same instruction simultaneously at each step.
- Each instruction computes a result, and each core remembers the results of all instructions it has executed so far.
-
Instruction Set:
- Arithmetic Operations:
+,-,*,/,% - Bitwise Operations:
|(OR),&(AND),^(XOR) - Comparison Operations:
=,!=,<,>,<=,>= - Conditional Selection:
if c a b(returnsaifcis non-zero, else returnsb) - Input and Constants:
const x: returns the constant valuex.id: returns the identification number of the core.input k: reads thek-th input of the core.
- Memory Access:
copy i: returns the result of instructioni.left i: returns the result of instructionifrom the core to the left.right i: returns the result of instructionifrom the core to the right.- The cores wrap around, so the "left" of the leftmost core is the rightmost core, and vice versa.
- Sorting:
sort i: reorders the cores based on the key valuer_i(the result of instructioni).- The core with the smallest key moves to the leftmost position.
- Sorting is stable: cores with equal keys maintain their relative order.
- Arithmetic Operations:
-
Programming Notes:
- Programs are written in text files, each instruction on a new line.
- Instructions can be named using labels (
label:) and referenced by name. - Comments start with
#and continue to the end of the line.
Examples Provided:
-
Finding the Minimum Input:
- Each core receives one input number.
- The goal is for the core with the smallest number to output
1, others output0. - Solution involves sorting the cores by their input and checking if a core is at the leftmost position.
-
Detecting Duplicates:
- Each core receives two input numbers.
- The goal is for cores to output
1if there exists another core with the same pair of inputs, else0. - Solution involves sorting cores first by the second input, then by the first input, and checking adjacent cores for duplicates.
Problem to Solve:
However, the problem description you've provided does not include a specific new task to solve beyond the examples given. To proceed, we need a clear statement of the problem or task that requires solving using Ondra's processor.
Next Steps:
Please provide the specific problem or task you would like to solve with Ondra's processor. Once we have the task, I can help develop a program using the given instruction set to achieve the desired outcome.
-