#kaykobad | Explore Tumblr posts and blogs

yugopk · 5 years ago

Text

Top-Rated Tourist Attractions in Konya

The important place of religious pilgrimage in Konya has a city center filled with museums and monuments of Seljuk splendor. Most tourists stop here just to see the Mevlana Museum and the tomb of the founder of the whirling dervish Mevlana Rumi, who wrote his famous poetry here in the 13th century.

But this central Anatolian city is also full of architectural attractions of mosques and old madrassas (schools of theology) which highlight the artistic talent of the Seljuk sultanate. Anyone interested in the history of Turkey should not miss a visit here. Discover the best places to visit with our list of the best tourist attractions in Konya.

Tile Museum (Karatay Medresesi)

This old madrassa (theological college) was founded in 1251 by the Seljuk emir Celaleddin Karatay. The building was recently restored and is now an impressive museum with Seljuk enamel tiles.

While visiting a tile museum may seem like a rather niche tourist attraction, the sheer beauty of the building makes it one of the best things to do on a Konya sightseeing itinerary. Its interior walls are covered with magnificent examples of Seljuk tiles and there are also ceramic exhibits of excavated finds from nearby archaeological sites. In the room on the left is the tomb of Celaleddin Karatay.

Mevlana Museum

The symbol of Konya is this complex tekke (Sufi lodge) that contains the tomb of the religious leader, philosopher and poet of the thirteenth century Mevlana Celaleddin Rumi, who founded the dervish sect of Sufism. The museum is located in lovingly maintained rose gardens, through which you walk to the ornate Dervisan Kapisi (Dervish Gate).

Once inside the complex, you enter the Mausoleum, which is the focus of much devotional worship to this day. Mevlana's tomb is at the other end, flanked by graves of close relatives and followers. The Semahane (hall where dervish ceremonies were held) is on the left and contains a museum of religious exhibitions.

Across the courtyard of the Mausoleum is the kitchen of the lodge, which contains dioramas of dervish life and is connected to Dervish Cells, where the Sufi followers would have lived and now contain exhibits on dervish life.

Koyunoglu Museum

Avid collector Ahmet Izzet Koyunoglu, a member of one of Konya's oldest families, bequeathed his strange and eccentric collection of artifacts, art, ethnography objects, geological items and simple things, to the city of Konya when he died.

The museum that resulted from this has to be the most peculiar view of the city. The building is a treasure trove of scattered, strange and wonderful exhibits ranging from rare paintings, manuscripts and carpets to stuffed animals and watches. For anyone who appreciates the slightly eccentric, this is a wonderful accompaniment to the city's most traditional attractions.

Museum of Wooden and Stone Carving (Ince Minare Medrese)

The Ince Minareli Medrese (Seminary of the Slim Minaret) lost the minaret in its name when it was struck by lightning in 1905. The madrassa was built in 1260 for the vizier Seljuk Sahip Ata, and the design presents a richly sculpted decoration on the portal. The building is now a museum, with a large collection of wood and stone sculptures from the Seljuk era that include animal reliefs (despite representations of animals and humans prohibited by Islamic law) from the city's ancient walls.

Archaeological Museum

Most of the archeology museums in Turkey have been modernized and modernized in the last decade, but not the Konya museum. This is an old and dusty place with poor lighting and information panels that can also be obsolete. But don't let that put you off, because the collection is excellent (and if you like these relic museums with their treasure-seeking atmosphere, go now before you get your much-needed face wash). There is a complete sample of findings from the nearby archaeological site of Çatalhöyük and a wonderful collection of intricately decorated Roman sarcophagi.

Right at the end of the road is the Konya Museum of Ethnography, which has a complete collection of Turkish crafts, costumes, jewelry, carpets and household items, but unfortunately it looks a bit dusty and loveless.

Alaeddin Tepe

Built on the site of the ancient citadel of Konya, this park, right in the city center, is where the inhabitants of Konya come to walk in the evening and sip tea in the gardens. At the foot of the slope of the hill are the excavation site of the palace of Alaeddin Kaykobad and the remains of the old city wall. At the top of the hill is the Alaeddin Camii, built in the 13th century. It was built as a mosque with columns according to the Arab design, with a wooden ceiling supported by 42 ancient columns.

Selimiye Mosque

Standing on the square opposite the Mevlana museum, this immense dome-shaped mosque, commissioned by Sultan Selim II and built between 1566 and 1574, marked the height of the architecture of the Ottoman mosque. Head to the square in the early evening to take photos of the mosque and the Mevlana museum behind, lit up against the twilight sky. Across the main road from the square are a series of outdoor cafes and restaurants, which are a great place to sit and admire the view of minarets and domes while relaxing with coffee or tea.

Çatalhöyük

Although there are not huge amounts to see, the Çatalhöyük settlement mound is one of the most important excavation sites in the world. Here, archaeologists have discovered the largest Neolithic site ever found, with a colony dating from around 9,000 years ago. Excavations are in progress, and if you visit in the summer, you can sometimes observe archaeologists working on the site.

A magnificent small museum at the entrance explains the history of the excavations and the importance of the site. From there, a path leads you to the twin excavation areas (protected under domed shelters), where you can see the deep levels, with clear construction outlines, which have been discovered so far.

Sille

Nice as a button, the ancient Greek settlement of Sille is a small town on the outskirts of the city and a favorite destination for the locals of Konya. Here are two Byzantine churches: Saint Helena and Küçük Kilise, both recently restored.

The church of Santa Elena has an interior covered with colorful frescoes, while the small Küçük Kilise, on the hill behind the town, now functions as a museum dedicated to watches and other watches. The town's streets are lined with beautiful wooden beamed houses, while the cliff ridge is marked with old cave dwellings.

Aziziye Mosque

Within the bustling bazaar district of Konya, the Aziziye Mosque is ideal for fans of architecture. It was first built in 1676 by the Ottoman court advisor Mustafa Pasa and rebuilt again in 1867 after a fire. Due to this restoration of the 19th century, the architecture of the mosque is strongly inspired by the Baroque (the most fashionable style at that time), with twin minarets in Rococo style and a brightly painted interior with a rococo prayer niche. This very European decorative style makes an interesting contrast to the traditional design of the mosque.

Sahib-i Ata Külliyesi

This religious complex comprises a mosque, dervish hut, türbe and baths and was built between 1258 and 1283. The door of the portal, grandly decorated, is beautifully decorated, and the interior of the mosque has a beautiful prayer niche of blue tiles. The dervish hut, with its beautifully restored interior of blue tiles and red bricks, has become a museum with an interesting collection of religious artifacts.

On the way to the mosque you will pass by Sirçali Medresi. Built in 1242, this ancient theological school has some beautiful (but crumbling) examples of tile decoration on its interior walls and an ornate stalactite portal. It houses a collection of Islamic gravestones, as well as some Hittite funeral urns.

Konya Mosques

The central city is full of other well-preserved examples of religious architecture. In particular, do not miss the yarn manufacturers' mosque (Iplikçi Camii) on Alaeddin Caddesi. Only the mosque of this religious complex, built in 1201, which was to the east of the ancient citadel of Konya, remains.

The site was initially endowed with a family of manufacturers of threads, hence its name. The square building has two oval and one round domes, and stands on twelve enormous "elephant feet" columns, with a prayer niche richly decorated in marble. Mevlana and her father taught here.

The tower mosque in the bazaar is also worth a hunt. It was built in 1658, but after falling into disrepair was rebuilt in 1811. The roof of the eight-domed mosque is supported by 10 pillars, and a collection of 14th and 15th century clothing can be found in one room inside the building.

Top Reasons Why Visiting Turkey In Winters Is A Great Idea!

Turkey Travel Guide

9 Things Not To Be Missed in Istanbul

Turkey Tour Packages from Pakistan

25 Most Stunning Landscapes Around The World That Fit Every Travelers List

Turkey Food and Visit Guid

#Konya Mosques #Sahib-i Ata Külliyesi #Aziziye Mosque #Sille #Çatalhöyük #Selimiye Mosque #Alaeddin Tepe #Archaeological Museum #Mevlana Museum

1 note · View note

shiho-elliptic · 6 years ago

Text

Segment Tree

Edited (2019/09/21 02:45): $$build(\alpha)$$, Monoidの定義 (Thanks @a3VtYQo) Edited (2019/09/22 08:06): 出典等追記.

一定の理解度を得ることができた気がしたので, 一通りまとめた. なお, この記事は問題を解くために書かれたものではなく, 純粋にSegment Treeというデータ構造に関して書かれていてほしい内容をすべて説明した記事というのがどこにもなかったために書かれたものである.

概要

なぜか誰も擬似コードの形ではこれを書いていなかったのでそれで書く. C++コードが競技プログラミングの世界では主流のようだが, アルゴリズムだけ知りたいときにはやはり擬似コードぐらいの抽象度まで上げてよいと思う (主観).

現状Lazy-Propagationな場合については触れていないが, 今後追記する予定である.

本記事に載っているアルゴリズムは主に[1]を読んだ結果と[2], [9]のものを参考としている. また, 理論的背景に関しては[1], [3], [4], [5], [6], [7], [8], [9]の内容をもとに考察した結果である. [11]も読むには読んだが, 問題を解くだけならいいけども理論的背景はほぼ知れなかった. [12]は解説資料としては良いが理論的背景に関しては物足りない感じがある. 他には[13], [14]を参考資料として読んでいた.

仮定

要素数は必ず$$N := 2^k$$で表されると仮定する1. [3]で触れられている通りこれは圏として考えられる(totalityが実際には不要)わけだが, 自分の圏に対する理解が進んでいないことから, 本記事ではMonoidを使用したものを考える.

Monoidの定義: 集合$$T$$, 二項演算 $$f: T\times T\rightarrow T$$, ある$$e\in T$$について, 以下条件が成立しているとき, $$(T, f, e)$$をMonoidという:

$$\forall x\in T$$, $$f(x, e) = f(e, x) = x$$ (Identity Element)

$$x, y, z\in T$$, $$f(f(x, y), z) = f(x, f(y, z))$$ (Associativity)

例えば, 自然数全体の集合に0を付け加えた集合$$\mathbb{N} _ 0 = \mathbb{N}\cup\lbrace 0\rbrace$$は$$(\mathbb{N} _ 0, +, 0)$$とすればMonoidになる. また, $$(\mathbb{N}, \cdot, 1)$$もMonoidである. 本記事ではそれぞれ名前を付けているが, 一般的には, コンテクストが明瞭な場合にしばしば集合の記号を指してMonoidということがある. e.g. 「Monoid $$\mathbb{N} _ 0$$について〜」.

構造

木構造, 特に完全二分木. ただし, 根に区間$$\lbrack 1, N\rbrack$$, 深さ1の2頂点にはそれぞれ$$\left\lbrack 1, \frac{N}{2}\right\rbrack$$, $$\left\lbrack \frac{N}{2} + 1, N\right\rbrack$$の区間を割り当てる. 同様に深さ$$\ell$$の頂点には長さ$$\frac{N}{2^{\ell}}$$の区間を割り当てていく2.

深さ$$\ell$$の頂点に割り当てられる区間の和集合をとると$$\lbrack 1, N\rbrack$$に等しい. このことから深さ$$\ell$$にある頂点は深さ$$\ell-1$$にある頂点の半分の区間を持つという, いわば「カバー範囲」を半分ずつとる構造をしていることがわかる. この点から, Segment Treeは二分探索木のように見ることができる.

蛇足

Segment Treeはデータ構造であり, 構造以上のものではない. このため, 「Segment Treeを利用するアルゴリズム」はSegment Treeとは別個に語られるべきものである. いわば次節に示されている「Segment Treeにより区間演算が$$O(\log N)$$で可能である」という事実は単なるおまけである. 本質的なデータ構造としては区間の割当であり, 区切られた(Segment)木である.

アルゴリズム

本節においては, Segment Treeを応用した点代入・区間クエリアルゴリズムを示す. 前述の通り[1], [2], [9]を参考にしているが, 擬似コードとして書き直す段階でかなり書き直しをしている. また, これまでは閉区間を扱っていたが, 条件式が簡単になる都合から半開区間で考える.

Notation

$$\mathcal{M} = (T, f, e)$$: Monoid

二分木の葉: $$\mathrm{leaf}\lbrack 1\rbrack, \ldots, \mathrm{leaf}\lbrack N\rbrack$$

二分木の頂点$$v$$の子頂点, 親頂点, 値: $$(v.left, v.right)$$, $$v.parent$$, $$v.value$$

二分木の根: $$\mathrm{root}$$

構築($$build(\alpha)$$)

入力: 初期値 $$\alpha\in T$$

Let $$Q$$ be a FIFO queue

For $$i = 1, \ldots, N$$

$$\mathrm{leaf}[i].value \leftarrow \alpha$$

If $$(i\bmod 2) = 1$$:

$$\mathrm{Enqueue\ } \mathrm{leaf}[i].parent \mathrm{\ to\ } Q$$

End If

End For

While $$Q\ne\emptyset$$:

$$v\leftarrow \mathrm{Dequeue\ from\ } Q$$

$$v.value = f(v.left.value, v.right.value)$$

If $$v \ne \mathrm{root}$$:

If $$v.parent.left = v$$:

$$\mathrm{Enqueue\ } v.parent \mathrm{\ to\ } Q$$

End If

End While

計算量: $$O(N)$$

すべての葉の値を$$\alpha$$で初期化する. 実装上はMonoidのIdentity Element $$e$$で初期化することが多いだろう.

このアルゴリズムはすべての頂点を葉から根へ幅優先で回る. 葉が$$N = 2^k$$個ある完全二分木なので, 全体の頂点数は$$1 + 2 + 2^2 + \cdots + 2^{k-1} + 2^k = 2^{k+1} - 1 = 2N - 1$$. ゆえに$$O(N)$$ (キューの処理時間は無視).

4.2行目の計算は$$\mathcal{M}$$のAssociativityにより正しく計算することができることが保証される.

更新($$update(i, v)$$)

入力: 葉の位置 $$i\in\lbrack 1, N+1)$$, 代入値$$v\in T$$

$$\mathrm{leaf}.value\lbrack i\rbrack \leftarrow v$$

$$c\leftarrow i$$

While $$c \ne \mathrm{root}$$:

$$c\leftarrow c.parent$$

$$c.value \leftarrow f(c.left.value, c.right.value)$$

End While

計算量: $$O(\log N)$$

$$\mathrm{leaf}\lbrack i\rbrack.value$$に$$v$$を代入する.

3.2行目の計算は$$\mathcal{M}$$のAssociativityにより正しく計算することができることが保証される.

クエリ($$query(\lbrack l, r))$$)

入力: 葉の区間 $$\lbrack l, r)$$

Return $$vertex\_query(\lbrack l, r), \mathrm{root}, \lbrack 1, N + 1))$$

計算量: $$O(\log N)$$

区間$$\lbrack l, r)$$について, $$f(\mathrm{leaf}\lbrack l\rbrack.value, f(\mathrm{leaf}\lbrack l+1\rbrack.value, f(\cdots, f(\mathrm{leaf}\lbrack r-2\rbrack.value, \mathrm{leaf}\lbrack r-1\rbrack.value)\cdots)))$$を計算する.

頂点指定クエリ ($$vertex\_query(\lbrack l, r), v, \lbrack a, b))$$)

入力: 葉の区間$$\lbrack l, r)$$, 現在見ている頂点$$v$$, 現在見ている頂点に割り当てられている区間 $$\lbrack a, b)$$

If $$r\leq a\lor b\leq l$$:

Return $$e$$

Else If $$a\leq l\land r\leq b$$:

Return $$v.value$$

End If

$$t_a\leftarrow vertex\_query\left(\lbrack l, r), v.left, \left\lbrack l, \frac{l + r}{2}\right)\right)$$

$$t_b\leftarrow vertex\_query\left(\lbrack l, r), v.right, \left\lbrack \frac{l + r}{2}, r\right)\right)$$

Return $$f(t_a.value, t_b.value)$$

計算量: $$O(\log N)$$

ある頂点$$v$$よりも下にある頂点から, $$\lbrack l, r)$$とオーバーラップしている部分の演算値を計算する.

6行目の計算は$$\mathcal{M}$$のAssociativityにより正しく計算することができることが保証される.

Conclusion

Segment Treeとは各頂点に区間を割り当てられた完全二分木である. その上にはMonoidによる演算を乗せることができ, その構造をうまく使うことで点代入・区間クエリを$$O(\log N)$$で処理することができる.

References

Jon Louis Ventley and Derick Wood. 1980. An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles.

秋葉拓哉. 2010. プログラミングコンテストでのデータ構造.

セグメント木の上に乗る構造はモノイドではなく圏である - うさぎ小屋

遅延伝搬segment木についてもっと詳しく - うさぎ小屋

Segment木の種類とその要件 - うさぎ小屋

双対セグメント木という概念について - うさぎ小屋

完全二分木への添字付けであってセグメント木ではないものを考える - うさぎ小屋

/segment tree - wiki.kimiyuki.net

セグメント木について - beet's soil

遅延伝播セグメント木について (旧: 遅延評価セグメント木について) - beet's soil

秋葉拓哉, 岩田陽一, and 北川宜稔. 2010. プログラミングコンテストチャレンジブック

Bowen Yu. 2016. The Art of Divide-And-Conquer

Nabil Ibtehaz, M. Kaykobad, and M. Sohel Rahman. 2018. Multidimensional segment trees can do range queriesand updates in logarithmic time

Pushkar Mishra. 2016. A New Algorithm for Updating and QueryingSub-arrays of Multidimensional Arrays

一般の$$N$$についても$$N\leq 2^k$$なる$$k$$を探し, 余った領域はIdentity Elementで埋めることでこの場合に帰着できる. ↩︎

[7]では添字が本質的という仮定を置いているが, それと自分の主張である「各頂点に割り当てられる区間が本質的」という主張は同値. これは, 添字割当の結果と区間割当の結果がそれぞれ一対一に対応するためである. ↩︎

1 note · View note