balance9235 的部落格

[Term Project]螞蟻演算法

"一、何謂螞蟻演算法?
  螞蟻演算法Ant Colony Optimization,ACO(也有人稱Ant Colony System,ACS;或者再更簡稱AC),是一種用來在圖中尋找優化路徑的機率型技術。在1992年Dorigo等人利用了螞蟻群體合作尋找食物的行為,設計出一個用於處理最佳化問題的螞蟻演算法。1996年Dorigo 將ACS演算法與GA、SA等啟發式演算法以TSPLIB國際列題進行比較,其結果皆優於其他的演算法,其結果與最佳解誤差皆小於3.5%。

 [@more@]

二、簡介
  有看過家裡常常會有螞蟻在牆壁上或是角落,排成一排,比值的從巢穴朝著食物而去?螞蟻依賴的不是視力,更不可能是他們的智慧,螞蟻們所憑藉的是牠們身上獨特的費洛蒙,靠著費洛蒙,讓許多螞蟻可以選擇到相對來說較好的路徑來行走。

    現實生活中我們不可能去預測螞蟻的複雜行為,那我們該如何利用螞蟻的特性去研究這項演算法?其實我們可以利用訂定幾項規則出來,藉以突顯螞蟻這些複雜行為中的規律,所以我們可以由這些規則,撰寫出簡單的程式碼,來控制螞蟻的行為。畢竟,我們不需要模擬螞蟻的所有行為,我們只是需要他們找尋出問題的最佳解出來罷了。

  三、訂定規則
  上面提到我們可以藉由制定一些規則來突顯、加強螞蟻行為的特色,然後就可以利用這些特徵,來撰寫出程式,那基本上我們制定規則分為兩大類。

? 路徑的選擇規則:『Pseudo-Random-Proportional Rule』
? 費洛蒙更新規則:『Online Update』、『Offline Update』

  1. 路徑的選擇規則
  在Dorigo於1997年提出的螞蟻演算法尋路規中,利用路徑選擇規則選擇路徑以縮短計算時間,而且只在最好的解增加費洛蒙的痕跡,經實驗證明,只在最好的解上增加費洛蒙的設計,確實有助於螞蟻能最快搜尋到最佳解。

  2. 費洛蒙更新規則
  螞蟻演算法中的費洛蒙更新規則也分為兩大類,一類是費洛蒙及時更新,另一類則是費洛蒙離線更新,前者用在每隻人工螞蟻走過該路徑後,後者是在該回合結束後,針對費洛蒙值做一些適度的變更。當然,這個機制不僅僅影響了接下來螞蟻做路徑選擇的決策,還對最後路徑解的好壞有著緊密的相關。

  (1)費洛蒙即時更新(Online Update)規則
  費洛蒙的濃度,顧名思義,跟路徑上的螞蟻數量成正比與此路徑的距離長度成反比。這項規則所著重的是路徑的熱門程度,也就是費洛蒙濃度對螞蟻做出選擇時的影響,並不把距離因素考慮進去。

  (2)費洛蒙離線更新(Offline Update)規則
  在該流程結束後,對於最佳路徑解,最一些費洛蒙濃度的調整、變更,這就稱為費洛蒙離線更新。同時,對其餘非最佳路徑之解做費洛蒙蒸發的動作,如此一來,在下次行程執行時,最佳路徑解被選擇的機率就會大大的增加。

  在完成規則的制定之後,螞蟻們之間都沒有什麼直接的關聯性,牠們處在這個大環境下利用散發費洛蒙來溝通。如果有一隻螞蟻找到了食物,那牠就利用走過的路徑上殘留的費洛蒙來告知他的親朋好友說『嘿!這有食物!』,那等到其他的螞蟻經過附近,發現費洛蒙的存在後,自然就會聚集在一起,想當然的,費洛蒙的濃度也就會越來越高。
  到目前為止我們都是屬於利用費洛蒙來判斷該路徑是否為最佳路徑解,那有沒有想過,第一個發現食物的螞蟻,牠是如何找到食物的呢?這隻小螞蟻從蟻穴出發時,所有路徑費洛蒙的濃度都是一樣的,也就是說,這隻螞蟻選擇任何一條路經的機率都是相同的,既然沒有外部因素的影響,那螞蟻就基於自身本能做移動了。小螞蟻會朝著一個方向前進,但是並不是保持直線,可能會走的歪歪扭扭,有一定的隨機性,使得螞蟻運動起來具有了一定的目的性,儘量保持原來的方向,但是卻又有新的試探,尤其當碰到障礙物的時候它會立刻改變方向,這可以看成一種選擇的過程,也就是環境的障礙物讓螞蟻的某個方向正確,而其他方向則不對。這就解釋了為什麼這隻小螞蟻在複雜像迷宮的現實世界中仍然能找到隱蔽的食物。
  螞蟻演算法也可以用來解決網狀網路跳點問題,當網路流量或基地站負載改變時,透過此規劃模式背後的改良式蟻群演算機制搜尋優化路由組合,可預見的,其能力將會優於目前WiMax所使用的傳統跳點規劃方法。ACO也被應用來解許多困難的尋優問題(NP- Hard problems), 如 Traveling salesman problem, quadratic assignment problem,等…

  四、螞蟻演算法範例
  1. Initialize:
    Set t:=0              {t is the time counter}
    Set NC:=0             {NC is the cycles counter}
    For every edge (i,j) set an initial value ?ij(t)=c for trail intensity and ??ij= 0
    Place the m ants on the n nodes

  2. Set s:=1 {s is the tabu list index}
   For k:=1 to m do
    Place the starting town of the k-th ant in tabuk(s)
  3. Repeat until tabu list is full   {this step will be repeated (n-1) times}
    Set s:=s+1
    For k:=1 to m do
     Choose the town j to move to, with probability pijk (t) given by equation (4)
                   {at time t the k-th ant is on town i=tabuk(s-1)}
    Move the k-th ant to the town j
    Insert town j in tabuk(s)

  4. For k:=1 to m do
    Move the k-th ant from tabuk(n) to tabuk(1)
    Compute the length Lk of the tour described by the k-th ant
    Update the shortest tour found
   For every edge (i,j)
    For k:=1 to m do
     ??ki , j ? Q/ Lk ,if (i, j) ??tour described by tabuk
           0 ,otherwise
     ??k ij : ????ij ????ij

  5. For every edge (i,j) compute ?ij(t+n) according to equation ?ij(t+n)=?.?ij(t)+??ij
   Set t:=t+n
   Set NC:=NC+1
   For every edge (i,j) set ??ij:=0

  6. If (NC < NCMAX)
   then
    Empty all tabu lists
    Goto step 2
   else
    Print shortest tour
    Stop

    若在該演算法執行NC圈後停止,這個演算法的時間複雜度會為O(NC.n2m),事實上,步驟1 is O(n2+m),步驟2 is O(m),步驟3 is O(n2.m),步驟4 is O(n2.m),步驟5 is O(n2),步驟6 is O(n.m)。既然已經利用實驗找到蟻穴跟螞蟻數量的線性關係,所以該演算法的時間複雜度為??NC.n3)。

  旅行推銷員問題 (TSP)
  一地區有若干的城市,城市之間都有道路相連,但卻有長短之分,有一位推銷員從某一城市出發,途中須經過所有城市,最後回到原點,問這位推銷員要怎麼走,才能讓這條路徑最短?
  Loop
    randomly position num_ants on nun_city cities
       for step=1 to run  city
          for k=1 to run ant
             Choose the next city to move to applying
             a probabilistic state transition rule
          end for
       end for
    Up date pheromone trails
  Until End_condition

  五、結論與心得
  這次演算法的期末專題,我選擇『螞蟻演算法』作為題目,了解了這個演算法的名字的由來、它是如何執行、它可以解決哪些問題,等…讓我對演算法這門課也多了解一點,雖然這學期以來,在小考以及作業部分大家還是互相cover的機會比較多。等到過了這學期之後,至少大家也都有了trace程式碼、解決問題的能力。我們也知道,演算法課程學到的許多方法,不僅僅只是應用在程式方面,現實生活中也可以利用演算法來幫你解決問題。
  這份報告真的事千呼萬喚始出來,其實我在前一天就已經把這份報告完成的差不多了,只剩後面一點點的心得跟程式碼的部分,經過兩小時我完成之後,我開開心新的整理桌面,刪除我的參考資料,我不曉得是眼花還是手殘,我竟然把我的成品直接用shift + delete刪掉了,我又花了很長的時間去找拯救檔案的軟體來試,final data和Drive Rescue不過竟然只找的到我的暫存檔,十分的不甘願下,我只好重做一份了。所以我對螞蟻演算法真的是有很深的體驗啊!

  六、參考資料
  http://eca2.mis.au.edu.tw/check/paper/GA3/GA3_5.doc
  http://en.wikipedia.org/wiki/Ant_colony_optimization
  http://iridia.ulb.ac.be/~mdorigo/ACO/about.html
  螞蟻演算法.pdf
  好用的google & yahoo知識+

"

About PRAM Model

"    Parallel Random Access Machine (PRAM) is a popular model for writing parallel algorithms. It consists of a number of processors that have a common, shared memory. A parallel program is not very different from a sequential (imperative) program, but there is a special "for i pardo Pi" structure that allows for parallel execution of subprograms.
[@more@]

    PRAM is a very simple model of parallel computation that helps algorithm designers to focus in the essence of parallelism. There is no obvious way of constructing a PRAM - in particular, constructing a large and fast shared memory is believed to be difficult. On the contrary, it is easier to construct architectures with distributed memory. One of the simplest architectures representing the Distributed Memory Model (DMM) is the mesh of processors. Distributed memory model is, unfortunately, harder to program than the shared memory model.

    We are interested in running PRAM programs automatically on distributed memory model. We have shown that with certain simulation techniques, a PRAM program can be executed with very small simulation cost. Indeed, simulation is work-optimal in the following sense: If a p-processor PRAM executes a program in time T, it is simulated by a q-processor DMM (with suitably smaller q) in time less than 2*(p/q)*T.

    Most recently we have been interested in routing in a(n optical) complete network under so called OCPC assumption. In the problem setting, all p processors have h packets to route to random addresses. By OCPC (Optical Communication Parallel Computer) assumption, if two (or more) packets arrive at the same target at the same moment, both fail. We have developed some algorithms based on backoff or thinning.

"

About PRAM Model

"    Parallel Random Access Machine (PRAM) is a popular model for writing parallel algorithms. It consists of a number of processors that have a common, shared memory. A parallel program is not very different from a sequential (imperative) program, but there is a special "for i pardo Pi" structure that allows for parallel execution of subprograms.
[@more@]

    PRAM is a very simple model of parallel computation that helps algorithm designers to focus in the essence of parallelism. There is no obvious way of constructing a PRAM - in particular, constructing a large and fast shared memory is believed to be difficult. On the contrary, it is easier to construct architectures with distributed memory. One of the simplest architectures representing the Distributed Memory Model (DMM) is the mesh of processors. Distributed memory model is, unfortunately, harder to program than the shared memory model.

    We are interested in running PRAM programs automatically on distributed memory model. We have shown that with certain simulation techniques, a PRAM program can be executed with very small simulation cost. Indeed, simulation is work-optimal in the following sense: If a p-processor PRAM executes a program in time T, it is simulated by a q-processor DMM (with suitably smaller q) in time less than 2*(p/q)*T.

    Most recently we have been interested in routing in a(n optical) complete network under so called OCPC assumption. In the problem setting, all p processors have h packets to route to random addresses. By OCPC (Optical Communication Parallel Computer) assumption, if two (or more) packets arrive at the same target at the same moment, both fail. We have developed some algorithms based on backoff or thinning.

"

parallel algorithm

"

In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is one which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.

    Some algorithms are easy to divide up into pieces like this. For example, splitting up the job of checking all of the numbers from one to a hundred thousand to see which are primes could be done by assigning a subset of the numbers to each available processor, and then putting the list of positive results back together.

[@more@]

    Most of the available algorithms to compute Pi, on the other hand, can not be easily split up into parallel portions. They require the results from a preceding step to effectively carry on with the next step. Such problems are called inherently serial problems. Iterative numerical methods, such as Newton's method or the three body problem, are also algorithms which are inherently serial. Some problems are very difficult to parallelize, although they are recursive. One such example is the depth-first search of graph.

    Parallel algorithms are valuable because it is faster to perform large computing tasks via a parallel algorithm than it is via a serial (non-parallel) algorithm, because of the way modern processors work. It is far more difficult to construct a computer with a single fast processor than one with many slow processors with the same throughput. There are also certain theoretical limits to the potential speed of serial processors. On the other hand, every parallel algorithm has a serial part and so parallel algorithms have a saturation point (see Amdahl's law). After that point adding more processors does not yield any more throughput but only increases the overhead and cost.

    The cost or complexity of serial algorithms is estimated in terms of the space (memory) and time (processor cycles) that they take. Parallel algorithms need to optimize one more resource, the communication between different processors. There are two ways parallel processors communicate, shared memory or message passing.

    Shared memory processing needs additional locking for the data, imposes the overhead of additional processor and bus cycles, and also serializes some portion of the algorithm.

    Message passing processing uses channels and message boxes but this communication adds transfer overhead on the bus, additional memory need for queues and message boxes and latency in the messages. Designs of parallel processors use special buses like crossbar so that the communication overhead will be small but it is the parallel algorithm that decides the volume of the traffic.

    Another problem with parallel algorithms is ensuring that they are suitably load balanced. For example, checking all numbers from one to a hundred thousand for primality is easy to split amongst processors, however some processors will get more work to do than the others, which will sit idle until the loaded processors complete.

    A subtype of parallel algorithms, distributed algorithms are algorithms designed to work in cluster computing and distributed computing environments, where additional concerns beyond the scope of "classical" parallel algorithms need to be addressed.

"

About Schema

    XML Schema如W3C建議,發布於2001年五月,是許多XML綱要語言中的一支。它是首先分離的於XML本身的綱要語言,故取得W3C的推薦地位。像所有XML綱要語言一樣,XML Schema有時用來表達一組綱要──一組XML文件必須遵守的規定,這樣根據該綱要才『合法』。然而,不像大部分其他綱要語言一樣,XML Schema亦意圖設計來確認在一收集來的資料與內附特殊資料型別的結果,它對開發XML文件處理軟體有助益,不過同時召來了非議。

    因為有其他XML綱要語言存在,故在引用這W3C建議的語言時,使用XML Schema或W3C XML Schema,Schema永遠字首大寫。

    一個XML Schema的實例是XML Schema定義(XSD),而且通常它的檔名後綴以".xsd"。該語言本身有時在通俗上說成XSD,雖然WXS(對W3C XML Schema來說)是更適當的字頭集縮寫(initialism)。

    經過XML Schema為基的驗證後,依照驗證意含的資料模型表達XML文件結構與內容是可能的。XML Schema資料模型包括:
    字彙(元素與屬性名稱集)
    內容模型(關聯與結構)
    資料型別群
   
    這些訊息集成又叫後Schema驗證資訊集(Post-Schema-Validation Infoset (PSVI))。PSVI賦予合法XML文件它的"型別"並促進以物件般處理文件,如使用物件導向編程(OOP)變化型般操作。

  這種對XML資料存取的特別的物件導向編程實現主要為微軟──對XML Schema發展的主要貢獻者──所倡導。轉換一份XML文件到自行資料型別感知物件在某些軟體設計部份相當有利。然而批評家爭論這同時暗中破壞了開放性──XML的主要特徵──並且它偏向於相容原生於微軟偏好的編程語言的資料型別。另,從XML Schema資料型別繼承出去的(以及肇因於XML Schema資料型別的)限制、這些資料型別與其他XML Schema間受限的搭配、以及在其他W3C規格裡這些資料型別的相依性,是許多XML軟體發展師的爭論焦點。

 

[Pre class]B-Trees

  B樹是一種樹資料結構,常見於資料庫與檔案系統之中。B樹能夠使資料保持有序,並擁有均勻的對數處理時間的插入和刪除動作。B樹的元素通常會自底向上插入,有別於多數自頂向下插入的二元樹。
[@more@]

  B樹在節點訪問時間遠遠超過節點內部訪問時間的時候,比可作為替代的實現有著實在的優勢。這通常在多數節點在次級存儲比如硬碟中的時候出現。通過最大化在每個內部節點內的子節點的數目減少樹的高度,平衡操作不經常發生,而且效率增加了。這種價值得以確立通常需要每個節點在次級存儲中佔據完整的磁碟塊或近似的大小。

  B背後的想法是內部節點可以有在預定範圍內的可變數目的子節點。因此,B樹不需要象其他自平衡二元搜尋樹那樣經常的重新平衡。對於特定的實現在子節點數目上的低和高邊界是固定的。例如,在 2-3 B樹(常簡稱為2-3 樹)中,每個內部節點只可能有2或3個子節點。如果節點有無效數目的子節點則被當作處於違規狀態。

  查找
  查找以典型的方式進行,類似於二元搜尋樹。起始於根節點,自頂向下遍歷樹,選擇其分離值在要查找值的任意一邊的子指針。在節點內部典型的使用兩分查找來確定這個位置。

  插入
  節點要處於違規狀態,它必須包含在可接受範圍之外數目的元素。
  1.首先,查找要插入其中的節點的位置。接著把值插入這個節點中。
  2.如果沒有節點處於違規狀態則處理結束。
  3.如果某個節點有過多元素,則把它分裂為兩個節點,每個都有最小數目的元素。在樹上遞歸向上繼續這個處理直到到達根節點,如果根節點被分裂,則建立一個新根節點。為了使它工作,元素的最小和最大數目典型的必須選擇為使最小數不大於最大數的一半。

  刪除
  1.首先,查找要刪除的值。接著從包含它的節點中刪除這個值。
  2.如果沒有節點處於違規狀態則處理結束。
  3.如果節點處於違規狀態則有兩種可能情況:
    1.它的兄弟節點,就是同一個父節點的子節點,可以把一個或多個它的子節點轉移到當前節點,而把它返回為合法狀態。如果是這樣,在更改父節點和兩個兄弟節點的分離值之後處理結束。
    2.它的兄弟節點由於處在低邊界上而沒有額外的子節點。在這種情況下把兩個兄弟節點合併到一個單一的節點中,而且我們遞歸到父節點上,因為它被刪除了一個子節點。持續這個處理直到當前節點是合法狀態或者到達根節點,在其上根節點的子節點被合併而且合併後的節點成為新的根節點。

About PageRank

  PageRank,網頁排名,又稱網頁級別、Google左側排名或佩奇排名。PageRank™是以公司創辦人拉里·佩奇(Larry Page)命名。是一種由搜索引擎根據網頁之間相互的超連結計算的網頁排名。它經常和搜索引擎優化有關。PageRank系統被Google用來體現網頁的相關性和重要性。Google的創始人拉里·佩奇和謝爾蓋·布林1998年在史丹福大學發明了這項技術。

  PageRank通過網路浩瀚的超連結來往來確定一個頁面的等級。Google把從A頁面到B頁面的連結解釋為A頁面給B頁面投票Google根據投票來源(甚至來源的來源,即連結到A頁面的頁面)和投票目標的等級來決定新的等級,簡單的說,一個高等級的頁面可以使其他低等級頁面的等級提升。

[@more@]

簡單的來說:網站連結進來的數量,愈多,當然愈好。外部連結網站自己的PageRank,愈高愈好。外部連結網站連結出去的數量,越低越好。
 
  如何提高PageRank?
 
  瘋狂登錄:將你的資料提供給所有搜尋引擎,這樣最起碼PageRank可以向上提升1到2分。

  與朋友互相連結:團結就是力量,你有網站、我也有,只要兩個人的網站互連,就會彼此受惠,PageRank都會提高「一點點」,何樂而不為,而且互相拉抬之後,如果朋友的網站PageRank因此提高,從他那邊分過來的分數也會提高,但也切勿漫無目的隨意內容相差太多的網站,否則可能被當成惡搞。

  提升網站品質:只要你的網站資料豐富、有趣,不用要求也會有人主動連結,這是經營網站的本質,也是確保PageRank的重要手段。我常常上網查到底有誰連結過Richyli.com,每次都覺得很好玩,也很感謝這些站長的連結。

About XPath

  XPath is a language for finding information in an XML document. XPath is used to navigate through elements and attributes in an XML document.XPath is a major element in the W3C's XSLT standard - and XQuery and XPointer are both built on XPath expressions. So an understanding of XPath is fundamental to a lot of advanced XML usage.

 

  What is XPath?
1.XPath is a syntax for defining parts of an XML document
2.XPath uses path expressions to navigate in XML documents
3.XPath contains a library of standard functions
4.XPath is a major element in XSLT
5.XPath is a W3C Standard

  XPath Path Expressions
XPath uses path expressions to select nodes or node-sets in an XML document. These path expressions look very much like the expressions you see when you work with a traditional computer file system.

  We will use the following XML document in the examples below.

<?xml version="1.0" encoding="ISO-8859-1"?><bookstore><book>
  <title lang="eng">Harry Potter</title>
  <price>29.99</price>
</book><book>
  <title lang="eng">Learning XML</title>
  <price>39.95</price>
</book></bookstore>
 
  After I've read this wedsite.I learned how to use XPath to navigate through elements and attributes in an XML document.And I also learned how to use some of the standard functions that are built-in in XPath.So I do understand what is XPath doing.That's really great!

About XML Project:SAML

組員名單:
資工二乙 494512229 朱育民
資工二乙 494512293 賀毓軒
資工二乙 494512475 沈馥安
資工二乙 494512516 姚宗宇

  OASIS(資訊標準架構促進會)於7月13日發表安全宣示標記語言(Security Assertion Markup Language,SAML),是以XML為基礎發展而成的。

  目的是提供採用Web Services的不同站臺,可以藉由SAML彼此溝通,並且安全地交換授權及認證,主要透過四種宣示以提高XML架構的安全性:認證宣示、屬性宣示、決策宣示及授權宣示。藉由SAML可以整合Web-based的安全機制達到單一登入的功效,能夠讓多家服務供應商跨站臺使用,並且以標準架構及協定提供資源共享的服務。

  在SAML運作中主要的角色包括主體(subject),也就是用戶,以及依賴方(relying party)或服務提供方(service provider),也就是提供網路服務的廠商。主體是訂定身份識別聲明的用戶。聲明方(asserting authority)或稱為可信賴的第三者,是用戶所屬的網域或委託者,透過其發行的身份識別可以被網路上其他廠商所接受。依賴方或服務提供方則是SAML聲明的接收者與驗證者;基於可信賴的第三者所提供的身份證明文件,授與該用戶存取權與各式許可證明。

  SAML 2.0預期將大大延伸其可用性。儘管SAML 2.0作了不少修正,此標準仍是一個新興而有待加強的技術。即使還在試行階段,SAML已提供在企業信任關係下,達到跨網域間分享應用程式、資料以服務,而不需額外建構與管理其他外部使用者的身份資訊,這已經跨出了一大步。在SAML架構下,客戶可以很輕易地從一個網站到另一個網站,而不需重新作身份驗證;企業可藉此減少建置身份識別管理的成本,以及相關基礎建設支出。最重要的是可以增進使用者愉快的使用經驗。

  心得:這次做這個專題,可能因為大家都已經很熟了吧,所以沒有意見不統一,或是爭執的發生,基本上可以算是一切順利的產生了所有的東西,大家配合度也都很高,所以算是很順利的完成了這次xml的專題!不過,可能因為這次的題目不是可以時做出來,加上資料也比較少,所以報告時顯的有點乾,但是大家都盡力了,所以不錯囉!

  貢獻百分比:姚宗宇、沈馥安、賀毓軒、朱育民都是25%

關於DTD

●何謂DTD?
DTD(Document Type Definition;文件型別定義)是一種用來定義XML文件規格的語法,其中規範了文件中所有可用的元素、屬性、記法和各種實體,以及其間的相互關係。DTD能讓你的文件格式具有自我描述能利。DTD起源於SGML(1986),XML起源於SGML,而XML的DTD更可說是直接來自SGML的DTD。由DTD所描述的語標語言,稱為一種application。其中最著名的,算是HTML。

●為何需要DTD?
有時光是well-formed並不能確保資訊的正確性。因其內涵可能不正確。這就必須使用DTD加以規範。

●使用DTD的好處:
一、提供資料格式一致化描述
二、驗證資料正確性
三、資料自動化處理
四、促進專業分工
五、提供更好的建構功能

●DTD的基本語法

文件型別宣告的規則:
一、一定要出現在文件實體之前
二、在一個XML文件中,只可出現一個DTD宣告
三、XML中所有元素都需在DTD中定義
四、DTD註解方式和XML其他地方相同
五、DTD可內部宣告,亦可外部宣告

元素宣告:
元素宣告的作用在宣告一個元素的名稱是什麼、可以有哪些子元素、元素的資料型態及組成方式等。同一個元素在DTD中只能定義一次。

實體宣告:
類似程式語言中的巨集功能,能夠讓我們以特定的某個名稱來代表一段資料內容。而實體宣告分成三類,內部實體、外部實體、參數實體。

記法(notation)宣告:
記法宣告可指明外部二進位檔案的資料型態。這個資料會傳遞給應用程式。其真正的用途則有應用程式自行決定。
用於指定外部檔案格式
<?NOTATION GIF87A SYSTEM “GIF”>
<!NOTATION JPEG SYSTEM “Joint Photographic Experts Group”>

 

頁面