Processing math: 100%
Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
1 beğenilme 0 beğenilmeme
1.3k kez görüntülendi

Soru: Hamming mesafesinin (distance) ucgen esitsizliginin sagladini gosteriniz?

Hammig mesafesi ne diyenler icin:

n basamakli (her basamagi sonlu bir cismin elemani olan) elemanlari iceren bir kod uzayimiz olsun. Buna C diyelim. xC elemanini x=x1x2xn  olarak yazalim. 

Diyelim ki x,yC olsun. Bu durumda  ikisi arasindaki Hamming mesafesini  d(x,y)=|{k|xiyi}| olarak tanimlayacagiz.

Bugun kodlama teorisi dersinde ogrencilerin cozmesi gereken sorulardan biri, burda da paylasayim dedim.

Akademik Matematik kategorisinde (25.6k puan) tarafından 
tarafından yeniden kategorilendirildi | 1.3k kez görüntülendi

kod uzayi nedir?

Hamming mesafesi ne diyenler için'den sonra başlayan ilk kısım.

Sonlu cisimlerin carpimi mi yani?

Evet. {(a1,a2,,an)|her 1in icin aiFq}.

Ogrencilerden biri olsaydim, kac puan almistim?

100 puanlık cevap, tabi 1 milyon üzerinden :)

1 cevap

2 beğenilme 0 beğenilmeme
En İyi Cevap
x,y,zC olsun. Gostermek istedigimiz d(x,y)d(x,z)+d(y,z) oldugu.
Oncelikle, ij farkli olmak uzere, iinci basamaktaki sayi ile jinci basamaktaki sayinin arasinda bir iliski olmadigini, bunlarin birbirinden bagimsiz oldugunu gozlemleyelim. 
Simdi, iki durumumuz var. Eger xi=yi ise bunun mesafeye bir etkisi olmuyor. Ama eger xiyi ise mesafe 1 artiyor.

Birinci durum: Eger xi=yi ise iki alt durum var:
  • xi=yi=zi: Bu durumda i koordinatinin katkisi d(x,y),d(x,z),d(y,z) mesafelerinin hepsi icin sifir.
  • xi=yizi: Bu durumda da i koordinatinin katkisi d(x,y) mesafesi icin sifir iken, d(x,z) ve d(y,z) mesafeleri icin bir.
Iki durumda da i koordinatinin etkisi azalmiyor.
Ikinci durum: Eger xiyi ise uc alt durum var:
  • xiyi=zi: Bu durumda i koordinatinin katkisi d(x,y) mesafesi icin bir, d(x,z) mesafesi icin bir, d(y,z) mesafesi icin ise sifir.
  • zi=xiyi: Bu durumda i koordinatinin katkisi d(x,y) mesafesi icin bir, d(x,z) mesafesi icin sifir, d(y,z) mesafesi icin bir.
  • xizi ve yizi: Bu son durumda ise i koordinatinin katkisi d(x,y),d(x,z),d(y,z) mesafelerinin hepsi icin bir.
Goruldugu gibi uc durumda da i koordinatinin etkisi azalmiyor.
Teker teker her koordinat icin, bu koordinatlarin katkilari azalmiyorsa; koordinatlarin katkisi bagimsiz oldugundan, bu katkilari topladigimizda toplam katki da azalmaz. Bu da ucgen esitligini kanitlamis olur.

Ayrica, bu mesafenin simetrik oldugu - yani d(x,y)=d(y,x) oldugu - bariz. Her x,yC icin d(x,y)0 ve d(x,x)=0 oldugu da ayni sekilde bariz.
(2.5k puan) tarafından 
tarafından seçilmiş

Aslinda bi nevi tumevarim. Sadece n=1 icin ispatlamak bile yetiyor, ki burda da aslinda n=1 icin ispat var.

Ayrica kumelerdeki simetrik farki kullanarak da ispatlanabiliyor. Belki dusunmek isteyenler olur diye yaziyorum. 

xiyi ise zi en cok biri ile ayni olabilir sadece. Aslinda bu ispati bitiren cumle. "Her farka en az bir fark geliyor" diyoruz.

Bunu kumelerdeki simetrik farkini kullanarak ucgen esitsizligini gosterebiliriz. Tabi soyle genis acidan bakinca bu da ayni olaya, mantiga denk geliyor.

20,333 soru
21,889 cevap
73,624 yorum
3,084,283 kullanıcı