Teoria informacji/TI Ćwiczenia 12: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
 
Linia 3: Linia 3:
 
Druga zasada termodynamiki w fizyce brzmi następująco:
 
Druga zasada termodynamiki w fizyce brzmi następująco:
 
<center>''W układzie zamkniętym w dowolnym procesie entropia nigdy nie maleje.''</center>  
 
<center>''W układzie zamkniętym w dowolnym procesie entropia nigdy nie maleje.''</center>  
−
Pokażemy tutaj że jak prawo to wiąże się z pojęciami z teorii informacji.
+
Pokażemy tutaj, jak prawo to wiąże się z pojęciami z teorii informacji.
  
−
W mechanice statystycznej, entropia układu jest definiowana przy pomocy identycznego wzoru jak entropia Shannona, gdzie konkretnym wartościom zmiennej losowej odpowiadają pojedyncze mikrostany układu. Każdy mikrostan opisuje wszystkie parametry układu mające wpływ na jego dalszą ewolucję. Oznacza to że stan układu w przyszłości zależy wyłącznie od stanu aktualnego, niezależnie od tego w jaki sposób stan aktualny został uzyskany. Dzięki temu zachowanie układu izolowanego w czasie możemy modelować za pomocą łańcucha Markowa <math>X_0, X_1, \ldots</math>.  
+
W mechanice statystycznej, entropia układu jest definiowana przy pomocy identycznego wzoru jak entropia Shannona, gdzie konkretnym wartościom zmiennej losowej odpowiadają pojedyncze mikrostany układu. Każdy mikrostan opisuje wszystkie parametry układu mające wpływ na jego dalszą ewolucję. Oznacza to, że stan układu w przyszłości zależy wyłącznie od stanu aktualnego, niezależnie od tego, w jaki sposób stan aktualny został uzyskany. Dzięki temu zachowanie układu izolowanego w czasie możemy modelować za pomocą łańcucha Markowa <math>X_0, X_1, \ldots</math>.  
−
Okazuje się że entropia w takim modelu nie zawsze rośnie, ale można wskazać warunki dla których tak się dzieje.
+
Okazuje się, że entropia w takim modelu nie zawsze rośnie, ale można wskazać warunki dla których tak się dzieje.
  
  
 
{{cwiczenie|1 [Jednostajny rozkład stacjonarny]|jrs|
 
{{cwiczenie|1 [Jednostajny rozkład stacjonarny]|jrs|
−
Załóżmy że rozkład stacjonarny procesu Markowa jest jednostajny (prawdopodobieństwa wszystkich mikrostanów są równe).  
+
Załóżmy, że rozkład stacjonarny procesu Markowa jest jednostajny (prawdopodobieństwa wszystkich mikrostanów są równe).  
−
W takim przypadku cały układ dąży do stanu jednostajnego i jego entropia dąży do maksymalnej. Udowodnij że w takiej sytuacji dla dowolnego stanu początkowego <math>X_0</math> i dowolnej ilości kroków <math>n</math> zachodzi <math>H(X_{n+1}) \ge H(X_n)</math>.}}
+
W takim przypadku cały układ dąży do stanu jednostajnego i jego entropia dąży do maksymalnej. Udowodnij, że w takiej sytuacji dla dowolnego stanu początkowego <math>X_0</math> i dowolnej ilości kroków <math>n</math> zachodzi <math>H(X_{n+1}) \ge H(X_n)</math>.}}
  
  
 
{{cwiczenie|2 [Entropia przyszłości]|ew|
 
{{cwiczenie|2 [Entropia przyszłości]|ew|
−
Załóżmy że układ znajduje się w stanie stacjonarnym, a więc <math>H(X_n)</math> nie zmienia się w czasie. Udowodnij że <math>H(X_n|X_1)</math> rośnie razem z <math>n</math> (a więc przewidywanie przyszłości jest tym trudniejsze, im dalszą
+
Załóżmy, że układ znajduje się w stanie stacjonarnym, a więc <math>H(X_n)</math> nie zmienia się w czasie. Udowodnij, że <math>H(X_n|X_1)</math> rośnie razem z <math>n</math> (a więc przewidywanie przyszłości jest tym trudniejsze, im dalszą
 
przyszłość chcemy przewidzieć).}}
 
przyszłość chcemy przewidzieć).}}
  
Linia 24: Linia 24:
  
 
{{cwiczenie|4 [Strzałka czasu]|sc|
 
{{cwiczenie|4 [Strzałka czasu]|sc|
−
Niech <math>\{X_i\}_{i=-\infty}^{\infty}</math> będzie stacjonarnym procesem Markowa. Pokaż że  
+
Niech <math>\{X_i\}_{i=-\infty}^{\infty}</math> będzie stacjonarnym procesem Markowa. Pokaż, że  
 
<center><math>H(X_0|X_{-1},X_{-2}, \ldots, X_{-n})=H(X_0|X_1,X_2,\ldots,X_n)</math></center>
 
<center><math>H(X_0|X_{-1},X_{-2}, \ldots, X_{-n})=H(X_0|X_1,X_2,\ldots,X_n)</math></center>
−
Czyli mając dany stan układu w kolejnych krokach, równie trudno jest obliczyć stan układu w przyszłości, jak  
+
(Czyli że mając dany stan układu w kolejnych krokach, równie trudno jest obliczyć stan układu w przyszłości, jak  
 
jego stan w przeszłości.}}
 
jego stan w przeszłości.}}
  
  
 
{{cwiczenie|5 [Tasowanie kart]|tk|
 
{{cwiczenie|5 [Tasowanie kart]|tk|
−
Niech T oznacza tasowanie (permutację) talii kart, X oznacza początkowe ich ułożenie, a TX oznacza ułożenie kart po zaaplikowaniu tasowania T do X. Pokaż że jeśli wybór T i X jest niezależny, to  
+
Niech T oznacza tasowanie (permutację) talii kart, X oznacza początkowe ich ułożenie, a TX oznacza ułożenie kart po zaaplikowaniu tasowania T do X. Pokaż, że jeśli wybór T i X jest niezależny, to  
 
<center><math>H(TX) \ge H(X)</math></center>}}
 
<center><math>H(TX) \ge H(X)</math></center>}}

Aktualna wersja na dzień 10:58, 20 wrz 2006

Druga zasada termodynamiki

Druga zasada termodynamiki w fizyce brzmi następująco:

W układzie zamkniętym w dowolnym procesie entropia nigdy nie maleje.

Pokażemy tutaj, jak prawo to wiąże się z pojęciami z teorii informacji.

W mechanice statystycznej, entropia układu jest definiowana przy pomocy identycznego wzoru jak entropia Shannona, gdzie konkretnym wartościom zmiennej losowej odpowiadają pojedyncze mikrostany układu. Każdy mikrostan opisuje wszystkie parametry układu mające wpływ na jego dalszą ewolucję. Oznacza to, że stan układu w przyszłości zależy wyłącznie od stanu aktualnego, niezależnie od tego, w jaki sposób stan aktualny został uzyskany. Dzięki temu zachowanie układu izolowanego w czasie możemy modelować za pomocą łańcucha Markowa . Okazuje się, że entropia w takim modelu nie zawsze rośnie, ale można wskazać warunki dla których tak się dzieje.


Ćwiczenie 1 [Jednostajny rozkład stacjonarny]

Załóżmy, że rozkład stacjonarny procesu Markowa jest jednostajny (prawdopodobieństwa wszystkich mikrostanów są równe).

W takim przypadku cały układ dąży do stanu jednostajnego i jego entropia dąży do maksymalnej. Udowodnij, że w takiej sytuacji dla dowolnego stanu początkowego i dowolnej ilości kroków zachodzi .


Ćwiczenie 2 [Entropia przyszłości]

Załóżmy, że układ znajduje się w stanie stacjonarnym, a więc nie zmienia się w czasie. Udowodnij, że rośnie razem z (a więc przewidywanie przyszłości jest tym trudniejsze, im dalszą

przyszłość chcemy przewidzieć).


Ćwiczenie 3 [Entropia przyszłości - c.d.]

Znajdź przykład dla którego w nie zawsze rośnie razem z .


Ćwiczenie 4 [Strzałka czasu]

Niech będzie stacjonarnym procesem Markowa. Pokaż, że

(Czyli że mając dany stan układu w kolejnych krokach, równie trudno jest obliczyć stan układu w przyszłości, jak

jego stan w przeszłości.


Ćwiczenie 5 [Tasowanie kart]

Niech T oznacza tasowanie (permutację) talii kart, X oznacza początkowe ich ułożenie, a TX oznacza ułożenie kart po zaaplikowaniu tasowania T do X. Pokaż, że jeśli wybór T i X jest niezależny, to

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Teoria_informacji/TI_Ćwiczenia_12&oldid=54334”