Automates et théorié des langages
opinarer@gsu.edu.tr
Contenus
Objectif du Cours
Acquérir les notions fondamentales de la théorie des langages
Introduire les bases de la calculabilité, de la décidabilité et de la complexité.
Contenu du Cours
• Rappels mathématiques et fondements formels
• Automates finis déterministes (AFD)
• Automates finis non déterministes (AFN)
• Expressions rationnelles et théorème de Kleene
• Propriétés des langages réguliers
• Lemme de pompage pour langages réguliers
• Minimisation des automates
• Grammaires hors-contexte (CFG)
• Automates à pile (PDA)
• Propriétés des langages hors-contexte
• Normalisations
• Machines de Turing
• Indécidabilité
• Introduction à la complexité
Acquis d'Apprentissage du Cours
- Familiarisation avec l’informatique théorique
- Acquisition des principaux concepts et théorème de la théorie des langages
- Acquisition des problématique liées aux notions de calculabilité et de décidabilité.
Méthodes d'Enseignement
Cours sous forme de diaporama accessible en ligne. Exercices d'applications pendant le cours.
Ressources
- Introduction to Automata, Theory, Languages and Computation, J.E. Hopcroft, Jeffrey D. Ullman, Rajeev Motwan, Addison Wesley
- Logique(s), langages formels et complexité pour l'informatique, Narendra Jussien, Hermes
- Elements of Automata Theory, Jacques Sakarovitch , Cambridge University Press
Intitulés des Sujets
| Semaine | Intitulés des Sujets |
|---|---|
| 1 | Rappels mathématiques et fondements formels |
| 2 | Automates finis déterministes (AFD) |
| 3 | Automates finis non déterministes (AFN) |
| 4 | Expressions rationnelles et théorème de Kleene |
| 5 | Propriétés des langages réguliers |
| 6 | Lemme de pompage pour langages réguliers |
| 7 | Minimisation des automates |
| 8 | Partiel |
| 9 | Grammaires hors-contexte (CFG) |
| 10 | Automates à pile (PDA) |
| 11 | Propriétés des langages hors-contexte |
| 12 | Normalisations |
| 13 | Machines de Turing |
| 14 | Indécidabilité |
Système d'évalution
| Activités | Numéro | Contribution |
|---|---|---|
| Contribution du contrôle continu à la note finale | 1 | 50 |
| Contribution de l'examen final à la note finale | 1 | 50 |
| Total | 2 | 100 |
| Activités | Numéro | Contribution |
|---|---|---|
| Devoir | 0 | 0 |
| Présentation | 0 | 0 |
| Examen partiel (temps de préparation inclu) | 1 | 50 |
| Projet | 0 | 0 |
| Travail de laboratoire | 0 | 0 |
| Autres travaux pratiques | 0 | 0 |
| Quiz | 0 | 0 |
| Devoir/projet de session | 0 | 0 |
| Portefeuille | 0 | 0 |
| Rapport | 0 | 0 |
| Journal d'apprentissage | 0 | 0 |
| Mémoire/projet de fin d'études | 0 | 0 |
| Séminaire | 0 | 0 |
| Autre | 0 | 0 |
| Make-up | 0 | 0 |
| Total | 1 | 50 |
Evalution de la Compétence
| No | Objectifs Pédagogiques du Programme | Contribiton | ||||
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | Matematik, fizik ve mühendislik bilimlerine özgü konularda yeterli bilgi birikimi; bu alanlardaki kuramsal ve uygulamalı bilgileri, mühendislik problemlerinin modellenmesi ve çözümünde kullanabilme becerisi. | |||||
| 2 | Karmaşık bilgisayar mühendisliği problemlerini saptama, tanımlama, formüle etme ve çözme becerisi; bu amaçla uygun analiz ve modelleme yöntemlerini seçme ve uygulama becerisi. | X | ||||
| 3 | Yazılımsal veya donanımsal karmaşık bir sistemi, süreci veya donanımı gerçekçi kısıtlar ve koşullar altında, belirli gereksinimleri karşılayacak şekilde tasarlama becerisi; bu amaçla modern tasarım yöntemlerini uygulama becerisi. | |||||
| 4 | Mühendislik uygulamalarında karşılaşılan karmaşık problemlerin analizi ve çözümü için gerekli olan modern teknik ve araçları geliştirme, seçme ve kullanma becerisi; bilişim teknolojilerini etkin bir şekilde kullanma becerisi. | X | ||||
| 5 | Analitik düşünce ile bir sistemi, sistem bileşenini ya da süreci analiz etme, modelleme, deney tasarlama ve yapma, veri toplama, çözüm algoritmaları üretebilme, uygulamaya alma ve geliştirme becerileri. | |||||
| 6 | Disiplin içi ve çok disiplinli takımlarda etkin biçimde çalışabilme becerisi; bireysel çalışma becerisi. | |||||
| 7 | Türkçe sözlü ve yazılı etkin iletişim kurma becerisi; en az iki yabancı dil bilgisi; etkin rapor yazma ve yazılı raporları anlama, yazılım ve donanım tasarımını, gerekirse teknik resim metotları kullanarak raporlayabilme, etkin sunum yapabilme becerisi. | |||||
| 8 | Bilgiye erişebilme ve bu amaçla kaynak araştırması yapabilme, veri tabanları ve diğer bilgi kaynaklarını kullanabilme becerisi | |||||
| 9 | Yaşam boyu öğrenmenin gerekliliği bilinci; kendini sürekli yenileme becerisi. | |||||
| 10 | Mesleki etik ilkelerine uygun davranma, mesleki sorumluluk bilinci; mühendislik uygulamalarında kullanılan standartlar hakkında bilgi. | |||||
| 11 | Proje yönetimi, risk yönetimi ve değişiklik yönetimi gibi, iş hayatındaki uygulamalar hakkında bilgi; girişimcilik, yenilikçilik hakkında farkındalık; sürdürülebilir kalkınma hakkında bilgi. | |||||
Tableau de la Charge de Travail
| Activités | Nombre | Durée | Charge totale de Travail |
|---|---|---|---|
| Durée du cours | 14 | 3 | 42 |
| Préparation pour le cours | 14 | 2 | 28 |
| Devoir | 0 | 0 | 0 |
| Présentation | 0 | 0 | 0 |
| Examen partiel (temps de préparation inclu) | 1 | 10 | 10 |
| Projet | 0 | 0 | 0 |
| Laboratoire | 0 | 0 | 0 |
| Autres travaux pratiques | 0 | 0 | 0 |
| Examen final (temps de préparation inclu) | 1 | 12 | 12 |
| Quiz | 0 | 0 | 0 |
| Devoir/projet de session | 0 | 0 | 0 |
| Portefeuille | 0 | 0 | 0 |
| Rapport | 0 | 0 | 0 |
| Journal d'apprentissage | 0 | 0 | 0 |
| Mémoire/projet de fin d'études | 0 | 0 | 0 |
| Séminaire | 0 | 0 | 0 |
| Autre | 0 | 0 | 0 |
| baclé | 0 | 0 | 0 |
| Yil | 0 | 0 | 0 |
| Yil | 0 | 0 | 0 |
| Yil | 0 | 0 | 0 |
| Charge totale de Travail | 92 | ||
| Charge totale de Travail / 25 | 3.68 | ||
| Crédits ECTS | 4 | ||