Deep Dive
рд░рд┐рд▓реЗрд╢рди рдХреНрдпрд╛ рд╣реИ рдФрд░ рдХреИрд╕реЗ рдмрдирддрд╛ рд╣реИ
рджреАрдкрдХ рд╕рд░ рдиреЗ рд╢реБрд░реБрдЖрдд рдореЗрдВ рдмрд╣реБрдд рд╕рд░рд▓ рддрд░реАрдХреЗ рд╕реЗ рд╕рдордЭрд╛рдпрд╛ рдХрд┐ рд░рд┐рд▓реЗрд╢рди рдХреНрдпрд╛ рд╣реЛрддрд╛ рд╣реИред рдЙрдиреНрд╣реЛрдВрдиреЗ рдПрдХ рд╕реЗрдЯ A = {1,2,3,4,5} рд▓рд┐рдпрд╛ рдФрд░ рдХрд╣рд╛ рдХрд┐ рджреЛ рдПрд▓рд┐рдореЗрдВрдЯреНрд╕ рдХреЛ рдЗрд╕ рддрд░рд╣ рдЪреБрдиреЛ рдХрд┐ рдЙрдирдХрд╛ рдпреЛрдЧ 4 рд╣реЛред рдЗрд╕рдХреЗ рдмрд╛рдж (1,3), (2,2), (3,1) рдпреЗ рдкреЗрдпрд░реНрд╕ рдирд┐рдХрд▓ рдХрд░ рдЖрддреЗ рд╣реИрдВред рджреАрдкрдХ рд╕рд░ рдиреЗ рдЬреЛрд░ рджреЗрддреЗ рд╣реБрдП рд╕рдордЭрд╛рдпрд╛ рдХрд┐ рд░рд┐рд▓реЗрд╢рди рд╕рд┐рд░реНрдл рдПрдХ рдХрдВрдбреАрд╢рди рджреЗрдирд╛ рд╣реИ рдФрд░ рдЙрд╕рдХреЗ рдмрд╛рдж рдЬреЛ рднреА рдкреЗрдпрд░реНрд╕ рдЙрд╕ рдХрдВрдбреАрд╢рди рдХреЛ рд╕реЗрдЯрд┐рд╕реНрдлрд╛рдИ рдХрд░реЗрдВ, рд╡рд╣реА рдЖрдкрдХрд╛ рд░рд┐рд▓реЗрд╢рди рдмрди рдЬрд╛рддрд╛ рд╣реИред рдпрд╣ рдХрд╛рдВрд╕реЗрдкреНрдЯ рдмрд╣реБрдд рдмреЗрд╕рд┐рдХ рд╣реИ рд▓реЗрдХрд┐рди рдкреВрд░реЗ рдЪреИрдкреНрдЯрд░ рдХреА рдиреАрдВрд╡ рд╣реИред рдЙрдиреНрд╣реЛрдВрдиреЗ рдпрд╣ рднреА рд╕рдордЭрд╛рдпрд╛ рдХрд┐ рд░рд┐рд▓реЗрд╢рди рдХреЛ рд╕реЗрдЯ рдмрд┐рд▓реНрдбрд░ рдлреЙрд░реНрдо рд╕реЗ рд░реЛрд╕реНрдЯрд░ рдлреЙрд░реНрдо рдореЗрдВ рдХреИрд╕реЗ рдХрдиреНрд╡рд░реНрдЯ рдХрд░рддреЗ рд╣реИрдВред
рдбреЛрдореЗрди, рд░реЗрдВрдЬ рдФрд░ рдХреЛрдбреЛрдореЗрди рдХреА рд╕рдордЭ
рджреАрдкрдХ рд╕рд░ рдиреЗ рддреАрди рд╕рдмрд╕реЗ рдорд╣рддреНрд╡рдкреВрд░реНрдг рдХрд╛рдВрд╕реЗрдкреНрдЯ рд╕рдордЭрд╛рдП: рдбреЛрдореЗрди, рд░реЗрдВрдЬ рдФрд░ рдХреЛрдбреЛрдореЗрдиред рдбреЛрдореЗрди рдореЗрдВ рд░рд┐рд▓реЗрд╢рди рдХреЗ рд╕рднреА рдкрд╣рд▓реЗ рдПрд▓рд┐рдореЗрдВрдЯреНрд╕ рдЖрддреЗ рд╣реИрдВред рдЕрдЧрд░ рд░рд┐рд▓реЗрд╢рди рдореЗрдВ (1,3), (2,2), (3,1) рд╣реИ рддреЛ рдбреЛрдореЗрди = {1,2,3}ред рд░реЗрдВрдЬ рдореЗрдВ рджреВрд╕рд░реЗ рдПрд▓рд┐рдореЗрдВрдЯреНрд╕ рдЖрддреЗ рд╣реИрдВ рдпрд╛рдиреА {1,2,3}ред рдХреЛрдбреЛрдореЗрди рд╡рд╣ рд╣реИ рдЬреЛ рд╢реБрд░реБрдЖрдд рдореЗрдВ рджрд┐рдпрд╛ рдЧрдпрд╛ рдерд╛, рдпрд╛рдиреА рдкреВрд░рд╛ рд╕реЗрдЯ A = {1,2,3,4,5}ред рджреАрдкрдХ рд╕рд░ рдиреЗ рдмрд╛рд░-рдмрд╛рд░ рдХрд╣рд╛ рдХрд┐ рдЗрди рддреАрдиреЛрдВ рдореЗрдВ рдЕрдВрддрд░ рд╕рдордЭрдирд╛ рдмрд╣реБрдд рдЬрд░реВрд░реА рд╣реИ рдХреНрдпреЛрдВрдХрд┐ рдкрд░реАрдХреНрд╖рд╛ рдореЗрдВ рдЗрдиреНрд╣реАрдВ рдХреЛ рд▓реЗрдХрд░ рд╕рд╡рд╛рд▓ рдЖрддреЗ рд╣реИрдВред
рд░рд┐рд▓реЗрд╢рди рдХреЗ рд╡рд┐рднрд┐рдиреНрди рдкреНрд░рдХрд╛рд░
рджреАрдкрдХ рд╕рд░ рдиреЗ рдкрд╛рдВрдЪ рдореБрдЦреНрдп рдкреНрд░рдХрд╛рд░ рдХреЗ рд░рд┐рд▓реЗрд╢рди рд╕рдордЭрд╛рдП: рдПрдореНрдкреНрдЯреА рд░рд┐рд▓реЗрд╢рди (рдЬрд┐рд╕рдореЗрдВ рдХреЛрдИ рдПрд▓рд┐рдореЗрдВрдЯ рдирд╣реАрдВ), рдпреВрдирд┐рд╡рд░реНрд╕рд▓ рд░рд┐рд▓реЗрд╢рди (рдЬрд┐рд╕рдореЗрдВ рд╕рднреА рдкреЗрдпрд░реНрд╕ рд╣реЛрдВ), рдЖрдЗрдбреЗрдВрдЯрд┐рдЯреА рд░рд┐рд▓реЗрд╢рди (рд╕рд┐рд░реНрдл рдбрдмрд▓реЗрдЯреНрд╕), рд░рд┐рдлреНрд▓реЗрдХреНрд╕рд┐рд╡ (рд╕рднреА рдбрдмрд▓реЗрдЯреНрд╕ рдЕрдирд┐рд╡рд╛рд░реНрдп), рдФрд░ рд╕рд┐рдореЗрдЯреНрд░рд┐рдХ (рдЕрдЧрд░ ab рд╣реИ рддреЛ ba рднреА рд╣реЛрдирд╛ рдЪрд╛рд╣рд┐рдП)ред рд╣рд░ рдкреНрд░рдХрд╛рд░ рдХреЛ рд╕рдордЭрд╛рддреЗ рд╕рдордп рд╕рд░ рдиреЗ рд╕реНрдкрд╖реНрдЯ рдЕрдВрддрд░ рджрд┐рдЦрд╛рдпрд╛ред рдЙрджрд╛рд╣рд░рдг рдХреЗ рд▓рд┐рдП рдЙрдиреНрд╣реЛрдВрдиреЗ рдХрд╣рд╛ рдХрд┐ рдЖрдЗрдбреЗрдВрдЯрд┐рдЯреА рдХреЗрд╡рд▓ рд╕реЗрд▓реНрдл рд▓рд╡рд░ рд╣реИрдВ рдЬреЛ рд╕рд┐рд░реНрдл рдЕрдкрдиреЗ рдЖрдк рд╕реЗ рдкреНрдпрд╛рд░ рдХрд░рддреЗ рд╣реИрдВ, рд▓реЗрдХрд┐рди рд░рд┐рдлреНрд▓реЗрдХреНрд╕рд┐рд╡ рдЬреНрдпрд╛рджрд╛ рдореЙрдбрд░реНрди рд╣реИрдВ рдЬреЛ рдЕрддрд┐рд░рд┐рдХреНрдд рд░рд┐рд▓реЗрд╢рдиреНрд╕ рднреА рд░рдЦ рд╕рдХрддреЗ рд╣реИрдВред рдЯреЛрдЯрд▓ рд░рд┐рдлреНрд▓реЗрдХреНрд╕рд┐рд╡ рд░рд┐рд▓реЗрд╢рдиреНрд╕ рдХрд╛ рдлреЙрд░реНрдореВрд▓рд╛ 2^(n*(n-1)) рд╣реИред
рдЯреНрд░рд╛рдВрдЬрд┐рдЯрд┐рд╡ рдФрд░ рдЗрдХреНрд╡рд┐рд╡реЗрд▓реЗрдВрд╕ рд░рд┐рд▓реЗрд╢рди
рджреАрдкрдХ рд╕рд░ рдиреЗ рдХрд╣рд╛ рдХрд┐ рдЯреНрд░рд╛рдВрдЬрд┐рдЯрд┐рд╡ рдЙрдирдХрд╛ рдкрд╕рдВрджреАрджрд╛ рд░рд┐рд▓реЗрд╢рди рд╣реИ рдХреНрдпреЛрдВрдХрд┐ рдпрд╣ рдХреБрдЫ рд╡рд┐рд╢реЗрд╖ рдирд┐рдпрдо рдХреЗ рд╕рд╛рде рдХрд╛рдо рдХрд░рддрд╛ рд╣реИред рдЙрдиреНрд╣реЛрдВрдиреЗ рд╕рдордЭрд╛рдпрд╛ рдХрд┐ рдЕрдЧрд░ (a,b) рдФрд░ (b,c) рджреЛрдиреЛрдВ рд░рд┐рд▓реЗрд╢рди рдореЗрдВ рд╣реИрдВ рддреЛ (a,c) рднреА рд╣реЛрдирд╛ рдЪрд╛рд╣рд┐рдПред рд▓реЗрдХрд┐рди рдПрдХ рдорд╣рддреНрд╡рдкреВрд░реНрдг рджреВрд╕рд░реА рдХрдВрдбреАрд╢рди рд╣реИ: рдЕрдЧрд░ ab рд╣реИ рд▓реЗрдХрд┐рди b рд╕реЗ рд╢реБрд░реВ рд╣реЛрдиреЗ рд╡рд╛рд▓рд╛ рдХреЛрдИ рдЕрдиреНрдп рдкреЗрдпрд░ рд╣реА рдирд╣реАрдВ рд╣реИ рддреЛ рднреА рдпрд╣ рдЯреНрд░рд╛рдВрдЬрд┐рдЯрд┐рд╡ рдорд╛рдирд╛ рдЬрд╛рддрд╛ рд╣реИред рдЗрдХреНрд╡рд┐рд╡реЗрд▓реЗрдВрд╕ рд░рд┐рд▓реЗрд╢рди рддреАрдиреЛрдВ рдЪреАрдЬреЗрдВ рдПрдХ рд╕рд╛рде рд╣реИ: рд░рд┐рдлреНрд▓реЗрдХреНрд╕рд┐рд╡, рд╕рд┐рдореЗрдЯреНрд░рд┐рдХ рдФрд░ рдЯреНрд░рд╛рдВрдЬрд┐рдЯрд┐рд╡ред рджреАрдкрдХ рд╕рд░ рдиреЗ рдХрд╣рд╛ рдХрд┐ рдЗрдХреНрд╡рд┐рд╡реЗрд▓реЗрдВрд╕ рд░рд┐рд▓реЗрд╢рди рдХреА рд╕рдВрдЦреНрдпрд╛ рдмреЗрд▓ рдирдВрдмрд░реНрд╕ рд╕реЗ рдирд┐рдХрд▓рддреА рд╣реИ рдЬреЛ рдПрдХ рд╡рд┐рд╢реЗрд╖ рд╕реАрдХреНрд╡реЗрдВрд╕ рдХрд╛ рдЕрдиреБрд╕рд░рдг рдХрд░рддреЗ рд╣реИрдВред
рдкреНрд░реИрдХреНрдЯрд┐рдХрд▓ рд╕рд╡рд╛рд▓ рдФрд░ рд╢реЙрд░реНрдЯрдХрдЯ рддрд░реАрдХреЗ
рдореИрд░рд╛рдерди рдХреЗ рджреМрд░рд╛рди рджреАрдкрдХ рд╕рд░ рдиреЗ рдХрдИ рдкреНрд░реИрдХреНрдЯрд┐рдХрд▓ рд╕рд╡рд╛рд▓ рдХрд┐рдП рдФрд░ рд╕реНрдЯреВрдбреЗрдВрдЯреНрд╕ рдХреЛ рдкреЛрд▓реНрд╕ рдХреЗ рдорд╛рдзреНрдпрдо рд╕реЗ рд╕рд╣реА рдЬрд╡рд╛рдм рджрд┐рд▓рд╡рд╛рдПред рдЙрдиреНрд╣реЛрдВрдиреЗ рдмрддрд╛рдпрд╛ рдХрд┐ рд╕реЗрдЯ рдмрд┐рд▓реНрдбрд░ рдлреЙрд░реНрдо рд╡рд╛рд▓реЗ рд╕рд╡рд╛рд▓реЛрдВ рдореЗрдВ рдкрд╣рд▓реЗ рд░рд┐рд▓реЗрд╢рди рдХреЛ рд░реЛрд╕реНрдЯрд░ рдлреЙрд░реНрдо рдореЗрдВ рд▓рд┐рдЦрдирд╛ рдЪрд╛рд╣рд┐рдПред рдПрдХ рдорд╣рддреНрд╡рдкреВрд░реНрдг рдЯреНрд░рд┐рдХ рджреА: рд░рд┐рдлреНрд▓реЗрдХреНрд╕рд┐рд╡ рдЪреЗрдХ рдХрд░рдиреЗ рдХреЗ рд▓рд┐рдП рджреЛрдиреЛрдВ рдЬрдЧрд╣ рд╕рдорд╛рди рдирдВрдмрд░ рдбрд╛рд▓реЛ, рд╕рд┐рдореЗрдЯреНрд░рд┐рдХ рдХреЗ рд▓рд┐рдП ab рдХрд╛ ba рджреЗрдЦреЛ, рдФрд░ рдЯреНрд░рд╛рдВрдЬрд┐рдЯрд┐рд╡ рдХреЗ рд▓рд┐рдП рдЪреЗрди рд░реВрд▓ рд▓рдЧрд╛рдУред рдЙрдиреНрд╣реЛрдВрдиреЗ рд╕реНрдЯреНрд░реЗрд╕ рдХрд┐рдпрд╛ рдХрд┐ рдХреЛрдИ рднреА рдХреИрд▓рдХреБрд▓реЗрд╢рди рдпрд╛ рдлреЙрд░реНрдореВрд▓рд╛ рдирд╣реАрдВ рд╣реИ, рд╕рд┐рд░реНрдл рд▓реЙрдЬрд┐рдХ рдФрд░ рдСрдмреНрдЬрд░реНрд╡реЗрд╢рди рд╣реИред рд╕реНрдЯреВрдбреЗрдВрдЯреНрд╕ рдХреЛ рдкреНрд░реЛрддреНрд╕рд╛рд╣рд┐рдд рдХрд░рддреЗ рд╣реБрдП рд╕рд░ рдиреЗ рдХрд╣рд╛ рдХрд┐ рдЗрди рд╕рд╡рд╛рд▓реЛрдВ рдореЗрдВ рдЬреАрд░реЛ рдирдВрдмрд░ рдирд╣реАрдВ рдЖрдПрдВрдЧреЗ, рдХреБрдЫ рддреЛ рдЕрд╡рд╢реНрдп рдорд┐рд▓реЗрдВрдЧреЗред