Do SAT Problems Have Boiling Points？
The Boolean Satisfiability problem, called SAT for short, is the problem of determining if a set of constraints involving Boolean (True/False) variables can be simultaneously satisfied. SAT solvers have become an integral part in many computations that involve making choices subject to constraints, such as scheduling software, chip design, decision making for robots (and even Sudoku!). Given their practical applications, one question is when SAT problems become hard to solve. The problem difficulty depends on the constrainedness of the SAT instance, which is defined as the ratio of the number of constraints to the number of variables. Research in the early 90’s showed that SAT problems are easy to solve both when the constrainedness is low and when it is high, abruptly transitioning (“boiling over” ) from easy to hard in a very narrow region in the middle. My project is aimed at verifying this surprising finding. I wrote a basic SAT solver in Python and used it to solve a large number of randomly generated 3SAT problems with given level of constrainedness. My experimental results showed that the percentage of problems with satisfying assignment transitions sharply from 100% to 0% as constrainedness varies between 4 and 5. Right at this point, the time taken to solve the problems peaks sharply. Similar behavior also holds for 2SAT and 4SAT. Thus, SAT problems do seem to exhibit phase transition behavior; my experimental data supported my hypothesis.
Bezier曲線與蚶線間之關聯性的探討與推廣
在這篇報告中，我們以貝斯曲線的做圖原理建立出一種新的曲線－環狀貝斯曲線，進而得到不少有趣的結果。我們發現有名的古典曲線－蚶線，也是屬於二次環狀貝斯曲線。軌跡方程式為：，此時，係數恰符合二項式定理。之後我們推廣至n次環狀貝斯曲線的軌跡方程式：，也符合二項式定理。
在複數平面上，給定z0、z1、z2三點，我們定義出一個二次變換 ，若，，可映射成蚶線的圖形；若z∈實數，則可映射成拋物線。利用此結果類推我們找到一個複數平面上由 z0、z1、...、zn 所決定的n次變換將以原點為圓心的單位圓，映射成n次環狀Bezier曲線。
In this essay, we use the method of forming a Bezier Curve to establish a new curve, circular Bezier Curve, and find a lot of interesting results. We discover the famous classical curve ＂limacon＂, which belongs to the Quadratic Circular Bezier Curve. The locus of Quadratic Circular Bezier Curve is, where. Its coefficients match the binomial theorem. Then we apply it to the locus of nth-circular Bezier Curve:, and it also matches the binomial theorem.On the complex plane, we define a quadratic transformation corresponding to three points—z0,z1 and z2 as .If , where , a limacon is mapped. If z is a real number, a parabola is mapped. With this result, we will find a nth transformation defined by z0、z1、...、zn on the complex plane. It will form a nth-circular Bezier Curve with unit circle centering on the origin.
M&m Sequences 之研究
本專題的目的是研究以任意實數 a1 、 a2 、 a3 為起始的M&m Sequences 之穩定性質。我們主要關心的問題是：(1) 是否任給定三數a1 、 a2 、 a3 為起始的M&m 數列皆會穩定？(2) 若上述的M&m 數列穩定，則其穩定的長度與a1 、 a2 、 a3的關係為何？(3) 其穩定的值與a1 、 a2 、 a3的關係為何？我們研究的主要步驟及結果如下︰1. 當1 2 3 a 1) 為起始的M&m 數列。3. 我們證明了下列性質：(1) 若M&m 數列中前n 項所成數列的中位數為n m ，則下式成立： (2) 當存在 k > 4 , k ? N ，使得 ?1 ?2 = k k m m 成立時，則此數列穩定，且穩定長度p 滿足：min{ | 4 } ?1 ?2 = > = k k p k k 且m m ，其中p 必為奇數。(3) { n m }為單調遞增且, 5 1 ? ? ? a m n n n4. 如果x ? 41.625，則{?x,1, x}為起始的M&m 數列，其對應的數列有相同的大小次序且此M&m 數列會穩定，穩定值為41.625，且穩定長度為73。5. 我們觀察發現：如果x 1). 3. We prove the following properties: (1) If the median of the former n numbers of the M&m sequence is n m , we obtain (2) There exist k > 4 , k ? N such that ?1 ?2 = k k m m , then the sequence is stable and the stable length min{ | 4 }?1 ?2 = > = k k p k k and m m , where p must be an odd number. (3) { n m } is monotone increasing and , 5 1 ? ? ? a m n n n . 4. Suppose x ? 41.625, then the all M&m Sequences beginning with –x , 1 , x are the same, and the sequences will be stable, the stable value is 41.625 and the stable length is 73. 5. By the computer experiments, we observe that if x is any positive real number less than 41.625, the M&m Sequence starting with –x, 1, x, will be also stable but does not appear to follow any clearly discernible pattern of behavior. However, the stable lengths are much variant and exist some unknown relation with point format of x. Moreover, we have the following properties: (1)If x is a node, then the stable value is x and the stable length equals to the index of median of the node + 2； (2)Near the branch of 41.625, the stable length is almost a constant except at the edge area，the stable length of (-x,1,x) as x around branch 1 is chaos； (3)If x near the node (K= 3, 5, 7, …, 67, 69), then the stable length is l(K)+K?1 where the positive integral l(K) is determined by Prop1 (see Table 6 and 7).
正N 邊形光圈之路徑追蹤
本研究是[對於正n 邊形A1A2…An邊上一點P(含頂點)，想像自定點P 朝鄰邊發出一條光線，若依逆(順)時針方向依序與每邊皆碰撞一次，經一圈而可回到P 點，則此路徑稱為「光圈」。過程試著追蹤在正n 邊形內能形成光圈的光線行進路徑及其相關問題。
本研究令，且以逆時針得光圈來討論：
1.根據[光的反射原理]，探討光圈之存在性，發現除定點P 在正2m 邊形或正三角形的頂點外，其餘皆有光圈。
2.將可形成光圈的路徑圖展開成[直線路徑圖]來探討。
3.由[直線路徑圖]，觀察到形成光圈的光線行進路徑，可能存在下列情況： (1)不通過正n 邊形的頂點，且產生路徑循環與不循環問題。 (2)通過正n 邊形的頂點。
4.發現正2m 邊形光圈皆為[完美光圈]。
5.發現正2m+1 邊形光圈之路徑與有理數、無理數之特質有關。即當s 值為有理數時，路徑會循環；當s 值為無理數時，路徑不循環。
The research is about [on Point P (including the angles) on the side of regular polygons A1、A2…An , imagine the light goes from Point P to the closest side, then bumps each side sequentially counterclockwise. After going a circle, it’s back to Point P. The track is called “the circle of light.” I try to trace the light track of the circle of light and other correlative questions.]
In this research, we suppose,and we discuss the circle of light according counterclockwise direction:1.According to the light reflective principles, we discuss whether the circle of light exists or not. And then we discover that the circle of light really exists except when Point P is on the angles of regular triangle or regular 2m polygons. 2.Spread out the circle of light’s track to [rectilinear track.] 3.By [the picture of rectilinear track], observing there are two kinds of the circle of light’s track: (1)If the light doesn’t go through the angles of regular polygons, it can be a circulative track or a non-circulative track. (2)When the light goes through the angles, it stops. 4.We discover that all the circles of light in regular 2m polygons are [the perfect circles of light.] 5.We discover the circle of light’s track is correlative with rational numbers and irrantional numbers. When s is a rational number, the track is circulative, if s is a irrantional number, the track is not circulative.
新型空氣清淨燈具之研究與開發
本研究主要的目的是在開發同時具有空氣清淨與照明的兩種燈具。其中桌燈是基於自然對流原理，利用燈泡發熱讓氣流通過燈具上方的濾網達到過濾功能，為了尋求過濾效果與照度兼顧的最佳值，本研究並提出比較因子的概念。在吊燈方面，除了運用自然對流原理之外，還更進一步利用太陽能驅動風扇，進行強制對流，強化過濾的效果，使得本研究成果更趨於完善。 由實驗結果可得知，桌燈在四星期長期測試條件之下，其過濾效果增進率分別為39.1, 40.8與 40.1%。在吊燈四週長期實驗的結果方面，螺旋與 100W 鎢絲燈泡在自然對流的過濾效果增進率分別為49.1%與 51.4%，而100W鎢絲燈強制對流方面過濾效果增進率則為60.2%。由整個研究結果可以發現，本燈具對於空氣清淨有極佳的效果，在不增加額外耗能條件之下，能增加燈具的散熱效果與延長壽命，同時又具備空氣清淨效果，對環境空氣品質具有相當的貢獻。 The purpose of this study is to develop a novel lamp with both the functions of air-cleaning and lighting. One of it is the desk light. Basing on free convection principle, it makes the air run through the filter on the top of the lamp by its heat in order to attain the aim of air cleaning. To find the optimum value of both cleaning effect and illumination, we advanced the compare factor. The other is the droplight, though it is based on the same principle, we use the solar energy as its power to drive the fan. So that the effect of the filter can be augmented and the result of this research approach perfect. According to the experimental result, in the four-week experiment with desk light, the enhanced efficiency of filter is 39.1%, 40.8% and 40.1% respectively. On the way of droplight with four-week experiment, the enhanced efficiency of filter is 49.1% and 51.4% with helix and tungsten(100W) lamp under the condition of free convection; the enhanced efficiency of filter is 60.2% with tungsten(100W) lamp under forced convection. All these results of the research shows that the novel lamp has great performance on air cleaning and much better effect of heat sink without extra consuming of energy, also the lifespan of the lamp can be extended. Furthermore, it is capable of air cleaning and contributes to the quality of environmental air.
Microbial diversity in the Mediterranean hypersaline deep-sea lake Tyro
1. Purpose of the research Characterization of bacterial and viral diversity of brine Tyro using molecular methods of identification. 2. Procedures For bacteria: 1. Amplification or multiplication of 16S rRNA gene (one of the most conservative gene) by polymerase chain reaction (PCR). 2. Agarose gel electrophoresis and purification of PCR product 3. Ligation of purified PCR product into the vector pGEM-T 4. Transformation of plasmids containing an insert into competent cells E.coli XB1 5. Blue-white selection (we need white colonies, they contain the insert of interest) 6. Isolation of plasmids containing an insert of interest 7. Sequencing of inserts 8. Bioinformatics analysis: matching homologues from GeneBank database, construction of phylogenetic trees, statistical analysis. For viruses: The same methods were used for gp23 gene, which code a major head protein of T-even bacteriophages; to amplify gp23 gene a special set of primers was used, along with a standard cloning protocol described above. 3. Data 1) Two libraries of clones were obtained during analysis: lake Tyro (24 operational taxonomic units (OTUs), 10 classes) and sea water (6 OTUs, 2 classes of eubacteria). 2) The most abundant classes were: gamma-, delta-, epsilon- Proteobacteria, which is in agreement with previous reports about bacteria in brines of Mediterranean Sea. 3) The number of clones was not sufficient to obtain stable estimates of diversity, the analysis require additional data. 4) The diversity of bacteria was unexpectedly high in brine but not in the seawater, due to higher and more diverse ion composition. 5) Most of the detected bacteria in the deep-sea lake belonged to the previously undescribed (18,75%) bacteria or had unusual metabolism (43,75%). 4. Conclusions The analysis demonstrated unexpectedly high diversity of halophilic bacteria inhabiting Tyro lake. Most of bacteria presented in brine water had unique and uncommon characteristics based on information about its closest relatives. Therefore, the deep-sea hypersaline lakes of Mediterranean Sea have great potential for further investigations. Preliminary results of diversity of viruses of Tyro lake were obtained during analysis, more complete description is coming soon.
水分子自我組裝之機制探討
Up to this time we have spent almost three years in studying condensation and water droplets. Little could we have done as compared with the almighty nature. However we are rewarded by the nature as we gradually found the secrets about electro-magneto field and water droplets: The size of water droplets turn smaller upon electro-magneto field and grow more uniformly especially upon electric field. This experiment presented here is actually the diary of the growth of water droplets in condensation, upon magnetic field and electric field. Through convection, it discusses the self assembly patterns of water droplets and peep into the uniformity both of the size and the distribution mode of water droplets. In former basic experiment, we focus on temperature and the speed of water moisture; generally speaking, higher temperature speeds up the coalescence procedure but does not affects the nucleation size of water droplets in simple plain surroundings; while speed of moisture does affects the nucleation size. As we went farther, deep into convection and found magneto-electric force did play an important role in the self assembly mechanism of water droplets. The topic is mostly concerned as we are surrounded by magneto-electric waves in today’s world. This experiment anchors the first step in discovering the uniformity of water droplets in different environment, and providing insights into the self assembly mechanism of water droplets upon electro-magneto field with nano sizes. 這是一系列關於水蒸氣冷凝為極細微小水珠的實驗。其中可以分為兩大部分； 第一部分是基礎實驗。將水蒸氣導入至潔淨的介面上(蓋玻片)，觀察冷凝水珠的結構。雖然看似簡單平常，但卻有令人驚奇的發現；不同溫度的水蒸氣，其冷凝最初始的細微顆粒之尺寸是相同的 ！爾後隨著溫度的升高，堆疊速率也跟著上升；以致於最後一起呈現出來的水珠大小不一，尺寸不一。 第二部分是將水蒸氣導到磁場及靜電場上，觀察其冷凝結構。這部分的實驗推翻了一般「水分子是電中性在電磁場中不受影響？」的刻板觀念 ！實驗所呈現出來的冷凝水珠，不但於附加磁場中尺寸縮小又不易長大，同時還有固定的自我組成模式( Slef-assembly pattern);而且也發現在磁場中的冷凝小水珠的尺寸比電場中的小，可是電場中的小水珠則表現出較大的均勻特質。